## 10754 - Fantastic Sequence

Moderator: Board moderators

backslash null
New poster
Posts: 8
Joined: Tue Nov 11, 2003 11:02 pm

### 10754 - Fantastic Sequence

Hi very body,
any idea to solve this problem fast.
I used some kind of DP but got TLE.

thanx.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
just an hint: Matrix multiplication

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
What should be the output of:

Code: Select all

``````1
2 1000 0
1 1 1
-10 -10
``````
I think it should be 990, am I right?

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
Well, my AC program actually outputs -10.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
My AC code returns 990.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Just got AC.
I was too stupid, forget to handle k=0.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### test cases

i am getting wa. can anyone give me more test cases.

ranjit

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### AC finally

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)
Just another brick in the wall...

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india
Thanks. Even i didnt initialize properly !!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Any more test cases? My program solves all of the above cases correctly and quickly, yet always WA......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Some random input: 10754.zip

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Ha... my code gets the same output as yours.........

[EDIT]Changed something about data type and got Accepted. Thanks everyone!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### I still got WA :'(

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?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
(-3) * (27884) - 1 = -83653 = -7 = 2 (mod 9)