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.

А161

Задача: Даны натуральное число n, действительные числа [latex]a_{1},…,a_{n}[/latex], получить [latex]b_{1},…,b_{n}[/latex], где [latex]b_{i}= \frac{a_{i}}{1 + (a_{1} +… + a_{i})^{2}}[/latex], [latex]i = 1,…, n[/latex].

[latex]n[/latex] [latex]a[/latex] [latex]b[/latex]
7 1 2 3 4 5 6 7 0.500 0.200 0.081 0.040 0.022 0.014 0.009
10 4.5 3.1 6.7 1.1 8.9 4.32 1.45 5.1 4.5 8.1 0.212 0.053 0.033 0.005 0.015 0.005 0.002 0.004 0.003 0.004

Создаем цикл от i до заданного n. В нем каждый раз читаем [latex]a[/latex] и по формуле получаем [latex]b[/latex]. В конце цикла запоминаем [latex]a_{n}[/latex] для вычисления  суммы [latex]a_{1}+…+a_{i}[/latex]. Если цикл дошел до конца файла то прерываем его.

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

 

Ideone.

Ю3.7

Задача: Время обслуживания. Для каждого посетителя парикмахерской (с одним мастером) известны следующие величины: [latex]t[/latex] — момент его прихода и [latex]\tau[/latex] — продолжительность его обслуживания. Сколько клиентов обслужит мастер за смену продолжительностью [latex]T[/latex]? Сколько рабочего времени он потратит на обслуживание?

 [latex]T[/latex] t1 t2 k T1
600 200 210 500 550 50 300 10 50 4  410
600 50 100 200 498 550 30 50 200 10 40  5  330
 600 0 80 100 367 680 20 30 20 30 50  4 100

Используем цикл while, который останавливается при достижении конца файла (input). С начала проверяем пришел ли текущий клиент во время обслуживания предыдущего, если да, то обслуживание этого клиента начнется с момента окончания предыдущего. Потом проверяем не выходит ли момент прихода клиента и сумма времени прихода клиента и время его обслуживания за рамки смены парикмахера. После запоминаем текущие t1 (момент прихода клиента) и t2 (время обслуживания) в новые переменные, чтобы в последующем шаге цикла проверить первое условие. Считаем общее время обслуживание прибавляя на каждом шаге цикла t2. В каждом шаге цикла прибавляем к переменной k +1, что и будет количеством обслуженных клиентов.

Ideone.

Ю3.47

Задача: Для заданного [latex]\varepsilon[/latex] найти наименьшее [latex]n[/latex] такое, что [latex]\frac{2^{n}}{n!} <\varepsilon[/latex]. Вывести все члены последовательности от 1-го до [latex]n [/latex].

[latex]\varepsilon[/latex] Члены последовательности (t) [latex]n[/latex]
0.5 2.000; 2.000; 1.333; 0.667; 0.267; 5
5 2.000; 1
1.99 2.000; 2.000; 1.333; 3

В цикле проверяется больше ли t(член последовательности) чем [latex]\varepsilon[/latex]. Если да то, запускается цикл в котором высчитывается каждый член последовательности пока t не станет меньше [latex]\varepsilon[/latex]. Каждый последующий член последовательности считается на основе предыдущего, то есть член последовательности будет выглядеть как предыдущее значение умноженное на [latex]\frac{2}{n}[/latex]. Если же t меньше [latex]\varepsilon[/latex], то цикл выполняется всего один раз. Если [latex]\varepsilon[/latex] больше двух, то в последовательность будет содержать всего один элемент, так как  значение [latex]\frac{2^{n}}{n!}[/latex] при
[latex]n = 1[/latex] равно двум.

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

 

Ideone.

А52

Задача: Даны действительные числа [latex]a, b, c, d, s, t, u[/latex]( [latex]s[/latex] и [latex]t[/latex] одновременно не раны нулю). Известно, что точки [latex] (a, b) [/latex]и [latex] (c, d)[/latex] не лежат на прямой [latex] l[/latex], заданной уравнением [latex] sx+ty+u=0[/latex]. Прямая [latex] l[/latex] разбивает координатную плоскость на две полуплоскости . Выяснить, верно ли, что точки  [latex] (a, b)[/latex] и[latex] (c, d)[/latex] принадлежат разным полуплоскостям?

a b c d s t u
2 -1 3 4 5 3 -7 (a,b) или  (b,c) принадлежат прямой
6 -3  2 -5 2  3 1 (a,b) и (c,d) принадлежат разным полуплоскостям
0 7 3 6 4 9 1 (a,b) и (c,d) принадлежат одной полуплоскости

Если точка  [latex](a, b)[/latex] или [latex](c, d)[/latex] лежит на прямой [latex] l[/latex] то уравнение [latex] sx+ty+u=0[/latex] должно выполнятся при подстановке значений  [latex](a, b)[/latex] или [latex](c, d)[/latex] вместо [latex] x[/latex] и [latex] y[/latex]. Если точки лежат в одной полуплоскости то [latex] sa+tb+u[/latex] и [latex] sc+td+u[/latex] — должны быть числами одного знака, в противном случае точки лежат в разных полуплоскостях.

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

 

Ю2.24

Задача: На шахматной доске стоят черный король и три белые ладьи (ладья бьет по горизонтали и вертикали). Проверить, не находится ли король под боем, а если есть угроза, то от кого именно.

x y x1 y1 x2 y2 x3 y3
3 6 1 1 3 7 2 5 Угроза от второй ладьи
1 2 7 8 4 6 3 6 Угрозы нет
1 2 5 4 3 7 1 2 Ошибка

Введем координаты каждой фигуры на шахматной доске от 1 до 8 (использовать отрицательные или дробные числа не имеет смысла). Проверим совпадает ли хотя бы один из координат короля с координатой хотя бы одной ладьи. Если, да то выводим соответствующее сообщение, если нет то выведем, что угрозы нет.

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

 

Ю1.21

Задача: Владелец автомобиля приобрел новый карбюратор, который экономит 50% топлива, новую систему зажигания, которая экономит 30% топлива, и поршневые кольца, экономящие 20% топлива. Верно ли, что его автомобиль теперь сможет обходиться совсем без топлива? Найти фактическую экономию для произвольно заданных сэкономленных процентов.

e1 e2 e3 f
50 30 20 72 Пройдено.
10 34 72 83.37 Пройдено.
0 0 0 0.00 Пройдено.
23.7 47.1 10.2 63.72 Пройдено.

 

Нет, машина не будет обходится совсем без топлива.

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

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