e-olymp 4475. Часы

Задача

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

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

Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:

  • $S, M, H ≤ 60$;
  • $S+M+H-2≤K≤1000$

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

Выходной файл должен содержать в единственной строке вычисленное Вашей программой количество суток.

Тесты

Входные данные Выходные данные
$5$ $12$ $12$ $30$ $380$
$7$ $10$ $40$ $70$ $5610$
$60$ $60$ $60$ $500$ $4560840$
$60$ $30$ $5$ $1000$ $4970$

Код программы

Алгоритм решения

  1. Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
  2. Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
    $\begin{pmatrix}
    1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
    1& 5& 8& 2& 4& 3& 7& 7& 6& 10
    \end{pmatrix}$
  3. Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Примечание

Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 2892. Сумма значений

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные Выходные данные
$3$ $7.833333333333333$
$1 \ 2 \ 3$
$2$ $0$
$1 \ -1$
$5$ $4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$ $10.1$
$10$

Код программы

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

Мы просто суммируем значения функции в каждой точке. Тут использовали класс BigDecimal для точек и значений функции для более высокой точности.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 161. Роботы

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

Составьте программу, которая по заданному набору роботов обоих типов определяет, за какое минимальное время они смогут обработать определенное количество деталей.

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex] [latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex] [latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex] [latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

Код программы

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
На втором этапе фактически делаем тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируем самый быстрый из роботов второго типа.
Теперь оценим сложность работы алгоритма. Для каждой из $n$ деталей работает логарифмическая вставка в очередь с приоритетом. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

A281 Последовательные вычисления значений нового массива

Условие задачи:
Даны действительные числа [latex]a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}[/latex]. Члены последовательности [latex]c_{1}, \ldots, c_{n+1}[/latex] связаны с членами данных последовательностей соотношениями [latex]c_{n+1}=0, c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right ).[/latex] Получить [latex]c_{1}, \ldots, c_{n+1}[/latex].

Входные данные:
В первой строке задано число [latex]n[/latex]. В последующих строках записано две числовые последовательности из n чисел.

Выходные данные:
Вывести результирующую последовательность [latex]c[/latex], найденную согласно условию задачи.

Тесты:

Входные данные Выходные данные
28 100 23 45 62 17 873 46 927 64 5 8 9 3 0 89 73 12 53 62 7 12 35 64 50 227 23 100 80
12 34 23 6 7 8 9 25 10 9 73 24 27 8 4 3 2 0 9 1 45 62 100 104 5 6 14 21
8.89145197864941 0.7532429753739995 3.46536409638595 10.014351523139867 -0.19111480725820545
95.9517680178081 -1.0983211464949347 50.88210356032888 6.781413598577088 0.5624396639914702
0.11015755091584475 0.3767441860465116 0.1111111111111111 0.0 4.803215151847447 -14.529255339679752
8.024345590557227 0.5045509487875016 -105.04390117066583 9.590229411789153 0.2700904535823736
0.5704400476332376 0.6438589905891021 0.5993533748082496 20.57676071984004 -6.031862745098037
9.813084112149534 3.8095238095238093 0.0
10 2 -4 1 2 45.2 34 -23 34 56 7.09
-3.4 4 4 -5 2.4 34.04 23 567 -3 4
-0.8567913942992066 -1.0657095142326265 0.24663198875517678 -0.05462407795229777 31.61389033873605 0.9702487256173882 -1.0025608427005548 0.05874893533055214 -11.733892090099529 1.7725 0.0

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

Алгоритм решения:
Узнаем количество необходимых элементов: считаем число [latex]n[/latex]. С помощью двух циклов также считаем все элементы массивов [latex]a[/latex] и [latex]b[/latex]. Заведем еще один счетчик для нахождения значений ячеек нового массива, воспользовавшись нашей заданной формулой [latex]c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right )[/latex] при условии, что [latex]c_{n+1}=0.[/latex] Выведем все элементы единой строкой.

Код программы на Java
Условие задачи

М6a

Задача

Чётные числа из стандартного потока ввода поместить в хранилище с именем Even, а нечётные — Odd. Во входном потоке неизвестное количество целых чисел через пробел.

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

Неизвестное количество целых чисел через пробел

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

Чётные числа в хранилище с именем Even и нечётные числа в хранилище с именем Odd

Тесты

Входные данные Even Odd
-2 17 38 23 147 68 -19 -46 11 13 73 8 -24 4 0 10 13 15 7 33 19
11 41 -37 14 98 64 -1 3 12 8 74 14 98 64 12 8 74 11 41 -37 -1 3

Решение

Создаем два вектора Odd и Even. С помощью цикла while вводим неопределенное количество элементов. Внутри цикла с помощью push_back четные числа помещаем в Even, а нечетные в Odd.

