OAE - OAE
Having joined forces and preparing for the war with the terminators the humans do know that it will be a tough battle. They plan to strike each base of the terminator and destroy them one by one. A genius computer engineer UD willing to extend his help to his fellow humans found out that each base of the terminator has password protected doors. He was able to recognise the pattern between the passwords. The password is an n character string having even number of zeroes. As you know many strings of this type exist. Help him to find out the total number of such strings. Each character in the password string is a digit from 0 to 9.
Input
The first line of input contains an integer t <= 50, the number of test cases. Then t test cases follow each containing a line with a single integer n (1 <= n <= 106).
Output
A single line for each test case, containing the answer modulo 314159.
Example
Input: 2 2 1 Output: 82 9
hide comments
|
ash_demon8:
2018-05-12 18:44:19
exactly...the problem could be done in O(n)... use of basic combinatorics:) |
|
minhthai:
2016-03-01 15:53:13
I was so naive :) nice problem! |
|
Sudarshan K:
2015-01-07 18:03:59
Take care while taking modulo. You will understand only after realizing your mistake. :) |
|
deCodeIt:
2014-09-18 10:55:40
Applied some simple probability and... voila... complexity is of order O(max)
|
|
:(){ :|: & };::
2014-06-26 03:25:21
Solvable with a single line of python. |
|
Ravi Kiran:
2011-03-17 15:47:54
@RadhaKrishnan
|
|
:D:
2011-02-12 13:42:20
When you have a answer modulo some integer M, range to M^2 should be sufficient most of the time. Last edit: 2011-02-12 13:47:59 |
|
Ahmed Sherif:
2011-02-12 13:23:16
Does it need A Bignum algo or just Modulo while summing is enough ?? |
|
|
:D:
2011-02-12 13:15:55
First example: all strings in range "00"-"99" except "01","02",..,"09" and "10","20",...,"90" (zero is an even number). |
| Added by: | Troika::Bytes |
| Date: | 2010-02-18 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: PERL6 |
RSS