Начало
Соревнования
Задачи очного тура личного первенства 2012
A. Компьютерное зрение
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (A) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Одной из основных задач компьютерного зрения является построение модели
скелета человека по данным, полученным от различных
устройств (RGB-камеры, IR-сенсора и т.д.). В большинстве случаев в качестве данных
используются карты глубин – структуры,
описывающие расстояния от устройства до точек сцены. В нашем случае карты глубин
представлены прямоугольными числовыми матрицами.
Каждый элемент матрицы (пиксел) соответствует некоторой точке в пространстве
сцены (в нашей задаче для простоты используется
ортогональная проекция на картинную плоскость), множество таких точек
будем называть облаком точек (см. рисунок). Облако точек,
представляющих человека в сцене, будем называть облаком точек человека.
Одним из методов скелетизации является метод Voxel Scooping. В ходе его применения
возникает следующая подзадача: необходимо разделить
облако точек человека набором плоскостей, параллельных картинной
таким образом, чтобы точки облака были наиболее равномерно
распределены в областях, порождаемых разбиением.
Итак, дана прямоугольная матрица размера `N` на `M` (`1\ ≤\ N\ ≤\ 50`, `1\ ≤\ M\ ≤\ 50`), элементы
матрицы – целые числа от 0 до 65535.
Ненулевые элементы матрицы – пиксели, задающие облако точек человека.
Требуется разделить облако точек человека не более
чем `K` (`1\ ≤\ K\ ≤\ 20`) вертикальными плоскостями таким образом,
чтобы сумма расстояний от каждой точки до ближайшей плоскости была
минимальной. В случае, если существует несколько оптимальных разделений,
необходимо выбрать то, которое содержит наименьшее количество
плоскостей. Если существует несколько вариантов с минимальным
количеством плоскостей, можно вывести любой из них.
Формат ввода
В первой строке ввода заданы числа `N`, `M` и `K`. Каждая из следующих `N` строк
содержит `M` целых чисел, задающих элементы матрицы.
Гарантируется, что матрица содержит хотя бы один ненулевой элемент.
Формат вывода
В первой строке вывести одно вещественное число – минимальное значение суммы
расстояний с точностью не менее `10^{-6}`.
Во второй строке вывести целое число `q` (`1\ ≤\ q\ ≤\ K`) – количество вертикальных плоскостей, входящих в оптимальное разбиение.
В третьей строке вывести `q` чисел через пробел – глубины разделяющих плоскостей в оптимальном разбиении с 9 десятичными знаками после точки.
Пример ввода
28 18 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 3 2 3 4 0 0 0 0 0 0 0 0 0 0 4 4 3 3 2 2 3 3 4 4 0 0 0 0 0 0 0 4 2 2 2 2 2 2 2 2 2 2 4 0 0 0 0 0 2 2 2 2 1 2 2 2 2 2 2 2 2 2 0 0 0 0 2 2 0 0 1 2 2 1 1 1 0 0 0 2 0 0 0 0 2 2 0 0 1 1 1 1 1 1 0 0 2 2 0 0 0 0 0 2 0 0 1 1 1 1 1 1 0 0 2 2 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 2 0 0 0 0 0 0 0 1 1 1 1 3 3 1 1 0 2 2 0 0 0 0 0 0 0 0 0 1 3 3 3 3 1 0 1 2 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 1 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 3 3 3 0 0 0 0 0 0 0 0 0 0 3 3 3 3 0 3 3 3 0 0 0 0 0 0 0 0 0 0 3 4 3 0 0 3 4 4 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 4 4 0 0 0 0 0 0 0 0 4 4 0 0 0 0 0 0 0 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Пример вывода
84.000000 2 1.500000000 3.500000000
B. Новая апория Зенона
Вывод формулыОлимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (B) |
| 02/07/2014 | Лето 2014 1 курс (47) |
| 25/06/2018 | Лето 2018 - 1 (упрощенное) (B) |
| 01/07/2019 | Лето 2019 - 1 (упрощенное) (A) |
| 29/06/2020 | Лето 2020 - 1 (упрощенное) (B) |
| 28/06/2021 | Лето 2021-1 (B) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Археологи при раскопках Александрийской библиотеки обнаружили неизвестное
ранее сочинение древнегреческого философа Зенона, в котором доказывалось
невозможность существования тел, находящихся в абсолютном покое.
"Если уронить упругий мяч с высокой башни, то он отскочит от земли на одну
десятую первоначальной высоты падения, при втором отскоке мяч
взлетит на одну десятую от высоты предыдущего отскока и так далее. Мяч будет
отскакивать от земли бесконечно количество раз и никогда не придет в состояние покоя".
Пусть мяч первоначально падает с высоты `H` метров, после отскока взлетает на `1/K` предыдущей высоты, а
ускорение свободного падения равно 10 м/c`^2`. Напишите программу, которая для заданной начальной высоты
падения `H` и коэффициента `K` вычисляет время до полного завершения отскоков и путь, пройденный мячом
до момента остановки.
Формат ввода
Первая строка ввода содержит два целых числа `H` и `K` (`2\ ≤\ H\ ≤\ 1000`, `2\ ≤\ K\ ≤\ 100`).
Формат вывода
В первой строке вывести время и путь с точностью `10^{-6}`.
Пример ввода
100 20
Пример вывода
7.048150 110.526316
C. Замена цифр
Генерация всех подмножеств, сочетаний, перестановокДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (C) |
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу, определяющую, какое наименьшее количество цифр нужно
заменить в заданном числе `X`, чтобы оно без остатка делилось на другое заданное число `Y`.
При этом первую цифру числа `X` нельзя заменять на 0.
Формат ввода
Первая строка ввода содержит два целых числа `X` и `Y` (`2\ ≤\ X\ <\ 10^18`, `2\ ≤\ Y\ <10^5`, `Y\ <\ X`).
Формат вывода
В первой строке вывести одно число – наименьшее количество измененных цифр.
Во второй строке вывести число `X` после выполнения изменений. Можно вывести любой из возможных вариантов.
Пример ввода
111 11
Пример вывода
1 121
D. A1.R1C1
Системы счисления с другим основаниемЛексический анализ
Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (D) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В электронных таблицах можно использовать две формы для указания в формуле адреса ячейки.
По умолчанию адрес ячейки состоит из буквенного обозначения столбца и номера строки. Столбец 1
обозначается A, столбец 2 – B, …, столбец 26 – Z. Следующие столбцы обозначаются двумя буквами,
столбец 27 – AA, столбец 28 – AB, …, столбец 52 – AZ, столбец 53 – BA и так далее.
Аналогично, после столбца ZZ идет столбец AAA, затем AAB и так далее. Для определения, где
находится указанная в формуле ячейка, требуется хорошее знание латинского алфавита.
Также большой проблемой становится изменение формул при копировании. Формула "A1+B1" превращается в
соседней справа ячейке в "B1+C1", а в соседней снизу ячейке — в "A2+B2", так как адрес ячейки считается
относительным. Для жесткой привязки адреса ячейки к определенному столбцу или строке
перед буквенным обозначением столбца и/или номером строки нужно поставить символ $ (доллар): $A$1 (адрес
не меняется), $A1 (может меняться только номер строки), A$1 (может меняться только столбец).
Гораздо удобнее обращаться к ячейке по номеру ее строки и столбца в форме R`n`C`m`, где `n` - номер строки,
а `m` - номер столбца, например, R1C1. Вместо абсолютного номера строки или столбца можно указать смещение по отношению к ячейке, содержащей формулу, в квадратных скобках. Смещение может быть как положительным, так и отрицательным. При нулевом смещении квадратные скобки и ноль опускаются.
Например, RC[-1] обозначает адрес соседней слева ячейки, а R[2]C[1] – ячейки,
находящейся на 2 строки ниже и на 1 столбец правее. Можно комбинировать относительную и абсолютную
адресацию, например, R1C[-1] – ячейка, расположенная в 1-й строке на 1 столбец левее.
Зафиксированная с помощью символа $ в форме A1 часть адреса ячейки соответствует абсолютному номеру строки или столбца в форме R1C1, а незафиксированная — относительному смещению, поэтому при копировании формулы, преобразованные в форму R1C1, не меняются.
Это особенно удобно, если заполнение таблицы данными и формулами происходит из внешнего приложения.
Напишите программу, которая преобразует адреса ячеек в формуле из формы A1 в форму R1C1.
Формат ввода
Первая строка ввода содержит адрес ячейки, содержащей формулу в форме A1.
Вторая строка ввода содержит формулу. Формула является корректным арифметическим выражением,
которое содержит только обращения к ячейкам в форме A1, числа (целые и вещественные с
разделителем ',' (запятая) между целой и дробной частью), пять знаков
операций ('*', '+', '-', '/' и '^'), круглые скобки и
вызовы математических функций. Имена функций состоят из прописных латинских букв и цифр и
начинаются с буквы, например, MAX, LOG10. Аргументы функции указываются в
круглых скобках и разделяются символом ';' (точка с запятой). Длина имени функции не
превышает 10 символов. Другие символы (пробелы, строчные латинские буквы и т.п.) в формуле отсутствуют.
Длина строки с формулой не превышает 1000 символов. Номер строки находится в диапазоне от 1 до `10^6`,
буквенное обозначение столбца содержит от 1 до 4 букв. Количество цифр в числе не превышает 10.
Формат вывода
В первой строке вывести формулу, в которой все адреса ячеек преобразованы в форму R1C1.
Пример ввода
B2 A1+2,5*B1+MAX($C1;0)
Пример вывода
R[-1]C[-1]+2,5*R[-1]C+MAX(R[-1]C3;0)
E. ABC-гипотеза
Алгоритм ЭвклидаПростые числа, разложение на множители
Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (E) |
Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В августе 2012 года японский математик Синити Мотидзуки опубликовал
доказательство знаменитой ABC-гипотезы, которая была сформулирована в работах Массера и
Эстерле в 80-х гг. XX века. Эта гипотеза оказалась весьма полезной при получении множество
фундаментальных результатов теории чисел и алгебраической геометрии и, в частности, великая
теорема Ферма может быть выведена в несколько строк как её следствие.
Для этой задачи необходимо понятие радикала. Радикалом числа `"rad"(n)` называется произведение всех
простых множителей этого числа. Например, `"rad"(24)=2*3=6`. У этого числа есть несколько очевидных свойств.
Например, если `a` и `b` взаимно просты, то есть не имеют общих делителей, отличных от единицы, то `"rad"("ab")\ =\ "rad"(a)*"rad"(b)`.
Кроме этого, равенство `"rad"(a)=a` выполняется тогда и только тогда, когда `a` – произведение попарно
различных простых чисел.
Рассмотрим тройки чисел `(a,\ b,\ c)`, для которых `a+b=c` и все три числа взаимно просты. Так как числа `a`, `b`, `c` взаимно
просты, то `"rad"("abc")="rad"(a)*"rad"(b)*"rad"(c)`. Массера и Эстерле заинтересовал вопрос: какое из
чисел `c` или `"rad"("abc")` больше? Оказалось, что однозначного ответа на этот вопрос нет. Например, для
тройки `(2,\ 3,\ 5)` `"rad"(2*3*5)=2*3*5=30>5`, а для тройки `(1,\ 8,\ 9)` `"rad"(1*8*9)="rad"(23*32)=2*3=6<9`.
Дальнейшие исследования позволили установить, что тройки первого типа встречаются намного чаще: если
взять случайную тройку, то почти всегда будет выполняться именно первое неравенство. Поэтому тройки,
для которых `c>"rad"("abc")`, получили название исключительных. Удалось доказать, что таких троек
бесконечно много, и даже построить бесконечную серию троек, у которой отношение `"rad"("abc")/c` стремится к 0.
Математикам удалось найти другое ограничение на возможные значения радикала, которое получило
название "ABC-гипотеза": для любого действительного числа `r>1` существует конечное число троек
натуральных чисел `(a,\ b,\ c)` таких, что для них выполняются одновременно три условия: `a+b=c`; `a`, `b` и `c`
взаимно просты и `c>"rad"("abc")^r`.
Напишите программу для поиска исключительных троек, которая для заданного `c` находит все пары натуральных
чисел `(a,\ b)`, таких что `a<b`, `a+b=c`, числа `a`, `b` и `c` взаимно просты (достаточно
проверить взаимную простоту любой пары из этой тройки) и `"rad"("abc")<c`.
Формат ввода
Первая строка ввода содержит натуральное число `c` (`2\ ≤\ c\ ≤\ 10^7`).
Формат вывода
В первой строке вывести число `K` – количество найденных пар. Затем вывести `K` строк – найденные пары
в порядке возрастания `a`.
Пример ввода
9
Пример вывода
1 1 8
F. Сапер
МоделированиеДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (F) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя часто играет на компьютере в игру "Сапер". Игра происходит на квадратном поле из `N\ times\ N` клеток.
Первоначально все клетки закрыты и некоторые из них заминированы. Игрок открывает клетки по одной.
Если игрок откроет клетку с миной, он проигрывает. Если в открытой клетке мины нет, то в ней
появляется число, показывающее, сколько клеток, соседствующих с только что открытой, заминировано.
Соседними считаются клетки, примыкающие к данной клетке стороной или углом. Используя
числа в открытых клетках, игрок должен рассчитать расположение мин и может пометить флагом
закрытые заминированные клетки. Когда игрок откроет все клетки, не содержащие мин, он выигрывает
и игра заканчивается. При этом неважно, помечены заминированные клетки флагом или нет.
Петя использует следующий алгоритм при игре. Пусть `m` – число в открытой клетке, вокруг которой
есть `c` закрытых клеток без флага и `f` закрытых клеток с флагом.
- Если на поле существует клетка, у которой `c>0` и `c+f=m`, то все соседние с ней закрытые, но не помеченные флагом, клетки Петя помечает флагом.
- Если на поле существует клетка, у которой `c>0` и `f=m`, то все соседние с ней закрытые, но не помеченные флагом, клетки Петя открывает.
- Если к текущей ситуации на поле неприменимы ни правило 1, ни правило 2, то Петя открывает одну из непомеченных флагом клеток случайным образом с равной вероятностью.
Напишите программу, которая определяет вероятность выигрыша Пети для заданного расположения мин на игровом поле.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 4`). Далее следует `N` строк, содержащих
по `N` символов – расположение мин. Символ '*' означает заминированную клетку, символ '.' – клетку без мины.
Поле содержит не менее одной клетки с миной и не менее одной клетки без мины.
Формат вывода
Вывести одно вещественное число — вероятность выигрыша Пети с точностью `10^{-8}`.
Пример ввода
2 .. .*
Пример вывода
0.25000000
G. Gold Coins
Реализация заданного алгоритмаОлимпиадные задачи на английском языке
| 06/10/2012 | Личное первенство Южного Урала (G) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
The king pays his loyal knight in gold coins. On the first day of his service,
the knight receives one gold coin. On each of the next two days (the second and third days of service),
the knight receives two gold coins. On each of the next three days
(the fourth, fifth, and sixth days of service), the knight receives three gold coins. On each of the
next four days (the seventh, eighth, ninth, and tenth days of service), the knight receives four gold coins.
This pattern of payments will continue indefinitely: after receiving `N` gold coins on each of `N` consecutive
days, the knight will receive `N+1` gold coins on each of the next `N+1` consecutive days, where `N` is
any positive integer.
Your program will determine the total number of gold coins paid to the knight in any given number of days
(starting from Day 1).
Input
Each line of the input (except the last one) contains data for one test case of the problem,
consisting of exactly one integer (in the range 1…10000), representing the number of days. The end of
the input is signaled by a line containing the number 0.
Output
There is exactly one line of output for each test case. This line contains the number of
days from the corresponding line of input, followed by one blank space and the total number of
gold coins paid to the knight in the given number of days, starting with Day 1.
Sample Input
10 6 7 11 15 16 100 10000 0
Sample Output
10 30 6 14 7 18 11 35 15 55 16 61 100 945 10000 942820
H. Место встречи
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (H) |
| 03/07/2019 | Лето 2019 - 2 (C) |
| 09/07/2021 | Лето 2021-6 (командное) (F) |
| 08/07/2022 | Лето 2022-6 (командное) (F) |
| 10/12/2022 | «Базовая олимпиадная подготовка» (second level) - Поиск в ширину (BFS) (проводит novink) (D) |
| 14/12/2022 | Курс I - BFS (проводит BOGAT) (D) |
| 11/12/2023 | Графы: BFS (проводит BOGAT) (D) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя должен срочно встретиться со своими друзьями. Он обзвонил друзей и узнал их местонахождение.
У каждого из друзей Пети на телефоне есть карта местности, разбитая на клетки. Пете нужно выбрать место
для встречи, в которое все смогут попасть за минимальное время, и разослать его координаты друзьям.
За одну секунду Петя и его друзья могут перейти из клетки, в которой находятся, в соседнюю по
горизонтали или вертикали клетку, свободную от препятствий. В одной клетке может находиться
любое количество людей одновременно. Пришедшие на место встречи раньше других должны подождать всех остальных.
Напишите программу, определяющую координаты места встречи и минимальное время, которое потребуется для того,
чтобы Пети и его друзья смогли до него добраться.
Формат ввода
Первая строка ввода содержит три целых числа `N`, `M` и `K` (`2\ ≤\ N,M\ ≤\ 1000`, `2\ ≤\ K\ ≤\ 9`).
Далее следует `N` строк, содержащих по `M` символов — карта местности. Символом '#' на карте
обозначены препятствия и здания, символом '.' – свободная клетка, цифрой от 1 до `K` – текущее
местонахождение Пети и его друзей, также свободная от препятствий клетка. Гарантируется, что любой из
друзей может дойти до Пети двигаясь только по свободным клеткам.
Формат вывода
В первой строке вывести одно целое число – минимальное время до встречи. Во второй строки
вывести координаты места встречи — номер строки и номер столбца через пробел. Если существует
несколько вариантов для места встречи, то можно вывести любой из них.
Пример ввода
3 4 3 1..2 ###. 3...
Пример вывода
4 2 4
