Ссылка на оригинальную статью.
Задача:
Зима. 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 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import neko.Lib; /** * ... * @author Zavada Sergey */ class Main { static function main() { var n:Int = Std.parseInt(Sys.stdin().readLine()); var A:Array<Array<Int>> = [for (x in 0...n+1) [for (y in 0...2) 0]]; var count:Int =0; A[count][1] = 0; A[count][0] = -1; count++; var t = 0; var m = 0; var sum: Int = 0; for (i in 0...n) { var t:Int = Std.parseInt(Sys.stdin().readLine()); var m:Int = Std.parseInt(Sys.stdin().readLine()); if (m == 0) { A[count][1] = A[ A[t][0] ][1]; A[count][0] = A[ A[t][0] ][0]; } else { A[count][1] = A[t][1]+ m; A[count][0] = t; } sum+=A[count][1]; count++; } trace(sum); } } |
- e-olymp 974. Флойд-1 - 13.06.2017
- e-olymp 1872. Снеговики - 13.06.2017
- A155 - 13.05.2017