I've got many RE16 with using python 3.4. Did anybody else get it? How did you solve it?

Help pls with test 10

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

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

I have WA12. Help me!

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

need help me please....

Edited by author 01.05.2009 17:09

Edited by author 01.05.2009 17:09

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

Что за ****?)

thanks I've got AC!!!

Edited by author 16.08.2008 02:45

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

give me this test becose i dont understand while and where error

whats wrong with test №6 help me pls. And give me pls other tests, because I want to test this problem.

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.

What's wrong with this test?

Help me, please.. Thanks..

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