Начало
Соревнования
Задачи очного тура личного первенства 2011
A. Суперпростые числа
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (A) |
| 22/07/2016 | Лето 2016 - 14 (A) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Назовем число из `n` цифр `a_1\ a_2\ …\ a_n` суперпростым,
если числа `a_1\ a_2\ …\ a_k` являются простыми для всех `k` от 1 до `n` включительно.
Найдите все суперпростые числа, состоящие из `n` цифр.
Ввод содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 9`).
Вывести все суперпростые числа из `n` цифр в порядке возрастания, по одному числу в строке.
Если ни одного суперпростого числа из `n` цифр не найдено, то вывести сообщение "NO SOLUTION" (без кавычек).
Пример ввода
2
Пример вывода
23 29 31 37 53 59 71 73 79
B. Преобразования
Задачи на идеюТехника программирования, моделирование
Олимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (B) |
| 22/07/2015 | Практика 1 и 2 курса (7) (E) |
| 22/07/2016 | Лето 2016 - 14 (B) |
| 09/07/2021 | Лето 2021-6 (командное) (G) |
| 08/07/2022 | Лето 2022-6 (командное) (G) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
С натуральным числом, записанном в десятичной системе счисления, разрешается делать следующие операции:
- дописать в конце цифру 0;
- дописать в конце цифру 4;
- разделить на 2 (если число четное).
Напишите программу, которая находит способ получения с помощью этих операций из числа 2 заданного числа `N`.
Ввод содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).
Вывести последовательность операций, в результате применения которых получается заданное число `N`
(можно вывести любую последовательность, не обязательно кратчайшую, но количество операций не должно превышать 256).
Если получить число `N` невозможно, то вывести сообщение "NO SOLUTION" (без кавычек).
Пример ввода
104
Пример вывода
CAB
C. Игра
ИгрыОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (C) |
| 19/03/2014 | Занятие 17 (D) |
| 22/07/2016 | Лето 2016 - 14 (C) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Есть `N` кучек камней. Двое играющих поочередно берут камни из кучек.
Во время хода можно взять любое количество камней из не более чем `K` кучек, и по крайней мере
один камень из какой-то кучки должен быть взят. Выигрывает тот, кто возьмет последний камень.
Напишите программу, которая для заданного распределения камней по кучкам определяет,
может ли игрок, делающий первый ход, выиграть и какой ход он должен сделать, чтобы выиграть.
Первая строка ввода содержит два целых числа `N` и `K` (`1\ ≤\ K\ <\ N\ ≤\ 100`).
Вторая строка содержит `N` целых чисел в диапазоне от 1 до 10000 – количество камней в кучках.
Вывести в первой строке сообщение "YES", если начинающий игрок может выиграть, иначе
сообщение "NO". Во второй строке в случае положительного ответа вывести `N` целых чисел –
сколько камней нужно взять из соответствующей кучки. Можно вывести любой вариант выигрышного хода.
Пример ввода 1
4 2 10 5 10 15
Пример вывода 1
YES 0 5 0 5
Пример ввода 2
2 1 10 10
Пример вывода 2
NO
D. Наибольшее число
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (D) |
| 07/10/2015 | Занятие по теме "Задачи на идею" (E) |
| 22/07/2016 | Лето 2016 - 14 (D) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Среди `n`-значных чисел, в десятичной записи которых нет цифры 0, найти число,
для которого разность между самим числом и произведением его цифр максимальна.
Ввод содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 10000`).
Вывести в первой строке найденное `n`-значное число с указанными свойствами.
Если существует несколько таких чисел, то можно вывести любое из них.
Пример ввода
2
Пример вывода
91
E. Невидимость
Поиск экстремума функцииОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (E) |
| 06/05/2013 | Занятие 27 (G) |
| 22/07/2016 | Лето 2016 - 14 (E) |
Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Земной флот должен подобраться незаметно к планете жукеров. Для этого на большом грузовом
корабле был установлен генератор поля невидимости.
Так как генератор потребляет энергию пропорционально кубу радиуса
создаваемого поля, желательно разметить корабль с генератором в точке, где расход энергии на поддержание
поля, скрывающего корабли флота, будет минимальным.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество кораблей. Далее следует `N` строк,
каждая из которых содержит три целых числа `X_i`, `Y_i`, `Z_i` (`-1000\ ≤\ X_i,\ Y_i,\ Z_i\ ≤\ 1000`) – координаты
`i`-го корабля в боевом порядке.
Вывести три вещественных числа `X`, `Y`, `Z` – координаты точки для размещения корабля с генератором
с точностью `10^{-5}`.
Пример ввода
3 0 0 0 1 1 0 2 0 0
Пример вывода
1.00000 0.00000 0.00000
F. Поход
Динамическое программирование и запоминающие функцииБитовые массивы
Олимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (F) |
| 22/07/2016 | Лето 2016 - 14 (F) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Пете нужно подготовить маршрут для похода. У Пети есть карта,
на которой для каждого участка местности указана сложность его преодоления.
Во время похода можно двигаться только на юг или на восток, переходя с одного участка местности на другой.
Петя хочет найти маршрут, сложность которого как можно ближе к заданной сложности `с`. Если есть
два маршрута со сложностью `c-d` и `c+d`, то предпочтительнее маршрут меньшей сложности.
Из двух маршрутов одинаковой сложности можно выбрать любой.
Первая строка ввода содержит три целых числа – размеры местности `n` и `m` (`2\ ≤\ n,\ m\ ≤\ 100`) и требуемая
сложность похода `c` (`0\ ≤\ c\ ≤\ 1000`). Далее следует `n` строк, содержащих по `m` символов – цифры от '0' до '9'.
Цифра означает сложность преодоления соответствующего участка местности.
Начальная точка маршрута находится верхнем левом углу карты, а конечная – в правом нижнем углу.
Вывести в первой строке сложность найденного маршрута.
Во второй строке вывести маршрут как последовательность из `(n+m-2)` букв
'S' (движение на клетку вниз) и 'E' (движение на клетку вправо).
Пример ввода
3 3 7 123 322 931
Пример вывода
8 ESES
G. Рассылка информации
Минимальное остовное деревоОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (G) |
| 10/01/2023 | Остовные деревья (проводит BOGAT) (C) |
| 05/03/2023 | «Базовая олимпиадная подготовка» (second level) - Остовные деревья (проводит novink) (C) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (3)
Староста группы должна сообщить всем студентам в группе некоторую информацию.
Так как стоимость разговора у разных операторов сотовой связи различна и может отличаться в зависимости от направления вызова,
то необходимо найти способ довести информацию до всех студентов,
потратив минимальные средства. Кроме того не у каждого человека есть номера телефонов
остальных студентов группы (т.е. `a` может позвонить `b`, а `b` может не знать номер телефона `a`).
Напишите программу, которая определит минимальные затраты на информирование студентов.
Первая строка ввода содержит два целых числа – количество студентов `N` (`1\ ≤\ N\ ≤\ 1000`)
и количество каналов связи
между студентами `M` (`1\ ≤\ M\ ≤\ 10000`).
Далее следует `M` строк, содержащих по три целых числа `a`, `b` и `с` (`0\ ≤\ a,\ b\ ≤\ N-1`, `a\ ≠\ b`, `0\ ≤\ c\ ≤\ 1000`),
означающие, что студент `a` может передать информацию студенту `b`, потратив `c` копеек.
Номер 0 соответствует старосте группы. Пары студентов (`a`,`b`) в списке каналов связи не повторяются.
Вывести одно целое число – минимальные затраты на информирование. Если разослать информацию невозможно,
то вывести сообщение "NO SOLUTION" (без кавычек).
Пример ввода 1
4 5 0 1 10 0 2 10 2 0 20 1 3 20 2 3 30
Пример вывода 1
40
Пример ввода 2
2 1 1 0 10
Пример вывода 2
NO SOLUTION
H. Кротовые норы
МоделированиеОлимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (H) |
| 22/07/2016 | Лето 2016 - 14 (G) |
| 12/07/2019 | Лето 2019 - 6 (командное) (I) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Петя хочет засыпать в саду несколько кротовых нор. Он сыпет в каждую нору грунт, пока
уровень грунта не совпадет с уровнем земли в саду. Этот способ не позволяет
засыпать горизонтальную часть норы полностью, так как грунт из вертикальной части норы
будет сыпаться только до тех пор, пока не образуется склон с углом 45 градусов.
Для упрощения расчетов будем рассматривать двумерную задачу.
Напишите программу, которая по схеме кротовых нор вычислит объем грунта, необходимого для засыпания всех нор.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 100`) – размеры схемы.
Далее следует `N` строк, содержащих по `M` символов '.' (нора) и '#' (земля) –
схема кротовых нор.
Верхняя граница схемы соответствует уровню земли. Предполагается, что за границами схемы ходов кротов нет.
Вывести одно вещественное число – объем грунта, необходимый для засыпания нор, с точностью `10^{-2}`.
Пример ввода 1
3 7 .####.# ......# ##...#.
Пример вывода 1
6.50
Пример ввода 2
2 3 .#. ...
Пример вывода 2
4.75
I. Optical Reader
Реализация заданного алгоритмаОлимпиадные задачи на английском языке
| 01/10/2011 | Личное первенство Южного Урала (I) |
| 11/10/2023 | Занятие 228 (проводит zhumagulovTM) (B) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Professor John decided to apply only multiple-choice tests to his students.
In each test, each question will have five alternatives (A, B, C, D, and E), and
the teacher will distribute one answer sheet for each student. At the end of the test, the answer
sheets will be scanned and processed digitally to obtain the test score for each student.
Initially, he asked a nephew, who knows computer programming, to write a program to extract
the alternatives marked by the students in the answer sheets. The nephew wrote a good piece of
software, but cannot finish it because he needs to study for the ICPC contest.
During processing, the answer sheets are scanned in gray levels between 0 (full black) and 255
(total white). After detecting the position for the five rectangles corresponding to each
of the alternatives of a question, the software calculates the
average pixel gray level for each rectangle, returning an integer value corresponding
to each alternative. If the rectangle was filled properly the average value is zero (all black).
If the rectangle was left blank the average value is 255 (white total).
Thus, ideally, if the average values for each alternative of a question are (255, 0, 255, 255, 255),
we know that the student has marked alternative B for that question. However, as answer sheets
are processed individually, the average gray level for a completely filled rectangle is
not necessarily 0 (may be higher), and the value for a rectangle not
filled is not necessarily 255 (may be less). Professor John determined that rectangle
average gray levels would be divided into two classes: those with values equal or lower to 127 are
considered black and those with values higher than 127 will be considered white.
Obviously, not necessarily all questions of all sheets are marked correctly.
It can happen that a student makes a mistake and marks more than one alternative for the
same question, or does not mark any alternative. In such cases, the answer to the question
should be disregarded.
Professor John now needs a volunteer to write one program that, given the average
gray level values of the five rectangles corresponding to the alternatives
of a question, determines which alternative was marked, or whether the answer to
the question should be disregarded.
Input
The first line of a input contains an integer `N` indicating
the number of questions in the answer sheet (`1\ ≤\ N\ ≤\ 255`).
Each of the `N` following lines describes the response to a question and contains five
integers `A`, `B`, `C`, `D` and `E`, indicating the values of average gray levels for
each alternative (`0\ ≤\ A,\ B,\ C,\ D,\ E\ ≤\ 255`).
Output
Your program must print `N` lines, each line corresponding to a question.
If the answer to the question was correctly filled in the answer sheet, the line
should contain the alternative selected ('A', 'B', 'C', 'D' or 'E').
Otherwise, the line should contain the character '*' (asterisk).
Sample Input
7 0 255 255 255 255 255 255 255 255 0 255 255 127 255 255 200 200 200 0 200 200 1 200 200 1 1 2 3 4 5 255 5 200 130 205
Sample Output
A E C D * * B
J. Just Prune The List
Быстрая сортировкаСлияние упорядоченных последовательностей
Олимпиадные задачи на английском языке
| 01/10/2011 | Личное первенство Южного Урала (J) |
| 22/07/2016 | Лето 2016 - 14 (H) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
You are given two list of integers. You can remove any number of elements
from any of them. You have to ensure that after removing some elements both of the list will
contain same elements, but not necessarily in same order. For example consider the following two lists
List #1: 1 2 3 2 1
List #2: 1 2 5 2 3
After removing 1 from first list and 5 from second list, both lists will contain same elements.
We will find the following lists after removing two elements.
List #1: 1 2 3 2
List #2: 1 2 2 3
What is the minimum number of elements to be removed to obtain two list having same elements?
Input
First line will contain two integers `N` (`1\ ≤\ N\ ≤\ 100000`), the number of element in the
first list and `M` (`1\ ≤\ M\ ≤\ 100000`), the number of element in the second list.
The next line will contain `N` integers representing the first list followed by another
line having `M` elements representing the second list. Each integers in the input is 32 bit signed integer.
Output
Output a single line containing the number of elements to be removed.
Sample Input
5 5 1 2 3 2 1 1 2 5 2 3
Sample Output
2
