e-olymp 1872. Снеговики

Ссылка на оригинальную статью.

Задача:

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

  • либо добавляет ему сверху один шар;
  • либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

Входные данные:

Первая строка содержит количество действий [latex] n (1 ≤ n ≤ 200000).[/latex] В строке номер [latex]i+1[/latex]содержится описание действия:

  • [latex]t[/latex] [latex]m[/latex]— клонировать снеговика номер [latex] t (0 ≤ t < i) [/latex] и добавить сверху шар массой [latex]m (0 < m ≤ 1000)[/latex];
  • [latex]t[/latex] [latex]0[/latex] — клонировать снеговика номер [latex]t (0 ≤ t < i)[/latex] и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия [latex]i[/latex], описанного в строке [latex]i+1 [/latex] создается снеговик номер [latex]i [/latex]. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

Выходные данные:

Выведите суммарную массу построенных снеговиков.

Решение: 

Считываем [latex]n[/latex] — количество действий. Задаем двухмерный массив размером [latex] [n+1][2] [/latex]. Указываем значение первого элемента равное [latex]0 [/latex] и нулевого элемента равного [latex]-1 [/latex], чтобы он ни на что не ссылался в начале.  В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна [latex]0 [/latex], то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно [latex]0[/latex], то мы клонируем снеговика и добавляем ему шар массой [latex]m [/latex]. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Тесты:

Input Output
8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
74
4
0 3
1 2
2 1
1 1
18

 

Код программы:

Сергей Завада

Сергей Завада

Студент кафедры математического обеспечения компьютерных систем Одесского национального университета имени И. И. Мечникова
Сергей Завада

Latest posts by Сергей Завада (see all)

Добавить комментарий