10754 - Fantastic Sequence

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

Moderator: Board moderators

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

10754 - Fantastic Sequence

Post by backslash null » Sun Oct 31, 2004 3:47 pm

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

thanx.
shahiN_reloadeD

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Sun Oct 31, 2004 7:33 pm

just an hint: Matrix multiplication

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Nov 03, 2004 4:30 am

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?

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Wed Nov 03, 2004 5:47 am

Well, my AC program actually outputs -10.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Nov 03, 2004 6:31 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Nov 03, 2004 11:08 am

My AC code returns 990.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Nov 03, 2004 3:06 pm

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

Post by ranjit » Wed Jan 05, 2005 3:56 pm

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

thanks in advance,
ranjit

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

AC finally

Post by helmet » Fri Jan 07, 2005 9:56 am

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 :D.
(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

Post by ranjit » Sat Jan 08, 2005 7:25 am

Thanks. Even i didnt initialize properly !!

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

Post by Observer » Wed Nov 09, 2005 10:11 pm

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

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Nov 10, 2005 5:00 am

Some random input: 10754.zip

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

Post by Observer » Thu Nov 10, 2005 2:29 pm

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

[EDIT]Changed something about data type and got Accepted. Thanks everyone!! :wink:
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 :'(

Post by FAQ » Thu Dec 22, 2005 6:28 am

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:

Post by mf » Thu Dec 22, 2005 11:42 am

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

Post Reply

Return to “Volume 107 (10700-10799)”