Начало
Соревнования
Задачи Южно-Уральского командного чемпионата 2014
A. Распознавание изображения
Задачи на идеюРазбор случаев
Олимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (A) |
| 23/04/2014 | Занятие 22 (A) |
| 03/07/2020 | Летние сборы - 3 (командное) (A) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Великобинария — виртуальная страна, моделируемая британскими исследователями с помощью суперкомпьютера.
Бинарию населяют два типа жителей: прямы, предпочитающие прямые углы и
строящие дома в форме прямоугольников, и остры, предпочитающие острые углы и дома в
форме остроугольных треугольников. Исследователи получили дамп участка памяти компьютера, в
котором находится одно из поселений, и хотят определить, сколько прямов и сколько остров живут
в этом населенном пункте.
Напишите программу, которая подсчитает количество зданий каждого типа. Здания на изображении
обозначены 1 и отделены друг от друга и краев изображения пустым пространством, обозначаемым 0,
шириной не менее одного пикселя. Координаты углов фигур на распознаваемом изображении необязательно
соответствуют целым числам, значение 1 имеет любой пиксель, в который попадает часть фигуры. Длины
сторон фигур — не менее 5.
Формат ввода
Первая строка ввода содержит два целых числа `H` и `W` (`10\ ≤\ H,\ W\ ≤\ 1000`) — соответственно ширина и высота
изображения местности в пикселях. Каждая из последующих `H` строк состоит ровно из `W` символов (нулей и единиц).
Формат вывода
Вывести два целых числа — количество треугольных и количество прямоугольных зданий.
Пример ввода
12 20 00000000000000000000 00000001000000000000 00000011000001100000 00000111100001111000 00001111100011111110 00000001110011111110 01111100000111111100 01111100000111111100 01111100001111111000 01111100000011111000 01111100000000110000 00000000000000000000
Пример вывода
1 2
B. Гадание на палочках
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (B) |
| 23/04/2014 | Занятие 22 (B) |
| 18/07/2016 | Лето 2016 - 10 (командная) (A) |
| 24/07/2019 | Лето 2019 - 11 (E) |
| 03/07/2020 | Летние сборы - 3 (командное) (B) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (2)
Среди бинарских остров популярно следующее гадание на палочках. Они выбирают из набора палочек три палочки и пытаются сложить из них остроугольный треугольник. Если это получится, то остры считают, что планируемое предприятие ждет успех, иначе отказываются от задуманного.
Напишите программу, определяющую вероятность успешно сложить остроугольный треугольник из трех случайно выбранных из заданного набора палочек.
Формат ввода
Ввод содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 10 000`) — количество палочек. Вторая строка
содержит `N` целых чисел в диапазоне от 1 до `10^9` — длины палочек.
Формат вывода
Вывести одно число — искомую вероятность с точностью `10^{-10}`.
Пример ввода
5 2 7 5 5 10
Пример вывода
0.2000000000
C. Дом для Мебибайта
Использование теорем из геометрии, формулы ПикаОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (C) |
| 18/07/2016 | Лето 2016 - 10 (командная) (B) |
| 28/06/2023 | Лето 2023-2 простые (A) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (1)
Мебибайт, житель Бинарии, хочет построить дом в форме остроугольного треугольника, стороны
которого имеют целочисленную длину. У Мебибайта уже есть две стены для здания длиной `A` и `B`. Он хочет
выбрать длину третьей стены таким образом, чтобы площадь дома была максимальной и все углы здания были острыми.
Формат ввода
Первая строка ввода содержит два целых числа `A` и `B` (`1\ ≤\ A,\ B\ ≤\ 10^9`) – заданные длины сторон.
Формат вывода
Вывести одно целое число — длина третьей стороны, при которой остроугольный треугольник с этими сторонами имеет максимальную площадь.
Пример ввода
5 10
Пример вывода
11
D. Пиццерия
Жадные алгоритмыОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (D) |
| 23/04/2014 | Занятие 22 (D) |
| 18/07/2016 | Лето 2016 - 10 (командная) (C) |
| 03/07/2020 | Летние сборы - 3 (командное) (C) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Создатели Великобинарии заложили в виртуальных жителей любовь к пицце, но их пицца
выглядит как последовательность букв, составляющих название пиццы. Для изготовления пиццы "Маргарита" нужно взять
три буквы А, две буквы Р и по одной букве М, Г, И и Т.
Бинарец Кибибайт работает в пиццерии и должен собирать пиццы из поступающих по конвейеру букв-ингредиентов.
В каждый момент времени может собираться только одна пицца, название которой выбирает Кибибайт перед началом
работы или после сборки очередной пиццы. С конвейера можно брать только тот ингредиент, который
проходит в текущий момент мимо Кибибайта. Кибибайт знает несколько названий-рецептов и последовательность
поступающих букв и хочет собрать как можно больше пицц, чтобы стать работником месяца и получить повышение.
Формат ввода
Первая строка ввода содержит одно целое число: количество названий `N` (`1\ ≤\ N\ ≤\ 1000`).
Далее следует `N` строк, содержащих названия. Названия имеют длину от 1 до 100 букв и состоят только
из русских прописных букв от А до Я (буквы с кодами от 192 до 223, без буквы Ё). Далее следует
строка длиной от 1 до `100\ 000` букв, состоящая из русских прописных букв — поступающие по
конвейеру буквы-ингредиенты.
Формат вывода
В первой строке вывести одно целое число `K` – максимальное количество пицц, которое может собрать Кибибайт.
Во второй строке вывести `K` целых чисел — номера рецептов. Если существует несколько
вариантов с максимальным количеством, то можно вывести любой из них.
Пример ввода
3 МАРГАРИТА СРЕДИЗЕМНОМОРСКАЯ ЛУКОВАЯ МАРГАРИТАЯАВОКУЛРЕДИСЗЕМЛЯТАРАКАНГОРЧИЦА
Пример вывода
3 1 3 1
Когда по конвейеру пройдет последний символ строки, рабочий день Кибибайта заканчивается.
Куда исчезают неиспользованные буквы-ингредиенты в данной задаче неважно, предположим, что из них собирают пиццы другие работники пиццерии, которые стоят на конвейере после Кибибайта. Но нас интересует только количество пицц, собранных Кибибайтом.
E. Цифры
Вывод формулыСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (E) |
| 18/07/2016 | Лето 2016 - 10 (командная) (D) |
| 12/07/2017 | Лето 2017 (1 курс) - 7 (D) |
| 03/07/2020 | Летние сборы - 3 (командное) (D) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В пиццерию часто приходят жители Бинарии, чтобы отметить какое-нибудь событие,
например, `K` секунд после старта процесса, моделирующего жизнь этого жителя. Кибибайт
после повышения стал организатором подобных мероприятий и должен выкладывать на пицце число, соответствующее
нужному событию.
Определите, какой минимальный набор из цифр необходим Кибибайту для выкладывания любого числа в диапазоне от 1 до `N`?
Формат ввода
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).
Формат вывода
В первой строке вывести 10 чисел – минимальное количество цифр 0, 1, 2, …, 9,
необходимое для выкладывания любого числа в диапазоне от 1 до `N`.
Пример ввода
19
Пример вывода
1 2 1 1 1 1 1 1 1 1
F. Строительство дамбы
Поиск в ширину (BFS)Максимальный поток
Олимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (F) |
| 23/04/2014 | Занятие 22 (F) |
| 18/07/2016 | Лето 2016 - 10 (командная) (E) |
| 03/07/2019 | Лето 2019 - 2 (D) |
| 04/10/2021 | Дискретная оптимизация - 3 (проводит BOGAT) (C) |
| 14/09/2022 | Пути в графах (повторение) (проводит BOGAT) (J) |
| 14/12/2022 | Курс I - BFS (проводит BOGAT) (F) |
| 05/07/2023 | Лето 2023-5 простые (E) |
| 11/12/2023 | Графы: BFS (проводит BOGAT) (F) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для защиты столицы Бинарии от наводнений в ущелье между морем и городом необходимо построить дамбу.
Чтобы уменьшить расходы на строительство, как часть дамбы можно использовать скалы, расположенные между
городом и морем.
Напишите программу, которая для заданного расположения скал определит план размещения остальных
частей дамбы, при котором дамба будет полностью защищать город от наводнений, и
потребуются минимальные расходы на строительство. Вода не может протечь между клетками, занятые дамбой
или скалами и соприкасающиеся сторонами, но может протечь между такими клетками, соприкасающиеся только углами.
Формат ввода
Первая строка ввода содержит два целых числа `N` и `M` (`5\ ≤\ N,\ M\ ≤\ 25`) – размеры карты местности.
Далее следует `N` строк, содержащих по `M` символов. Символ '.' означает свободную клетку, а
символ '*' – клетку, занятую скалой. Море находится на верхней границе карты, а город — на нижней.
На левой и правой границе карты находятся горы.
Формат вывода
Вывести `N` строк, содержащих по `M` символов — карту местности, на которой символом '#' отмечены
места строительства дополнительных частей дамбы. Можно вывести любой из минимизирующих строительство вариантов.
Пример ввода
5 6 *..... ...... **.*.. *..**. ......
Пример вывода
*..... ...... **#*.. *..**# ......
G. Dangerous Mission
Поразрядная сортировка и сортировка подсчетомОлимпиадные задачи на английском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (G) |
| 18/07/2016 | Лето 2016 - 10 (командная) (H) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
The recent earthquake in Great Binair did not affect too much the buildings in the capital, which was at the
epicenter of the quake. But the scientists found that it affected the dike wall, which now has a significant
structural failure in its underground part that, if not repaired quickly, can cause the collapse of the dike,
with the consequent flooding the whole capital.
The repair must be done by divers, at a large depth, under extremely difficult and dangerous conditions.
But since the survival of the city is at stake, its residents came out in large numbers to volunteer
for this dangerous mission.
As is traditional in dangerous missions, each diver received at the start of his/her mission a small
card with an identification number. At the end of their mission, the volunteers returned the nameplate, placing
it in a repository.
The dike is safe again, but unfortunately it seems that some volunteers did not return from their
missions. You were hired for the grueling task of, using the list of the plates taken from or
placed in the repository, determine which volunteers lost their lives to save the city.
Input
The input is composed of two lines. The first line contains
one integer `K` (`1\ ≤\ K\ ≤\ 10\ 000`), indicating the length of the list. The second line contains
a sequence of `K` integers. The negative integer `-X` indicates, that the diver with identification
number `X` went to the mission, the positive integer `X` indicates, that the diver with
identification number `X` returned from the mission. Volunteers are identified by numbers from 1 to `10^6`.
Output
Your program must produce a single line containing the identifiers of the volunteers who did not
return from their missions, in ascending order of their identifications. Leave a
blank space after each identifier (notice that, therefore, there must be a blank
space after the last identifier in the line). If every volunteer returned, the
line must contain a single character '*' (asterisc).
Sample Input #1
8 -3 -4 -1 3 -2 -9 1 9
Sample Output #1
2 4
Sample Input #2
8 -5 -3 5 -7 -5 3 7 5
Sample Output #2
*
H. Casino
Системы счисления с другим основаниемПоразрядная сортировка и сортировка подсчетом
Олимпиадные задачи на английском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (H) |
| 23/04/2014 | Занятие 22 (H) |
| 03/07/2020 | Летние сборы - 3 (командное) (E) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
In a lazy afternoon Gibibyte came to realize that, to make his future plans successful he needs a lot of money. To make some quick cash he decided to go to the casino to play a game. The rule of the game is the following:
1. The player is given `N` cards. Each card has a non-negative integer printed in it.
2. The player will choose `K` cards from the given cards.
3. The bitwise AND value of the chosen cards will be calculated and the player will be given the same amount of money (i.e. equal to the bitwise AND value of the chosen cards).
After getting `N` cards Gibibyte was in a fix as usual. He could not decide which of the cards to choose.
So he called you to help him. Please tell him the maximum amount he can win from these set of cards. If you are confused about bitwise AND operation see the notes section below.
Input
The first line of input will contain two integers `N` and `K` (`0\ <\ K\ <\ N\ ≤\ 10^5`). Then the following line
will contain `N` non-negative integers `C_i` (`0\ ≤\ C_i\ <\ 2^31`) separated by space, denoting the numbers printed
on each of the cards.
Output
Print the maximum amount, that Gibibyte can win, on the first line of output and chosen cards on the second line (in any order).
Note:
A bitwise AND takes two binary representations of equal length and performs the logical AND operation on each pair of corresponding bits.
The resulting bit of a position is 1 if the bit at that position of both numbers is 1; otherwise, that bit is 0.
For example:
0101 (decimal 5)
AND 0011 (decimal 3)
= 0001 (decimal 1)
Sample Input
4 2 8 5 0 3
Sample Output
1 3 5
I. Исчисление согласных
Разбор случаевОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (I) |
| 23/04/2014 | Занятие 22 (I) |
| 03/07/2020 | Летние сборы - 3 (командное) (F) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Бинарские математики обратили внимание на количество согласных в названиях числительных и,
затратив на исследования миллиард наносекунд, смогли найти наименьшие натуральные числа, в названии которых
содержится ровно `K` согласных, для `K` от 1 до 10. Такими числами оказались one (1 согласная),
two (2), three (3), twelve (4), thirteen (5),
twenty two (6), twenty three (7),
one hundred two (8), one hundred three (9),
one hundred twelve (10).
Вам необходимо продолжить их работу и найти наименьшие натуральные числа, в названии которых
содержится ровно `K` согласных, для `K` от 1 до 432. Названия числительных в английском языке:
zero, one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen,
sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred,
thousand (`10^3`), million (`10^6`), billion (`10^9`), trillion (`10^12`), quadrillion (`10^15`),
quintillion (`10^18`), sextillion (`10^21`), septillion (`10^24`), octillion (`10^27`), nonillion (`10^30`),
decillion(`10^33`), undecillion (`10^36`), duodecillion (`10^39`), tredecillion (`10^42`),
quattuordecillion (`10^45`), quindecillion (`10^48`), sexdecillion (`10^51`), septendecillion (`10^54`),
octodecillion (`10^57`), novemdecillion (`10^60`). Со словом hundred может быть связано только числительное
от 1 до 9, т.е. 2500 записывается как "two thousand five hundred", а не "twenty five hundred". Перед
словами hundred, thousand, million и т.д. должно быть указано какое-то числительное, т.е. нужно
писать "one million", а не просто "million".
Формат ввода
Ввод содержит одно целое число `K` (`1\ ≤\ K\ ≤\ 432`).
Формат вывода
Вывести одно целое число — наименьшее натуральное число, в названии которого содержится ровно `K` согласных.
Пример ввода
10
Пример вывода
112
J. Светопредставление
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (J) |
| 18/07/2016 | Лето 2016 - 10 (командная) (F) |
| 03/07/2020 | Летние сборы - 3 (командное) (G) |
| 01/02/2022 | Зима 2022 - 7 (проводит BOGAT) (C) |
| 19/03/2024 | Дерево отрезков (начало) (проводит BOGAT) (B) |
Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мебибайту необходимо рассчитать энергетические нагрузки во время светомузыкального шоу.
Управление `2^20` лампочками происходит следующим образом. Для каждого такта музыкального сопровождения
указаны два целых числа, определяющих диапазон номеров лампочек, состояние которых должно
измениться на противоположное. Если лампочка была выключена, она должна загореться, а
горящая лампочка — погаснуть. В начальный момент времени все лампочки выключены.
Напишите программу, определяющую количество горящих лампочек после выполнения каждой команды.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100 000`) – количество команд на переключение
состояния лампочек. Далее следует `N` строк, каждая строка содержит два целых
числа `a_i` и `b_i` (`1\ ≤\ a_i\ ≤\ b_i\ ≤\ 2^20`) — команда на переключение.
Формат вывода
Вывести `N` строк, в `i`-ой строке вывести количество горящих лампочек после `i`-ой команды.
Пример ввода
3 5 10 3 8 1 12
Пример вывода
6 4 8
K. Гигамеш и бездонная пропасть
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (K) |
| 23/04/2014 | Занятие 22 (K) |
| 18/07/2016 | Лето 2016 - 10 (командная) (G) |
| 03/07/2020 | Летние сборы - 3 (командное) (H) |
| 14/12/2022 | Курс I - BFS (проводит BOGAT) (B) |
| 05/07/2023 | Лето 2023-5 простые (F) |
| 11/12/2023 | Графы: BFS (проводит BOGAT) (B) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В Бинарии сохранились логи от предыдущих версий модели, в которых можно найти информацию о
героическом путешествии Гигамеша, который исследовал границы виртуального мира.
Однажды Гигамешу преградил путь глубокий разлом, но на горизонте был виден еще не присоединенный к модели
кусок виртуального пространства, а между краями разлома медленно проплывали облака.
Используя ошибку в ранних версиях модели, которая позволяла некоторое время находиться на облаке, Гигамеш
смог перебраться на другой край пропасти.
Гигамеш умеет прыгать на фиксированное расстояние `L` вперед и назад. Прыжки можно
делать только в точках с целыми координатами. Также Гигамеш может передвигаться пешком по земле и облакам.
Небольшая ошибка в параметре прочности не сделала облака достаточно надежной конструкцией, поэтому Гигамеш
должен был при переправе минимизировать расстояние, пройденное по облакам пешком.
Напишите программу, которая определит по расположению облаков минимальное расстояние, которое
должен пройти Гигамеш пешком по облакам, чтобы переправиться на другой край пропасти.
Формат ввода
Первая строка ввода содержит три целых числа: ширина пропасти `W`,
длина прыжка `L` (`2\ ≤\ L\ ≤\ 1000`, `L < W ≤\ 100 000`) и количество облаков `N` (`1\ ≤\ N\ ≤\ 10 000`).
Далее следует `N` строк, каждая строка содержит два целых числа `a_i` и `b_i` — координаты начала и окончания
поверхности `i`-го облака (`0\ <\ a_1\ ≤\ L`, `a_i\ <\ b_i`, `b_i\ <\ a_{i+1}`, `a_{i+1} - b_i ≤\ L`, `b_N <\ W`, `W - b_N\ ≤\ L`,
координата 0 соответствует краю пропасти, на котором стоит Гигамеш). Первый прыжок можно сделать как из точки на
краю разлома, так и находящейся на некотором расстоянии от него,
аналогично для приземления на другой стороне разлома (см. пример ввода 2).
Формат вывода
В первой строке вывести одно целое число — минимальное расстояние, которое должен
пройти Гигамеш пешком по облакам при переправе. Во второй строке вывести координаты точек,
в которых Гигамеш должен делать прыжки. Можно вывести любой вариант, в котором достигается
найденный минимум. Если переправиться на другой край пропасти невозможно, то в первой строке вывести число `-1`.
Пример ввода 1
17 5 4 4 5 6 8 9 11 12 13
Пример вывода 1
2 0 5 11 7 12
Пример ввода 2
5 4 1 2 3
Пример вывода 2
0 -2 2
