Задача:
Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).
В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:
- либо добавляет ему сверху один шар;
- либо удаляет из него верхний шар (если снеговик не пустой).
Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.
Входные данные
Первая строка содержит количество действий n (1 ≤ n ≤ 200000). В строке номер i+1 содержится описание действия:
- t m — клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);
- t 0 — клонировать снеговика номер t (0 ≤ t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.
В результате действия i, описанного в строке i+1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.
Все числа во входном файле целые.
Выходные данные
Выведите суммарную массу построенных снеговиков.
Решение: Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2]. Указываем значение первого элемента равное 0 и нулевого элемента равного -1, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна 0, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно 0, то мы клонируем снеговика и добавляем ему шар массой m. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.
Задача на e-olymp.
Код:
|
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 |
#include <cstdlib> #include <iostream> using namespace std; int main() { int n; cin >> n; int a[n+1][2]; int count=0; a[count][1] = 0; a[count][0] = -1; count++; int t, m; long long sumr=0; for( int i=0 ; i<n ; i++ ){ cin >> t >> m; 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; } sumr+=a[count][1]; count++; } cout << sumr << endl; } |
Тесты:
| 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 |
Хорошо, только добавьте ключевые слова (метки) и ссылки на задачу.