BogosortProblem code: BOGOSORT |
All submissions for this problem are available.
Recently Johnny have learned bogosort sorting algorithm. He thought that it is too ineffective. So he decided to improve it. As you may know this algorithm shuffles the sequence randomly until it is sorted. Johnny decided that we don't need to shuffle the whole sequence every time. If after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle Johnny gets (1, 2, 5, 4, 3, 6) he will fix 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Johnny hopes that this optimization will significantly improve the algorithm. Help him calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.
Input
The first line of input file is number t - the number of test cases. Each of the following t lines hold single number n - the number of elements in the sequence.
Constraints
1 <= t <= 150
2 <= n <= 150
Output
For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions.
Example
Input: 3 2 6 10 Output: 2 1826/189 877318/35343
| Author: | spooky |
| Date Added: | 6-08-2010 |
| Time Limit: | 2 sec |
| Source Limit: | 10000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, 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
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
@admin he will fix 4 also
for n=2 shuffles=1 but here
for n=2
shuffles=1
but here it says 2 help!!
The question isn't very well
The question isn't very well worded, but when it talks about first/last elements, a number is only fixed if every number before it is also correct, or every number after it is correct. Not the case with the 4.
Half the time shuffling (2,1) you will get (2,1), so the answer certainly isn't 1.
I could not understand the
@admin please any help??
I could not understand the
what is the shuffling
can anyone explain more bout
admin please explain input
Could some one solve it with
could anyone please explain
@admins Please clarify the