Magic sequenceProblem code: F5 |
All submissions for this problem are available.
Johnny has invented a magic sequence. Each element of the sequence is defined by the same recursive definition - take some linear combination of previous elements (whose coefficients are fixed) and add to them the n-th powers of some integers. Formally: Xn = Xn-1*a1 + ... + Xn-i*ai + b1*d1n + ... + bj*djn, for some integer constants p,q,a1,...,ap,b1,..., bq,d1,..., dq. Of course, as the values can quickly grow, he computed them modulo a fixed value: 106. He wrote many consecutive values of the sequence, but then he lost most of his work. All he has now, is 10 consecutive values taken from somewhere in the sequence (he doesn't know at what n they begin), and the recursive rule. And he would like to recover the sequence, or at the very least, to be able to write the next 10 values taken from the sequence.
Input
First, two integers, 0 p 4, 0 q 4. Then come the descriptions of the coefficients, -100 a1,...,ap,b1,..., bq,d1,..., dq 100. Then, the following 10 integers are Xn,Xn+1,...,Xn+9 for some unknown n.
Output
Output 10 integers - Xn+10,Xn+11,...,Xn+19
Example
Input:
1 1
1
1
1
11 12 13 14 15 16 17 18 19 20
Output:
21 22 23 24 25 26 27 28 29 30
Explanation:
xn=xn-1+1
Input:
1 1
1
1
2
1 3 7 15 31 63 127 255 511 1023
Output:
2047 4095 8191 16383 32767 65535 131071 262143 524287 48575
Explanation:
xn=xn-1+2n=...=2n+2n-1+...+1=2n+1-1
Input:
2 0
1 1
1 1 2 3 5 8 13 21 34 55
Output:
89 144 233 377 610 987 1597 2584 4181 6765
Explanation:
xn=Fib(n) is the n-th Fibonacci number
Input:
2 1
2 -1
2
1
0 1 4 9 16 25 36 49 64 81
Output:
100 121 144 169 196 225 256 289 324 361
Explanation:
xn=n2
| Author: | admin |
| Date Added: | 10-07-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Hi ppl!! I am gettin WA for this problem. I think the algo is right . Can someone verify o/p for this test case:
Input:
2 1
2 -1
2
1
20001 40004 60009 80016 100025 120036 140049 160064 180081 200100
My Output:
220121 240144 260169 280196 300225 320256 340289 360324 380361 400400
You aren't supposed to ask for output verification during the contest: http://blog.codechef.com/2009/07/29/rule-change-for-august-contest-guide...
oh!!i m very sorry!! I did'nt know!!!
In the Problem.. Does this "ap" represents a subscript p
@rahul Yes
the recursive definition is applicable for n>?. and is i=p and j=q?
Applicable for all n. Your second question doesn't make much sense.
It does make sense actually; and yes, i should be replaced by p and j by q in the problem statement. (The ... shows the indices go from 1 to p, you don't need the extra variable i).
I had the same doubt as dot-dot-dot's second question (whether i and j could really be less than p and q, and were some independent unknowns), but I was reluctant to ask lest it should be taken as a violation of the rules. Thanks to Stephen Merriman for the clarification.
What is the result of a negative number modulo 10^6 in this problem? For example, what is the result of -(10^6 1) modulo 10^6? 999999 or -1?
@susam By definition of modular arithmetic, there is only one correct answer to your question.
Input is included 10 integers are Xn,Xn 1,...,Xn 9 for some unknown n.
What is the value of n. In example there is no input of n.
2nd example is wrong! It misguides.
@admin
i) Can p=q=0, in any test case. In that case sequence is not defined, do we have entries for the 10 elements of the sequence?
ii) are values of a, b, d on "different lines" for non null entries?
I am getting NZEC when trying to read input, when i catch number-format-exception, there is no NZEC.
No p and q both won't equal 0 in a test case. The entries for 'a' will be space separated integers on one line. Same for the entries related to 'b', 'd' and the 10 numbers.
@Suvendu Samanta
You're wrong. sentence X_n = 2^n should be quantified:
forall_n X_n = 2^n
It's typicall that all free variables in mathematicall sentence are closed by universall quantifier. So this *n* is different *n* that appears in problem statement. Learn about variables range...
@admin
There seems conclusive evidence to suggest that the input is not the type you have mentioned.
In particular if i catch number format exception , there is no NZEC
while if i dont catch any exceptions wile reading input that, there is NZEC (runtime error)
Note that my processing logic are all in try catch blocks hence a NZEC cant arise out of that.
the only place which i can possibly get NZEC is while reading input, and which will happen when the input is not the right format as suggested
By definition of modular arithmetic, all answer have to be positive, correct? and Xn,Xn 1,...,Xn 9 (given) are guaranteed to be positive?
@piyush Try now.
@admin
Thanks, it worked now!
I tried 73 submissions, may be I should have contacted you admins earlier :-) . Besides i was wondering why this should be a java specific error, cause correct submissions in C/C and other languages kept on coming.
@Eric
quick checking inputs... yep, they are guaranteed
in the final example, ai is given as 2-1, could some one please explain?
@admin : Are there test cases where the 10 input values are also written modulo 10...................as they were larger than 1000000
@sharad All input values are less than 10^6
@admin: No I mean, is it possible that according to the recursive definition some of the input values might be having more than 6 digits but after computing modulo only last 6 digits are written........
Like, one of the input values according to actual definition is 12345678 but it is given 345678 in input....
Is it possible ??
Yes.
how can same program submission result in "Wrong Answer" which ran for 0.01 seconds and next submission gives "Time Limit Exceeded" ?
If something of that sort has happened, mail us the submission ids.
How is the first term calculated? What will be Xn-1 in that case? What will be the first term if q=0?
@Admin: My submission ids which are 67097 and 67099
You don't need to calculate the 0th term. You will be given 10 numbers and you have to calculate the 'next' 10 integers in the sequence.
@ankit your submissions are not the same. Check line 318. In one submission you are printing one value and in the other submission you are printing some other value.
@Admin: what's wrong with my submission id 67774? It worked well in my system.
@anoop Sorry, we cannot look at individual submissions and tell you what is wrong while the contest is going on.