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

Задача: 

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

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

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

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

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

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

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

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

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

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

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

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

Задача на e-olymp.

 

Код:

 

Тесты:

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

А704

Задача: Даны квадратные матрицы A, B и C порядка n. Получить матрицу (A+B)C.

Решение: В первом цикле читаем матрицу A. Во втором цикле читаем матрицу B и сразу прибавляем ее к матрице A, получаем сумму матриц. В третьем цикле умножаем сумму матриц A и B на матрицу C и выводим результат.

Код:

 

Тесты:

n A B C Output
3 1 2 3
4 5 6
7 8 9
0 1 0
0 0 0
0 0 0
1 0 0
0 1 0
0 0 1
1 3 3
4 5 6
7 8 9
2 4 6
12 7
3 2
1 1
7 3
2 8
65 85
107 103
3 3 4 1
1 2 1
5 6 7
1 3 1
2 4 5
6 5 1
1 1 0
5 8 1
2 3 2
43 66 11
45 69 18
82 123 27

AA7

Задача: В заданной строке вставить перед каждым символом «-» символ «+».

Решение: В цикле просматриваем строку x, если находим символ «-», то увеличиваем счетчик. Создаем строку длинной старой строки плюс счетчик. Во втором цикле, если символ не равен «-», то записываем его в новую строку, иначе вставляем «+», а после него «-».

Код:

Тесты:

Строка Результат

ef34_ve-ev-++vev)-

ef34_ve+-ev+-++vev)+-

3-5=8-10+0

3+-5=8+-10+0

Ю12.20

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

Ввод Вывод
qwerty
ytrewq
av
ab
va
tg
qwerty — ytrewq
av — va
12345
45
67
54
123567
543
54321
12345 — 54321
45 — 54

 

 

Записываем каждое слово словаря в вектор. А цикле переворачиваем каждое слово вектора и потом в цикле сравниваем его с каждым словом в словаре, если найдено обратное слово, то закидываем пару слов в новый вектор. Выводим вектор из пар слов на экран.

Ideone.

А412в

Задача: Даны две целочисленные квадратные матрицы порядка 6. Найти последовательность из нулей и единиц [latex]b_{1},\ldots,b_{6}[/latex] такую, что [latex]b_{i}=1[/latex], когда:

в)[latex]i[/latex]-e строки первой и второй матриц содержат вместе не более трех положительных элементов;

Первая матрица Вторая матрица [latex]b_{1},\ldots,b_{6}[/latex]
2 4 5 -1 -2 -3
-1 -2 -3 1 -3 -2
2 4 5 -1 -2 -3
2 4 5 -1 -2 -3
-1 -2 -3 1 -3 -2
2 4 5 -1 -2 -3
2 4 5 -1 -2 -3
-1 -2 -3 1 -3 -2
2 4 5 -1 -2 -3
2 4 5 -1 -2 -3
-1 -2 -3 1 -3 -2
2 4 5 -1 -2 -3
010010
8 5 -2 -4 -2 -1
-1 -2 0 1 0 2
11 -4 6 0 0 -3
1 3 -5 0 2 -3
-11 0 -3 1 -3 -2
1 -4 4 0 0 0
0 0 0 0 0 0
-7 -4 -5 1 -4 -2
2 -4 0 -1 -2 -3
3 1 -5 9 -6 -7
-1 -2 -3 0 -3 2
2 4 5 5 7 8
111010

 

Вводим две матрицы 6×6. Создаем одномерный массив с шестью элементами. В цикле просматриваем одновременно обе строки каждого массива и если находим положительный элемент то увеличиваем счетчик на один. Проверяем значение счетчика, если оно меньше трех, то в одномерный массив записываем 1, если больше, то 0.

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

 

Ideone.

Ю4.25

Задача: Заполнить матрицу заданного размера [latex]M(k,l)[/latex] числами 1,2,3,4 так, чтобы по горизонтали, вертикали и диагонали не было одинаковых рядом стоящих чисел.

[latex]k[/latex] [latex]l[/latex] Output
6 6 1 2 3 4 1 2
3 4 1 2 3 4
1 2 3 4 1 2
3 4 1 2 3 4
1 2 3 4 1 2
3 4 1 2 3 4
5 5 1 2 3 4 1
3 4 1 2 3
1 2 3 4 1
3 4 1 2 3
1 2 3 4 1
Код на Ideone.

Заполняем массив с помощью формулы (j + 2 * (i % 2)) % 4 + 1. При i четном 2 * (i % 2) будет обращаться в 0. То есть в нечетных строках будут числа 1, 2, 3, 4 подряд, а в четных строках будут меняться цифры 1 на 3, 2 на 4, 3 на 1, 4 на 2.

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

Код на Ideone.