GSWORDS - Counting Words
Supervin likes counting. In this problem, he invites you to count together.
Supervin defines a word as "a string only consist of 'o' or 'x'", and additional requirement, for each substring with prime-length, the number of 'o' is not less than the number of 'x'.
Supervin gives you an integer N (1 <= N <= 10^12). Supervin challenges you to determine how many words can be made with exactly N-length.
You are having difficulties, make a program to determine how many N-length words. Because the output can be too big, output the number of words modulo 1 000 000 007.
Input
One line, an integer N
Output
One line, an integer indicates how many N-length words modulo 1 000 000 007
Example
Input: 2 Output: 3
Input: 3 Output: 4
Explanation
In the first sample, the words can be made are: "oo", "ox", "xo".
In the second sample, the words can be made are: "ooo", "oox", "oxo", "xoo"
hide comments
|
rashigupta16:
2017-02-03 21:39:13
Great problem :) |
|
mukesh227:
2015-10-30 21:25:08
finally AC!!!Hurrry!!!! |
|
:.Mohib.::
2015-01-16 11:15:17
Can anybody plzz provide some testcases???
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-08-06 10:26:59
@Jonathan Irvin Gunawan: Good luck, IOI 2012 at Sirmione, Italia. I know you're great programmer ;) hope you win the gold medal. "Lakukan yang terbaik untuk Indonesia" :D |
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-08-06 10:26:59
@Jonathan Irvin Gunawan: I agree with Mitch Schwartz, upload multiple test cases on single file allow you to add thousand of test cases and make the judge faster. Btw, Nice problem "Problem yang keren". Google +1 for your problem ;) |
|
Mitch Schwartz:
2012-08-06 10:26:59
It seems better to me to have many test cases per input file (and maybe 1-4 input files), rather than ~50 separate input files each with just one test case. This is not only logistically easier but also easier on SPOJ servers. For example, if somebody tries an algorithm that will get TLE, right now it would use ~50 seconds of server time, because the way the judge works is to run the program against EVERY input file and only afterward report according to success or the first failure. Additionally, a Java submission would use close to 0.3 seconds for each test case just to start up the virtual machine. Also it makes users wait a little longer to see the result of their submission, although this is a smaller concern. |
| Added by: | jonathanirvings |
| Date: | 2012-08-06 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Jonathan Irvin Gunawan, used in TOKI OpenContest March 2012 |
RSS