Page 1 of 2
10754 - Fantastic Sequence
Posted: Sun Oct 31, 2004 3:47 pm
by backslash null
Hi very body,
any idea to solve this problem fast.
I used some kind of DP but got TLE.
thanx.
shahiN_reloadeD
Posted: Sun Oct 31, 2004 7:33 pm
by abishek
just an hint: Matrix multiplication
Posted: Wed Nov 03, 2004 4:30 am
by Cho
What should be the output of:
I think it should be 990, am I right?
Posted: Wed Nov 03, 2004 5:47 am
by abishek
Well, my AC program actually outputs -10.
Posted: Wed Nov 03, 2004 6:31 am
by Cho
Any tricks to handle negative input?
Or any tricky thing I missed?
(I originally convert all negative numbers to positive, I've just removed this part of code after reading previous post.)
I use long long to store all the value, I %m for each addition and multiplication, but still keep getting WA.
Posted: Wed Nov 03, 2004 11:08 am
by Krzysztof Duleba
My AC code returns 990.
Posted: Wed Nov 03, 2004 3:06 pm
by Cho
Just got AC.
I was too stupid, forget to handle k=0.
test cases
Posted: Wed Jan 05, 2005 3:56 pm
by ranjit
i am getting wa. can anyone give me more test cases.
thanks in advance,
ranjit
AC finally
Posted: Fri Jan 07, 2005 9:56 am
by helmet
Of all the trivial mistakes I could make , this one took the cake.I hadn't initialised one of my arrays properly!!!AC finallly (phew)
Anyways I hope the sample ip-op is correct:
- 16
2 76 0
2147483647 2147483647 -2147483648
-2147483647 -2147483648
2 76 1
2147483647 2147483647 -2147483648
-2147483647 -2147483648
2 76 2
2147483647 2147483647 -2147483648
-2147483647 -2147483648
2 76 3
2147483647 2147483647 -2147483648
-2147483647 -2147483648
2 76 4
2147483647 2147483647 -2147483648
-2147483647 -2147483648
0 88 10
2147483647
2 1000 0
1 1 0
-1 -1
2 30 1
1 1 0
-1 -1
2 54 2
1 1 0
-1 -1
2 3453 3
1 1 0
-1 -1
2 3453 4
1 1 0
-1 -1
2 45 5
1 1 0
-1 -1
2 543 6
1 1 0
-1 -1
5 85785 34385
34 -54 2332 -543 54 -555
213 23 22 333 -42
1 1 1
1 1
1
5 89485 435
345 45 454 -555 -555 -555
-234 -35 -54 -54 -54
output:
- 17
16
63
41
72
23
999
29
52
3450
3448
37
530
12000
0
59651
I hope people learn to find their flaws with their own ip-op as well
.
(note the point CC)
Posted: Sat Jan 08, 2005 7:25 am
by ranjit
Thanks. Even i didnt initialize properly !!
Posted: Wed Nov 09, 2005 10:11 pm
by Observer
Any more test cases? My program solves all of the above cases correctly and quickly, yet always WA......
Posted: Thu Nov 10, 2005 5:00 am
by Cho
Some random input:
10754.zip
Posted: Thu Nov 10, 2005 2:29 pm
by Observer
Ha... my code gets the same output as yours.........
[EDIT]Changed something about data type and got Accepted. Thanks everyone!!
I still got WA :'(
Posted: Thu Dec 22, 2005 6:28 am
by FAQ
I tried tests of Cho. I have a question
This test
Code: Select all
1 9 9
-3 -1
4
a[0] = 4
a[1] = (-3) * 4 - 1 = -13
a[2] = (-3) * (-13) - 1 = 38
a[3] = (-3) * (38) - 1 = -115
a[4] = (-3) * (-115 ) - 1= 344
a[5] = (-3) * (344) - 1 = -1033
a[6] = (-3) * (-1033) - 1 = 3098
a[7] = (-3) * (3098) - 1 = -9295
a[8] = (-3) * (-9295) - 1 = 27884
a[9] = (-3) * (27884) - 1 = 83653
then a[9] mod 9 = 7, but your answer is 2 ?
Am I wrong?
Posted: Thu Dec 22, 2005 11:42 am
by mf
(-3) * (27884) - 1 = -83653 = -7 = 2 (mod 9)