Задача

Зима. 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$. Изначально имеется пустой снеговик с номером ноль.

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

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

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

Тесты

Входные данные	Выходные данные
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
2 0 1 1 5	7
5 1 2 3 4 5 5 1 7 5 6	26

Код задачи

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), count = 0, t, m;
		int a[][] = new int[n + 1][2];
		a[count][1] = 0;
		a[count][0] = -1;
		count++;
		long sumr = 0;
		for(int i = 0; i < n; i++){
			t = in.nextInt();
			m = in.nextInt();
			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++;
		}
		System.out.println(sumr);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), count = 0, t, m;

int a[][] = new int[n + 1][2];

a[count][1] = 0;

a[count][0] = -1;

count++;

long sumr = 0;

for(int i = 0; i < n; i++){

t = in.nextInt();

m = in.nextInt();

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++;

}

System.out.println(sumr);

}

Решение задачи

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

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

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