11191 - Square

[sclo]

Maybe that's a good reason for everyone to switch to Java or C/C++

[Observer]

Maybe . But I don't have time to do so now. You know, the heavy schoolworks....

And to me, writing programs in PASCAL is as comfortable as talking in my own language. Anyway, will write more C/C++ programs in the coming Easter holiday I think.

[Sedefcho]

I think this is a really nice problem as it requires some knowledge
in a lot of different areas: Number Theory, Combinatorics,
Bitwise Masks and Operations.

Here is some sample input. I hope it will be useful to someone.

Code: Select all

12
3
2 2 2
3
2 2 4
3
2 -2 2
3
0 2 5
4
10 14 35 29
1000
29 13 17 35 121 29 13 17 35 121 29 13 17 35 121 29 13 17 35 11 29 13 17 35 11 29 169 169 169 11 29 13 17 35 169 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 29 13 17 35 11 
5
1 1 1 -1 -1
6
0 0 -1 -1 4 7
10
1 1 0 0 -1 1 -1 2 8 16
100
1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 1 1 0 0 -1 1 -1 2 8 16 
500
8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 8 0 -8 -3 -27 1 1 -1 9 121 
100
64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 64 729 15625 117649 1771561 4826809 24137569 47045881 148035889 594823321 

And here is the corresponding output:

Code: Select all

3 0
1 1
1 0
2 1
0 1
98134 686826
4 4
10 17
25 76
2950 104620
52250 8785500
4950 161700

Good luck to everyone.

[Spykaj]

I have acc and I think it is not so easy problem ;p

[Sedefcho]

Yes, sure.

I didn't say it is easy, I said it is a nice problem

I really liked that problem although my ACC runtime
is about 5 secs i.e. it is nothing special.

Regards.

[Robert Gerbicz]

Hi all! I'm new on this forum from Hungary, but I've already solved 200+ problems.

Here is some sample input. I hope it will be useful to someone.

My c++ program has given the same output! But I'm getting only WA. I think I've figured out the math of the problem and
1. I'm using long long int for X,Y
2. If n<1 (the length of the sequence) then the output is 0 0
3. Now I'm using fread/fwrite, I hope that part is correct.

What can be wrong?
Can somebody give me more input/output?

[Robert Gerbicz]

I've solved the problem, the size of num array was smaller by one that was needed! Now my program time is 2.176 sec. and second place. Not bad.

My previous program was failed on this test case: ( the largest number is 2*3*5*7*11*13*17*19*23*29 )

Code: Select all

1
6
-2310 2310 -2800733 2800733 -6469693230 6469693230

and the correct output is 0 4

[Akter_Sust]

Find Out any bug in my code or please give me some testcase for which my code dosent work. My code got WA.

Code: Select all

cut after Acc and Thnx to piklu_Sust

[Piklu_sust]

I changed the following part of your code and get it accepted.
Your code:

Code: Select all

int n,i,j,u,v;
long long m,zero;

I changed that part:

Code: Select all

int i,j,u,v;
long long n, m,zero;

For your regards:
1. After accepted, you should remove your code from the post.
2. If you cofuse about the limit of number or range of number after operation, always use the largest one.
3. You can improve your running time using map or hashing.

Wish you good luck.