10450  World Cup Noise
Moderator: Board moderators

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:
10450  World Cup Noise
Hi !
I tried to solve "world cup noise" 4 times but I only got Time Limit Exeeded and WA.
I know it seem to be an easy problem. But I really don't understand why I can't manage to get Acc.
Is that anybody could give me a heap of sample input/outpout
Thanks.
______________________
 Theocrite le Newbee 
I tried to solve "world cup noise" 4 times but I only got Time Limit Exeeded and WA.
I know it seem to be an easy problem. But I really don't understand why I can't manage to get Acc.
Is that anybody could give me a heap of sample input/outpout
Thanks.
______________________
 Theocrite le Newbee 
Last edited by bery olivier on Sat Feb 15, 2003 3:16 pm, edited 1 time in total.

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:
Well anyway, the first time I sent my source I got WA. Then I print the 4 last numbers ( if(51) printf("XXX"); I know it's not really beautiful, but it was accepted. I'll try to improve it) and it worked perfectly. I don't know what's the matter. Maybe something wrong whit my compiler or something else.
Not AC yet AC at last
why fibonacci?
hei,
I spent some time on the problem and I just couldn't figure out how to solve it, but after looking at this thread, it seems that it is using the fibonacci numbers  could someone explain me why or just recommend some book/website? thanx a lot.
I spent some time on the problem and I just couldn't figure out how to solve it, but after looking at this thread, it seems that it is using the fibonacci numbers  could someone explain me why or just recommend some book/website? thanx a lot.
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
code : array [1..50] of longint;
zeros : longint;
when n = 1
there are only two possibilities '1' and '0'
for n = 2 we try to add '0' and '1' after them
(code[1] = 2 , zeros = 1(one number end with zero))
for number end with '1' , we can add '0' only
for '0' , we can add both '0' and '1'
so '10' , '01' , '00' ( total number = zeros * 2 + ones = 3
new zeros = code[1])
.........
we come up with the code
zeros:= 1;
code[1]:=2;
for i:=2 to 50 do begin
code := code[i1] + zeros;
{code:= code[i1]  zeros + zeros *2}
zeros := code[i1];
end;
and I discover that zeros is code[i2] when it is added.
so  >
code[1]:=1;
code[2]:=3;
for i:=3 to 50 do
code:=code[i1] + code[i2];
zeros : longint;
when n = 1
there are only two possibilities '1' and '0'
for n = 2 we try to add '0' and '1' after them
(code[1] = 2 , zeros = 1(one number end with zero))
for number end with '1' , we can add '0' only
for '0' , we can add both '0' and '1'
so '10' , '01' , '00' ( total number = zeros * 2 + ones = 3
new zeros = code[1])
.........
we come up with the code
zeros:= 1;
code[1]:=2;
for i:=2 to 50 do begin
code := code[i1] + zeros;
{code:= code[i1]  zeros + zeros *2}
zeros := code[i1];
end;
and I discover that zeros is code[i2] when it is added.
so  >
code[1]:=1;
code[2]:=3;
for i:=3 to 50 do
code:=code[i1] + code[i2];
ALAN LEE

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Base Case:
T(1) = 2 (0) and (1)
T(2) = T( 1 ) ( This is adding a '1' to each of the string ) plus 1 ( Adding a '0' to the (1) string ) = 3
T(3) = T(2) (Again, adding '1' to each of the string) plus T(1) (This is the number of occurences where the last digit is not zero.
and so on...
I learnt this in my combinatorics class, and I took that a few years ago, so maybe someone can explain this better..
T(1) = 2 (0) and (1)
T(2) = T( 1 ) ( This is adding a '1' to each of the string ) plus 1 ( Adding a '0' to the (1) string ) = 3
T(3) = T(2) (Again, adding '1' to each of the string) plus T(1) (This is the number of occurences where the last digit is not zero.
and so on...
I learnt this in my combinatorics class, and I took that a few years ago, so maybe someone can explain this better..
thanx a lot guys,
I guess I'll just borrow a combinatorics book from someone and read through that  I'm just a freshman and combinatorics is next semester for me....
thanx again!
I guess I'll just borrow a combinatorics book from someone and read through that  I'm just a freshman and combinatorics is next semester for me....
thanx again!
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
In many cases recurence is involvwe with DP. I think, that of of this guys talking about recurences using it (with me too). If not  TLE must occur )) because computing >25 number in this problem is very timeconsuming ...
Dominik Michniewski
Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Hello Moni, ... I hope this can explain a little bit on why it is related to Fibonacci sequence, ...
We all know from problemstatement that we finally reduce the problem to finding the number of all binarystrings of length n that don't have consecutive ones.
Let f(n) = number of binarystrings of length n that don't have consecutive ones.
We can split f(n) by two smaller functions:
> f0(n) > finds the number of strings that start with '0'.
> f1(n) > finds the number of strings that start with '1'.
Let's consider f1(n) ... If the string starts with '1', clearly the next digit has to be '0'. So, the strings are fixed to "10????..."
Starting from s[2] until s[n1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n2) ...
f0(n) is even simpler. Since it starts with '0' ... the next digit can be either '0' or '1' ... So, the strings are only fixed to this pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as calculating f(n1).
Finally, we can see right away that f(n) = f(n2) + f(n1) ... which is Fibonacci sequence.
turuthok
We all know from problemstatement that we finally reduce the problem to finding the number of all binarystrings of length n that don't have consecutive ones.
Let f(n) = number of binarystrings of length n that don't have consecutive ones.
We can split f(n) by two smaller functions:
> f0(n) > finds the number of strings that start with '0'.
> f1(n) > finds the number of strings that start with '1'.
Let's consider f1(n) ... If the string starts with '1', clearly the next digit has to be '0'. So, the strings are fixed to "10????..."
Starting from s[2] until s[n1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n2) ...
f0(n) is even simpler. Since it starts with '0' ... the next digit can be either '0' or '1' ... So, the strings are only fixed to this pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as calculating f(n1).
Finally, we can see right away that f(n) = f(n2) + f(n1) ... which is Fibonacci sequence.
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10450
Hi,
I always got WA.
Is my output right?
Input:
9
0
2
10
9
13
50
51
47
49
Output:
0
3
81
60
175
10151
10777
8420
9550
Thanks.
I always got WA.
Is my output right?
Input:
9
0
2
10
9
13
50
51
47
49
Output:
0
3
81
60
175
10151
10777
8420
9550
Thanks.

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
RedScorpion, ... 51 is not a valid input ...
Here's the output of my solution (excluding 51):
turuthok
Here's the output of my solution (excluding 51):
Code: Select all
Scenario #1:
0
Scenario #2:
3
Scenario #3:
144
Scenario #4:
89
Scenario #5:
610
Scenario #6:
32951280099
Scenario #7:
7778742049
Scenario #8:
20365011074
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).