2589. Cleaning the dishes
Bessie and Canmuu
are teaming up to wash the massive pile of n
(1 ≤ n ≤ 10000) dirty dishes
left over after the CowMoose Festival. Bessie is washing the dishes; Canmuu will
dry them.
Each dish has a
unique serial number in the range 1..n.
At the beginning, the dishes are stacked in order with 1 on the top
and n on the bottom.
Bessie first
washes some number of dishes Di by
taking one from the top of the incoming pile, washing it, and then stacking it
on the other side of the sink (this reverses the order of those dishes).
Once she has
finished washing those dishes, either she washes another set of dishes or
Canmuu comes back to dry Di
dishes while Bessie goes off to eat her well-earned snack. He takes those
dishes, one by one, off the stack that Bessie left him, dries the dish, and
stacks it (again in reverse order) in the cleaned stack.
Canmuu then
either takes another set of dishes to dry or goes off to get a snack while
Bessie comes back to wash. They repeat these operations until all of the dishes are washed and dried.
What is the final
order (top to bottom) in which the clean, dry dishes are stacked?
To illustrate,
suppose that Bessie has a stack of 5 dishes to wash:
D1 is 3,
so Bessie takes three dishes from the top of the stack, one by one,
washes them, and stacks on the other side of the sink for Canmuu to dry:
Canmuu dries two of these, one by one, and
place them onto the clean stack:
Bessie washes the
final two dishes:
Finally, Canmuu
dries the last three dishes, stacking them in the resulting order below:
So the final order
is: 1, 4, 5, 2, 3.
Each of the main
input lines contains both a command, Ci (1
≤ Ci ≤ 2)
where 1 indicates Bessie washing while 2 indicates Canmuu drying, and
the number of dishes Di (1
≤ Di ≤ n) to be washed or dried.
Input. First line contains n – the number of dishes to wash
and dry.
Starting from the
second, each line contains a command and a count of dishes to process: Ci and Di.
Output. Print n lines: i-th line contains the i-th cleaned
dish, starting from the top.
|
Sample input |
Sample output |
|
5 1 3 2 2 1 2 2 3 |
1 4 5 2 3 |
SOLUTION
stack
Algorithm analysis
Declare three
stacks: dirty, washed and wiped dishes. Thrn simulate the stacks, processing requests for washing
and wiping dishes.
Algorithm realization
Declare three
stacks: dirty, washed and wiped dishes.
stack<int> dirty, washed, cleaned;
Read the number of plates n. Initialize
the stack of dirty dishes: put numbers from n
to 1 into it.
scanf("%d", &n);
for (i = n; i >= 1; i--) dirty.push(i);
Read the command.
while (scanf("%d
%d", &code, &x) == 2)
{
Bessie should wash x plates.
if (code == 1)
{
for (i = 0; i < x; i++)
{
Move x plates from the dirty
stack to the washed stack.
washed.push(dirty.top());
dirty.pop();
}
}
Kanmu must wipe x plates.
else
{
Move x plates from the washed
stack to the wiped stack.
for (i = 0; i < x; i++)
{
cleaned.push(washed.top());
washed.pop();
}
}
}
Print the answer – a sequence of numbers of clean plates.
while (!cleaned.empty())
{
printf("%d\n", cleaned.top());
cleaned.pop();
}
Java
realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Stack<Integer> dirty = new
Stack<Integer>();
Stack<Integer> washed = new
Stack<Integer>();
Stack<Integer> cleaned = new Stack<Integer>();
for(int i = n; i >= 1; i--) dirty.push(i);
while(con.hasNext())
{
int code = con.nextInt();
int x = con.nextInt();
if (code == 1)
{
for(int i = 0; i < x; i++)
washed.push(dirty.pop());
}
else
{
for(int i = 0; i < x; i++)
cleaned.push(washed.pop());
}
}
while(!cleaned.empty())
System.out.println(cleaned.pop());
con.close();
}
}
Python realization
import
sys
dirty
= []
washed
= []
cleaned
= []
n = int(input())
for i in range(n, 0, -1): dirty.append(i)
for s in sys.stdin:
code, x = map(int,s.split())
if (code == 1):
for i in range(x):
washed.append(dirty.pop());
else:
for i in range(x):
cleaned.append(washed.pop());
while(cleaned):
print(cleaned.pop());