11191 - Square

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj »

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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz »

Hi all! I'm new on this forum from Hungary, but I've already solved 200+ problems.
Sedefcho wrote: 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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by 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
New poster
Posts: 4
Joined: Sat Sep 16, 2006 9:55 am

Re: 11191 - Perfect Square

Post by 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
Last edited by Akter_Sust on Fri Jun 13, 2008 6:39 am, edited 1 time in total.

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Re: 11191 - Perfect Square

Post by 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.

Post Reply

Return to “Volume 111 (11100-11199)”