|
|
I've got many RE16 with using python 3.4. Did anybody else get it? How did you solve it? I don't know why , but I just stopped using division in my solution and got AC! thanks I've got AC!!! Edited by author 16.08.2008 02:45 Me too. What's on this test? A very nice thing happend to me! When I used long arithmetic with base 10^17 I got TL many times. Even after I made my program calculate an expression like (2^N * 3^M) only one time! (I didn't use fast power). Then I generally rewrote my class BigInteger, and now it can calculate the product of two big numbers :) So I used the "fast-power" algo, and after this I immediately got AC in 0.156s. It should be noted that now I use base = 10^9 and store the numbers in vector (earlier they were stored in arrays). Of course, these "upgrades" make this class work slower and use more memory. But my program uses only ~700 KB of memory (it was another surprise for me). The only thing I did to make my program faster was use the algo written above. I didn't expect it would work much faster... So, fast power RULEZZZ! :D Edited by author 27.09.2010 01:39 The answer will contain 23857 digits in this case! What to do? Long arithmetic will not help because of TL use long arithmetic on base (9-17)-digits ;) Maybe someone could give me some tests to find the bug in my program. I have tried the tests on this forum(and others) and it provides the correct answer(for those tests). L.E.: Never mind, I got accepted. Using an automated test generator, which I wrote, I found that my program failed to provide a correct answer on the following test: //Input 2 -1 -1 //Correct Output 1 //My Output -1 And obviously, it failed all tests of the type n -1 -1 ... -1 by providing the answer -1. Maybe this will help others of wasting a few days on the problem. Edited by author 23.02.2010 21:27 need help me please.... Edited by author 01.05.2009 17:09 Edited by author 01.05.2009 17:09 My old program get AC, but on the test 15 2 -2 3 -1 0 2 1 -1 1 3 -2 -1 -3 -2 3 My old answer on this test is 36, but right answer is 108. I noticed it only when I wrote the solution again. Try this test 8 -1 0 -1 -3 -2 1 2 1 right answer is 12. 15 -1 2 2 1 -1 2 3 -3 2 2 -2 2 -2 0 0 right answer is 2304 15 -1 -3 -2 0 -1 2 -1 -2 1 2 0 -2 0 0 2 right answer is 8 I don't understand, how it is possible to get the answer for the test 50000 3 3 3 3 ... 3 3^50000 has length around 23856. Use long arithmetics :) How do it fast, so it can pass the time limit? Maybe there are some trick there. Long multiplication takes very long time, to do it 50000 times. I used just long by short (< 2^63) multiplication. Calculate it as ((3^2)^2 * 3)^2 * 3 for 3^11. For calculating product, do we have to see how many consecutive numbers are same so as to calculate product of them by logarithmic power method? Because I see no other way to use the power method of logarithmic time... Note, that given "an integer not exceeding 3 in absolute value" Edited by author 01.01.2009 16:16 x = 3^50000 does x have length 23856 or 23857? does it start in 115 and end in 761000001? import java.io.*; import java.math.*; import java.util.*; public class Main {
static BigInteger ans, a2, a3; static int dans[], t[]; static StreamTokenizer in; static PrintWriter out; static double C32 = Math.log(3) / Math.log(2); static double C23 = Math.log(2) / Math.log(3);
static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; }
public static void count(int p[]) { dans[0] = 2; t[2] = p[2] - dans[2]; t[3] = p[3] - dans[3];
if (t[2] >= 0 && t[3] >= 0) { dans[2] = p[2]; dans[3] = p[3]; } else if (t[2] < 0 && t[3] < 0); else { if (t[2] == 0 || t[3] == 0); else { if (t[2] > 0 && t[3] < 0) { if ((double)t[2] * C23 + (double)t[3] > 0) { dans[2] = p[2]; dans[3] = p[3]; } } else if (t[2] < 0 && t[3] > 0) { if ((double)t[3] * C32 + (double)t[2] > 0) { dans[2] = p[2]; dans[3] = p[3]; } } } } }
public static void main(String[] args) throws Exception {
in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter print = new PrintWriter(System.out);
BigInteger negStart, posStart; ans = BigInteger.ZERO;
t = new int [4]; dans = new int[4]; dans[0] = 0; dans[1] = 0; dans[2] = 0; dans[3] = 0;
int neg[] = new int[4]; int pos[] = new int[4]; neg[0] = 0; neg[1] = 0; neg[2] = 0; neg[3] = 0; pos[0] = 0; pos[1] = 0; pos[2] = 0; pos[3] = 0;
int saveneg[] = new int[4]; int savepos[] = new int[4]; for(int j = 0; j < 4; j++) { saveneg[j] = neg[j]; savepos[j] = pos[j]; }
int n = nextInt(); int a, b = 0;
for(int i = 1; i <= n; i++) {
a = nextInt(); if (i == 1) { ans = BigInteger.valueOf(a); b = a; } else if (b < a) b = a;
if (neg[1] + neg[2] + neg[3] == 0 && a < 0) { ++neg[-a]; neg[0] = 0; } else { if (a == 0) { // count neg[0] = 0; neg[1] = 0; neg[2] = 0; neg[3] = 0; } else if (a < 0) { ++neg[-a]; neg[0] = 2 - neg[0]; } else if (neg[1] + neg[2] + neg[3] > 0) ++neg[a]; }
if (pos[1] + pos[2] + pos[3] == 0 && a > 0) { ++pos[a]; pos[0] = 2; } else { if (a == 0) { // count pos[0] = 0; pos[1] = 0; pos[2] = 0; pos[3] = 0; } else if (a < 0) { if (pos[1] + pos[2] + pos[3] > 0) { ++pos[-a]; pos[0] = 2 - pos[0]; } } else ++pos[a]; }
if (neg[0] == 2) count(neg); if (pos[0] == 2) count(pos);
}
if (dans[0] == 2) { a2 = BigInteger.valueOf(2); a3 = BigInteger.valueOf(3); a2 = a2.pow(dans[2]); a3 = a3.pow(dans[3]); a2 = a2.multiply(a3); if (a2.compareTo(ans) > 0) ans = a2; }
a2 = BigInteger.valueOf(b); if (ans.compareTo(a2) < 0) ans = a2;
String r = ans.toString(); System.out.println(r); print.close();
}
} Edited by moderator 08.10.2008 17:57 Use your own data structure to calculate the answer. My Java solution works in 0.7 sec Help me, please.. Thanks.. Because you passed 14 test with BigNum you is Ok therefore you have problem with logic of the task. In this situation simple but clever test may help and they easy to produce if having AC. Try the next: 15 1 -1 0 2 -2 0 3 -1 0 0 -3 -3 2 0 1 Ans=18 and this one: 11 -1 0 -1 0 -3 0 -1 0 0 0 -2 Ans=0 Edited by author 29.10.2007 22:39 I used big numbers only for printing answer. I like my solution :) Got WA14 too... But currently I use big numbers for temporary calculations. Got AC. The problem was with long arithmetics. I wrote it modulo 10000, and it started overflowing after squaring because number of digits also must be taken into consideration. After reverting to modulo 1000, it worked fine. Try test with 50000 of 3s, check if you do not get negatives in the answer. assert function doesn't work here. for the program i used assert.it failed there was no response #include<iostream> #include<cassert> using namespace std; int main(){ assert(0==1); return 0; } the above program must result in a statement program aborted.But instead the program gives WA assert() function outputs a message and ends the program with nonzero return code. Of course, the Judge interprets such behaviour as wrong answer. It is not "of course" becase other online judges (and real ACM contest servers) treat non-zero return as runtime error. I usually abort with #define FAIL *(int*)0 = 0 causes CRASH runtime error give me this test becose i dont understand while and where error You can mail your code to me. I'll try to find a bad test for your. Of fix a bug. naxart@yandex.ru whats wrong with test №6 help me pls. And give me pls other tests, because I want to test this problem. What's wrong with this test? does it mean: -3, -2, -1.. etc? or say: -1 (1 1 2 -2 -1) i am choosing the last 5? Edited by author 27.10.2007 17:16 |
|
|