Начало
Соревнования
Задачи очного тура личного первенства 1998
1. Анаграмма в квадрате
Поразрядная сортировка и сортировка подсчетомОбработка строк
Олимпиадные задачи на русском языке
| 23/10/1998 | Личное первенство университета по программированию (1) |
Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Слово является анаграммой другого слова, если оно состоит из
тех же самых букв в том же самом количестве, расположенных в другом
порядке (например, слова sword и words). Анаграммами в квадрате будем называть два предложения, которые состоят из одинаковых слов или
их анаграмм.
Словом будем называть последовательность прописных и строчных
латинских букв (до 30 символов). Регистр букв игнорируется.
x-ray состоит из 2 слов X и RAY
Mary's состоит из 2 слов MARY и S
It's words состоит из 3 слов IT, S и WORDS
Прочие символы при определении анаграмм в квадрате игнорируется.
Входной файл содержит от 2 до 20 строк длиной до 80 символов,
каждая из которых содержит одно предложение.
В выходной файл вывести все предложения, которые имеют
анаграммы в квадрате, в том же порядке, в котором они содержатся во
входном файле. Если таких предложений нет, вывести сообщение "NO ANAGRAM".
Пример ввода
No one post words. Neo stops no word. Sword stop on one! Stop on neon words?
Пример вывода
No one post words. Sword stop on one!
2. "Обходимые" числа
Полный переборОлимпиадные задачи на русском языке
| 23/10/1998 | Личное первенство университета по программированию (2) |
| 04/07/2011 | Лето 2011 - дорешивание (05A) |
| 08/07/2011 | Лето 2011 - 5 (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
`N`-значным обходимым числом будем называть целое число из `N`
различных цифр от 1 до 9, которое можно обойти по следующим
правилам. Обход начинается с левой цифры, эта цифра показывает,
сколько мы должны отсчитать цифр слева направо до следующей цифры,
которая будет использована для следующего отсчета, и так далее. При
необходимости переходим с правого края числа на левый. Обход
заканчивается, если пройдены все цифры по одному разу и мы дошли
снова до самой левой цифры.
Например, таким числом является 81362. Стартуем с цифры 8,
отсчитывая 8 цифр, доходим до 6 (при этом переходим с правого края
числа на левый), отсчитывая 6 цифр, доходим до 2, затем до 1, 3, и
наконец снова попадаем на 8.
Во входном файле находится от 1 до 10 строк с одним целым
числом `R` в строке. Число `R` содержит от 2 до 7 цифр. Для каждого
такого числа найти наименьшее обходимое число равное или большее `R`.
Входные данные подобраны так, чтобы такое число существовало.
Входной файл заканчивается строкой с 0.
Пример ввода
12 123 1234 81111 82222 83333 911111 7654321 0
Пример вывода
13 147 1263 81236 83491 83491 913425 8124956
3. Космическая станция
Рекурсивный переборЖадные алгоритмы
Олимпиадные задачи на русском языке
| 23/10/1998 | Личное первенство университета по программированию (3) |
| 24/10/2007 | Занятие 7 (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На международной космической станции много центрифуг в каждой
лаборатории. Каждая центрифуга имеет несколько (`N`) отделений, в
каждое из которых можно поместить 0, 1 или 2 образца. Вы должны
написать программу, которая позволит разместить `M` образцов по
отделениям центрифуги, таким образом, чтобы число образцов в
отделении не превышало 2 и следующее выражение для IMBALANCE было
минимальным:
`N`
IMBALANCE = `∑` `|\ "МО"_i\ -\ "СМ"\ |`
`i=1`
где `MО_i` – это масса `i`-го отделения, равная сумме масс образцов в
`i`-ом отделении
`СM` – это средняя масса отделения и равна сумме масс всех
образцов, деленной на число отделений (`N`).
Входной файл содержит несколько наборов данных. Первая строка
каждого набора содержит два числа, разделенных пробелом. Первое
число `N` (`1\ ≤\ N\ ≤\ 5`) определяет число отделений в центрифуге, а второе
число `M` (`1\ ≤\ M\ ≤\ 2*N`) определяет число образцов. Вторая строка
содержит `M` чисел (от 1 до 1000), разделенных пробелом,
представляющие массы образцов. Ввод завершается строкой с двумя
нулями.
В выходной файл для каждого набора вы должны напечатать строку
с номером набора в формате "Set #`X`" где `X` – номер набора, нумерация
начинается с 1. Следующие `N` строк содержат номер отделения в первой
колонке, двоеточие во второй колонке и массы образцов, начиная с
четвертой колонки, разделенных одним пробелом. Далее ваша программа
должна напечатать значение IMBALANCE с точностью 5 знаков после
запятой (т.е. десятичной точки). После результатов для каждого
набора (в т.ч. и самого последнего) вывести пустую строку.
Пример ввода
2 3 6 3 8 3 5 51 19 27 14 33 5 9 1 2 3 5 7 11 13 17 19 0 0
Вывод для примера
Set #1 1: 3 6 2: 8 IMBALANCE 1.00000 Set #2 1: 14 33 2: 19 27 3: 51 IMBALANCE 6.00000 Set #3 1: 1 17 2: 2 13 3: 3 11 4: 5 7 5: 19 IMBALANCE 11.60000
4. Пути-дороги
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 23/10/1998 | Личное первенство университета по программированию (4) |
| 28/11/2006 | Практическое занятие 12 (C) |
| 10/12/2013 | Занятие 11 для начинающих (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (2)
"Путь" – это игра для двоих игроков, которая ведется на доске `N` на `N` клеток. Два игрока "Белый" и "Черный" пытаются проложить дорогу из квадратиков своего цвета от одного своего края доски до другого (противоположного) края.
Вы должны написать программу, анализирующую состояние доски и определяющую, кто выиграл в игре или кто может выиграть следующим ходом, помещая квадратик своего цвета в незанятую клетку. Ход Белого является следующим в рассматриваемой позиции.
Доска представляется матрицей букв W, B и U, где W – это белые квадратики, B – черные, а U – незанятые клетки. Белый игрок должен соединять левый и правый края доски, а Черный – верхний и нижний края.
Соседними считаются клетки, расположенные на доске рядом по горизонтали или вертикали. Внутренняя клетка доски имеет 4 соседей, клетка на углу – 2 соседей, клетка на краю – 3 соседей.
Путь – это последовательность различных клеток `L_0,\ L_1,\ …,\ L_k`, таких, что `L_i` и `L_{i+1}` являются соседними для всех `i` от 0 до `k-1`. Выигрышный путь для игрока – это такой путь `L_0,\ \ L_1,\ …,\ L_k,` заполненный квадратиками игрока, что `L_0` находится на одном краю игрока, а `L_k` на другом краю игрока. Выигрышный путь одного игрока блокирует проведение выигрышного пути для другого игрока.
Ввод
Входной файл содержит несколько наборов данных. Каждый набор начинается со строки, содержащей размер доски `N` (0<`N`≤64). Далее следует `N` строк по `N` символов (W, B, U). Входной файл заканчивается строкой, содержащей 0.
Вывод
В выходной файл для каждого набора данных вы должны вывести одну из пяти строк:
- Белый выиграл.
- Черный выиграл.
- Белый может выиграть следующим ходом.
(помещая квадратик белого цвета в незанятую клетку)
- Черный может выиграть следующим ходом.
(если Белый не может выиграть следующим ходом, а Черный может при неправильном ходе Белого)
- Нет выигрыша.
(во всех остальных случаях)
Пример ввода
7 WBBUUUU WWBUWWW UWBBBWB BWBBWWB BWWBWBB UBWWWBU UWBBBWW 3 WBB WWU WBB 0
Пример вывода
Белый выиграл. Белый может выиграть следующим ходом.
При выводе можно использовать кодировку символов 1251 (windows) или 866 (dos).
Источник: ACM Pacific NW RC, 1997
5. What Day Is It?
Разбор случаевОлимпиадные задачи на английском языке
| 23/10/1998 | Личное первенство университета по программированию (5) |
Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
The calendar now in use evolved from the Romans. Julius Caesar
codified a calendar system that came to be known as the Julian
calendar. In this system, all months have 31 days, except for
April, June, September, and November, which have 30 days, and
February, which has 28 days in non-leap years, and 29 days in leap
years. Also, in this system, leap years happened every four years.
That is because the astronomers of ancient Rome computed the year
to be 365.25 days long, so that after every four years, one needed
to add an extra day to keep the calendar on track with the seasons.
To do this, they added an extra day (February 29) to every year
that was a multiple of four.
Julian Rule: Every year that is a multiple of 4 is a leap year,
i.e. has an extra day (February 29).
In 1582, Pope Gregory's astronomers noticed that the year was
not 365.25 days long, but closer to 365.2425. Therefore, the leap
year rule would be revised to the following:
Gregorian Rule: Every year that is a multiple of 4 is a leap
year, unless it is a multiple of 100 that is not a multiple of 400.
To compensate for how the seasons had shifted against the
calendar up until that time, the calendar was actually shifted 10
days: the day following October 4, 1582 was declared to be October
15.
England and its empire (including the United States) didn't
switch to the Gregorian calendar system until 1752, when the day
following September 2 was declared to be September 14. (The delay
was caused by the poor relationship between Henry VIII and the
Pope.)
Write a program that converts dates in the United States using
a calendar of the time and outputs weekdays. The input will be a
series of positive integers greater than zero, three integers per
line, which represent dates, one date per line. The format for a
date is "month day year" where month is a number between 1 (which
indicates January) and 12 (which indicates December), day is a
number between 1 and 31, and year is positive number. The output
will be the input date and name of the weekday on which the given
date falls in the format shown in the sample. An invalid date or
nonexistent date for the calendar used in the United States at the
time should generate an error message indicating a invalid date.
The input will end with three zeroes.
Sample Input
11 15 1997 1 1 2000 7 4 1998 2 11 1732 9 2 1752 9 14 1752 4 33 1997 0 0 0
Sample Output
Saturday Saturday Saturday Friday Wednesday Thursday Invalid date
Source: ACM Pacific NW RC, 1997
