My Fair Coins
All submissions for this problem are available.
There are coins of 2 different denominations in Crazyland, 1-cent coins and 2-cent coins. As all the coins do, even these coins have two faces, i.e. heads and tails.
Your task is to find out the the number of ways to create a linear arrangement of these coins so that their sum is N cents. The only condition on the linear arrangement is that
the first coin in the arrangement should always face heads. All other coins could either face head or face tail.
Take N = 2 as an example. The possible arrangements are (1H, 1H), (2H), (1H, 1T), where H is heads and T is tails.
Therefore there are 3 possible arrangements that sum up to 2-cents.
While counting make sure that you count heads and tails as different.
First line contains T, the number of cases.
T lines follow, each containing a single number N, the required sum.
0 <= T <= 10000
1 <= N <= 1000000000
For each case the output should be a single integer representing the number of such arrangements possible. As this can be very large print it modulo 1000000007.
3 1 2 3
1 3 8
|Tags||easy, july12, kaushik_iska, matrix-expo, recurrence|
|Time Limit:||0.314214 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.