Description

Given a sequence of well-formed parentheses that consists only of '(' and
')', our target is to output, for each of the closing parentheses that we
scan from left to right, the location of the corresponding open parenthesis.

Remark: We will include some very long sequences of parentheses as our
test cases. If your program cannot pass all the test cases, the most
common reasons are either it contains bugs, or it does not run in linear
time.

Input

There are many cases in the input.
For each case, it is one line with legal brackets.
Input will end with EOF.

1407: length <= 30
1408: length <= 2000
1409: length <= 40000

Output

For each case, output the closing parentheses that we scan from left to right, the location of the corresponding open parenthesis.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given n persons, labeled by 1, 2, 3, ..., n in a circle, each surviving
person takes turn to kill some person, until only one person survives. The
rule is similar to the Josephus problem, where player 1 starts the
killing. The difference is that in the i-th turn, a player kills the i-th
person in front of him/her in the circle (where such a person could be
himself/herself). Also, after each killing, the one immediately after the
person being killed starts the killing in the next round. Our target is,
given the input n, output the label of the survivor.

 

Example:

Suppose n = 5. Beginning: 1 2 3 4 5 (in the circle)
Round 1: 1 3 4 5 (1 kills 2)
Round 2: 1 3 4 (3 kills 5)
Round 3: 3 4 (1 kills 1)
Round 4: 4 (3 kills 3)
==> Output 4 as the survivor.

Suppose n = 6. Beginning: 1 2 3 4 5 6 (in the circle)
Round 1: 1 3 4 5 6 (1 kills 2)
Round 2: 1 3 4 6 (3 kills 5)
Round 3: 1 3 6 (6 kills 4)
Round 4: 3 6 (6 kills 1)
Round 5: 3 (3 kills 6)
==> Output 3 as the survivor.

Input

There are many cases in the input.
For each case, it is one line with n.
Input will end with EOF.

1410: n <= 30
1411: n <= 1000
1412: n <= 4000

 

Output

For each case , output the label of the survivor.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Implement a queue of numbers that supports the following operations:

1. print: print the content of the queue, from beginning to end
(use # to specify the end of queue)
2. enqueue: add a number at the end of the queue
3. dequeue: remove a number from the front of the queue
4. delete-mid: remove the item in the middle of the queue, if the
queue has odd number of items. Otherwise, remove the
two items in the middle of the queue if the queue has
even number of items.
(Do nothing when the queue is empty)

Assuming we start with an empty queue, our target is to perform a sequence
of operations specified by the input

Case 1: operations <= 50
Case 2: operations <= 1500
Case 3: operations <= 10000

Input

Each line contains one operation. The input is terminated by end of file. (EOF)

Example Input 1: 

enqueue 1
enqueue 2
print

 

Example Input 2: 

enqueue 1
enqueue 2
enqueue 5
enqueue 4
enqueue 3
delete-mid
print

Example Input 3: 

enqueue 1
enqueue 2
enqueue 5
enqueue 4
enqueue 3
dequeue
delete-mid
print

Example Input 4: 

enqueue 1
enqueue 2
enqueue 5
enqueue 4
enqueue 3
dequeue
dequeue
dequeue
delete-mid
print

Output

For each print operation, print the content of the queue, from beginning to end. Use # to specify the end of queue. Each number and # should be separated by a blank. Note that there is no blank after #. See the Sample Output below.

Example Output 1:

1 2 #

Example Output 2:

1 2 4 3 #

Example Output 3:

2 3 #

Example Output 4:

#

Sample Input  Download

Sample Output  Download

Tags

Discuss