PB - Parking Bay
Luke Skywalker successfully leads the rebel starship fleet to break the Emperor's siege of the planet Endor. The rebels, jubilant in their victory, return to their base on the moon of Endor to pay their homage to Princess Leia. They fly towards the parking bay where there are n parking slots in a row. One by one n starships numbered S1 to Sn enter the parking bay. Each rebel Ri heads to his favorite parking slot Pi, and if it is free, he docks his starship there. Otherwise, he continues further to the next free slot and occupies it. But if all succeeding slots are occupied, he leaves for good. How many sequences Pi are such that every rebel can dock his starship?
Input Description
The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The description of each test case contains exactly one line (a positive integer), containing the value of n ≤ 1000000.
Output Description
The output consists of exactly t lines. The ith line should be Ai%10007, where Ai is the number of sequences in the ith case, and 'x%y' represents the remainder when x is divided by y.
Example
Input
2
1
2
Output
1
3
Explanation: In the given example, 11, 12 and 21 are the possible sequences.
hide comments
|
sherlock11:
2018-06-16 07:56:57
pen paper is basic requirement for solving this question............ |
|
ayushgupta1997:
2018-06-02 23:37:53
Explore about Parking Functions it's interesting! |
|
azam_9:
2016-07-04 11:51:52
use the formula ( (n+1)^(n-1) )%10007 and its done..happy coding..:P Last edit: 2016-07-04 11:52:05 |
|
aryan_r:
2016-06-27 14:58:50
Here is just one more test case in Order to understand it better :
|
|
unXled:
2012-07-15 11:39:08
anyone plz tell the answer for n=7 and n=1000000 |
|
Mahesh Chandra Sharma:
2010-05-06 08:58:12
@kalini he cant shift left, only right shifing is possible |
|
suteerth:
2010-04-06 19:51:27
By using the logic used for 11, I can then even say that 22 is a valid sequence where both wants 2, the first rebel will park at the leftmost 2 and the other will settle for the spot left, thus making the total count 4. |
|
|
suteerth:
2010-04-06 19:49:08
When it clearly says that Ri will want to park in the slot Pi, how can there be two slots marked 1. The slots have to be marked from 1 to n, and having slots of the same name invalidates what has been explained. |
|
Pavel Kazatsker:
2009-06-18 19:22:12
in example 2, there are two pilots; they can each choose place to park and the only fail condition is if they both choose the second slot. 11 means that they both want to park in the first slot |
|
manmeet:
2009-06-17 19:27:54
i am not clear what the problem means. what does sequence 11 in second example imply |
| Added by: | Kashyap KBR |
| Date: | 2006-10-10 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE |
| Resource: | Fair Isaac Programming Challenge - prelims 2006 |
RSS