Пример работы программы можно увидеть на ideone.

e-olymp 5741. Стек шаров

Задание

Телеканал XYZ разрабатывает новое игровое шоу, в котором участники должны сделать некоторый выбор чтобы получить приз. Игра состоит из треугольного стека шаров, на каждом из которых записано целочисленное значение, как показано ниже на примере.

Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю.

Директор телешоу заинтересован в том, чтобы участник получил максимальный приз для заданного стека. Так как он является Вашим босом, то попросил Вас решить эту задачу.

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

Каждый тест задается в нескольких строках. Первая строка содержит количество рядов [latex]N (1 ≤ N ≤ 1000)[/latex] в стеке. [latex]i[/latex]-ая из следующих [latex]N [/latex] строксодержит [latex]i[/latex] целых чисел [latex]B_{ij} (-10^{5}≤ B_{ij}≤ 10^{5}[/latex] для [latex]1 ≤ j ≤ i ≤ N)[/latex]; значение [latex]B_{ij}[/latex] равно числу, записанному на [latex]j[/latex]-ом шаре в [latex]i[/latex]-ом ряду стека (первый ряд — самый верхний, в каждом ряду первым шаром является самый левый).

За последним тестом следует строка, содержащая один ноль.

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

Для каждого теста вывести в отдельной строке целое число — максимальный приз, который может получить участник игры для заданного стека шаров.

Тесты

Ввод Вывод
4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0
7
0
6
3
7
2 1
3 4 6
2
5
9 2
1
2
0
23
16
2

Код

Решение

Иницианилизируем  двумерный массив [latex]s[/latex], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.

Ссылки

  1. Условие на e-olymp
  2. Код на Ideone

e-olymp 6129. Дек с защитой от ошибок

Задача с сайта e-olymp.com.

Условие задачи

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

 

Входные данные
Каждая строка содержит одну команду.

Выходные данные
Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

Входные данные Выходные данные
1 front
back
pop_back
pop_front
exit
error
error
error
error
bye
2 push_back 1
back
exit
ok
1
bye
3 push_back 1
push_front 2
back
front
size
clear
size
pop_back
exit
ok
ok
1
2
2
ok
0
error
bye

Код программы

Описание

Структура данных «дек» реализована в виде двусвязного списка. В классе MyDeque реализованы все требуемые методы. Те из них, после вызова которых, по условию, программа должна вывести некоторую строку, возвращают эту строку («ok» или «bye»). При попытке удалить или просмотреть элемент пустого дека создаётся и передаётся новый объект класса DequeException, наследующего класс Exception. В ходе работы функции main создаётся объект класса MyDeque, после чего читаются строки из входного потока и выполняются требуемые команды. В случае, если перехватывается исключение, выводится строка «error».

Код на ideone.com.

Засчитанное решение на e-olymp.com.

AL6

Условие

Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

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

$latex ({([])})$

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

Yes.

Код

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Пример работы программы можно увидеть на сайте ideone.
Условие задачи.

A301. Количество точек в полукругах

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

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

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

Код программы

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

e-olymp 2820. Перемещение коня

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]n[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]a[/latex]—[latex]h[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]—[latex]8[/latex]), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»

Тест

Пример входных данных Пример выходных данных
[latex]e2[/latex] [latex]e4[/latex] Путь от [latex]e2[/latex] к [latex]e4[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]b2[/latex] Путь от [latex]a1[/latex] к [latex]b2[/latex] занимает [latex]4[/latex] шагов.
[latex]b2[/latex] [latex]c3[/latex] Путь от [latex]b2[/latex] к [latex]c3[/latex] занимает [latex]2[/latex] шагов.
[latex]a1[/latex] [latex]h8[/latex] Путь от [latex]a1[/latex] к [latex]h8[/latex] занимает [latex]6[/latex] шагов.
[latex]a1[/latex] [latex]h7[/latex] Путь от [latex]a1[/latex] к [latex]h7[/latex] занимает [latex]5[/latex] шагов.
[latex]h8[/latex] [latex]a1[/latex] Путь от [latex]h8[/latex] к [latex]a1[/latex] занимает [latex]6[/latex] шагов.
[latex]b1[/latex] [latex]c3[/latex] Путь от [latex]b1[/latex] к [latex]c3[/latex] занимает [latex]1[/latex] шагов.
[latex]f6[/latex] f[latex]6[/latex] Путь от [latex]f6[/latex] к [latex]f6[/latex] занимает [latex]0[/latex] шагов.

 

Решение

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные aи b типа char, где a и b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых a, ny — координата одной клетки и b, ty — координата другой клетки. nx — цифровая координата, которую мы получаем из буквы, отнимая от a.  Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.