| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11510 | Can a Permutation Be Sorted By a Stack |
|
| 11845 | Josephus_0 |
|
Description
Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either
(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or
(iii) pop from the stack, and output that number.
Can we obtain the output sequence as 1, 2, 3, ..., n.
So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.
Hint:
Our strategy could be as follows.
First, we try operation (iii).
If it is invalid, then we try operation (i).
If it cannot produce what we want, try operation (ii).
If we run out of the supply and the stack is not empty. The answer is NO.
Input
There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).
Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000
Output
For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Based on the original Josephus Problem introduced in class, an additional rule of this problem is to change
direction of counting after killing a person.
For example, there are 8 people, numbered 1 to 8, in a circle and arranged in clockwise.
The step to kill in each round is incrementing by 1 and starting from 2 steps.
Here's the example:
1, 2 (kill 2, change the direction to counter-clockwise)
1, 8, 7 (kill 7, change the direction to clockwise)
8, 1, 3, 4 (kill 4, change the direction to counter-clockwise)
3, 1, 8, 6, 5 (kill 5, change the direction to clockwise)
6, 8, 1, 3, 6, 8 (kill 8, change the direction to clockwise)
6, 3, 1, 6, 3, 1, 6 (kill 6, change the direction to counter-clockwise)
1, 3, 1, 3, 1, 3, 1, 3 (kill 3, change the direction to clockwise)
So the person numbered 1 is the survivor.
You're asked to solve this problem using circular linked list.
You will be provided with main.c and function.h, and you need to implement function.c.
Notice: There are several testcases with time limits.
Input
Multiple lines with each line representing the length of the sequence
Output
Each line represents the survivor number.