10754 - Fantastic Sequence

[backslash null]

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


thanx.
shahiN_reloadeD

[abishek]

just an hint: Matrix multiplication

[Cho]

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]

Well, my AC program actually outputs -10.

[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.

[Krzysztof Duleba]

My AC code returns 990.

[Cho]

Just got AC.
I was too stupid, forget to handle k=0.

[ranjit]

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

thanks in advance,
ranjit

[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)

[ranjit]

Thanks. Even i didnt initialize properly !!

[Observer]

Any more test cases? My program solves all of the above cases correctly and quickly, yet always WA......

[Cho]

Some random input: 10754.zip

[Observer]

Ha... my code gets the same output as yours.........

[EDIT]Changed something about data type and got Accepted. Thanks everyone!!

[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?

[mf]

(-3) * (27884) - 1 = -83653 = -7 = 2 (mod 9)