2589. Мытье посуды

Бесси и Канму объединяются, чтобы вымыть огромную кучу из n (1 ≤ n ≤ 10000) грязных тарелок после Коровье-Лосиного Фестиваля. Бесси будет мыть тарелки, а Канму вытирать.

Каждая тарелка имеет уникальный номер в промежутке 1..n. Сначала все тарелки сложены в стопку друг на друга так, что сверху находится тарелка номер 1, а снизу тарелка с номером n.

Сначала Бесcи моет D_i тарелок: берет их по одной из входной стопки, моет и складывает в стопку на другой части раковины (вымытые тарелки изменяют свой порядок расположения на противоположный).

Как только Бесси заканчивает мыть тарелки, она либо берет следующую партию тарелок на мойку, либо Канму приходит вытирать D_i тарелок, пока Бесси съедает свой заслуженный пирожок. Он берет тарелки одну за одной со стопки, оставленной ему Бесси, вытирает их, и снова складывает в стопку (переворачивая ее в обратном порядке) уже чистых тарелок.

Потом Канму либо снова берет следующую партию тарелок для вытирания, либо уходит съесть булочку в то время как Бесси возвращается мыть посуду. Описанные операции повторяются пока все тарелки не будут вымыты и вытерты.

Вам следует найти порядок, в котором будут расположены вымытые тарелки (сверху до низу) в конечной стопке.

Рассмотрим пример, в котором Бесси следует вымыть стопку из 5 тарелок:

D₁ равно 3, поэтому Бесси берет три тарелки сверху стопки, одна за другой, моет их, и складывает с другой стороны раковины для Канму:

Канму вытирает две из них, одну за другой, и кладет их в стек чистых тарелок:

Бесси моет оставшиеся две тарелки:

Наконец Канму вытирает последние три тарелки, складывая их следующим образом:

Конечным порядком будет: 1, 4, 5, 2, 3.

Каждая из входных строк содержит C_i (1 ≤ C_i ≤ 2), где 1 указывает на то что Бесси следует мыть, а 2 на то что Канму должен вытирать, а также количество тарелок D_i (1 ≤ D_i ≤ n) которое следует вымыть или вытереть.

Вход. Первая строка содержит количество тарелок n, которые следует вымыть. Начиная со второй, каждая строка содержит два числа C_i и D_i.

Выход. Вывести n строк: i-ая строка содержит номер i-ой вымытой тарелки, считая сверху.

Пример входа	Пример выхода
5 1 3 2 2 1 2 2 3	1 4 5 2 3

РЕШЕНИЕ

стек

Анализ алгоритма

Объявим три стека: грязных, вымытых и вытертых тарелок. Далее моделируем работу стеков, обрабатывая запросы на мытье и вытирание тарелок.

Реализация алгоритма

Объявим три стека: грязных, вымытых и вытертых тарелок.

stack<int> dirty, washed, cleaned;

Читаем количество тарелок n. Инициализируем стек грязных тарелок: заносим в него числа от n до 1.

scanf("%d", &n);

for (i = n; i >= 1; i--) dirty.push(i);

Читаем команду.

while (scanf("%d %d", &code, &x) == 2)

{

Бесси следует мыть x тарелок.

if (code == 1)

{

for (i = 0; i < x; i++)

{

Перемещаем x тарелок из стека грязных в стек вымытых тарелок.

washed.push(dirty.top());

dirty.pop();

}

}

Канму должен вытирать x тарелок.

else

{

Перемещаем x тарелок из стека вымытых в стек вытертых тарелок.

for (i = 0; i < x; i++)

{

cleaned.push(washed.top());

washed.pop();

}

}

}

Выводим ответ – последовательность номеров чистых тарелок.

while (!cleaned.empty())

{

printf("%d\n", cleaned.top());

cleaned.pop();

}

Java реализация

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 реализация

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());