Начало
Соревнования
Задачи очного тура личного первенства университета 2002
1. Снежный ком
Поиск в ширину (BFS)Деревья (map, set), хэш-таблицы
Олимпиадные задачи на русском языке
| 04/10/2002 | Личное первенство университета по программированию (1) |
| 10/10/2007 | Занятие 5 (задачи личного первенства 2002г) (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Фраза, которая начинается со слова из одной буквы, и в которой каждое слово на одну букву длиннее предыдущего, называется "снежным комом". Вот великолепный пример снежного кома из 20 английских слов: "I do not know where family doctors acquired illegibly perplexing handwriting; nevertheless, extraordinary pharmaceutical intellectuality, counterbalancing indecipherability, transcendentalizes intercommunications' incomprehensibleness."
Для получения случайного осмысленного текста можно использовать следующий алгоритм. Возьмем произвольный большой текст. Взяв в качестве первого слова любое слово из этого текста, следующим ставим слово, которое расположено где-нибудь в исходном тексте непосредственно после выбранного слова. Если есть несколько кандидатов, случайно выбираем любого из них. Аналогично третьим ставим слово, которое расположено в исходном тексте непосредственно после второго выбранного слова. И так далее.
Напишите программу, которая выделяет максимально длинный "снежный ком" из большого текста по указанному выше алгоритму.
Во входном файле содержится одна или более строк длиной не более 200 символов, в которых содержится текст, состоящий не более чем из 30000 слов. Количество различных слов в тесте не превышает 5000. Максимальная длина слов не превышает 20 букв. Текст состоит из латинских букв и знаков препинания. Регистр букв при составлении снежного кома игнорируется. Словом будем называть последовательность прописных и строчных латинских букв ("x-ray" состоит из 2 слов X и RAY, "Mary's" состоит из 2 слов MARY и S, "It's words" состоит из 3 слов IT, S и WORDS).
В выходной файл вывести самый длинный снежный ком, найденный в тексте. Снежный ком не должен содержать знаков препинания, а слова, напечатанные строчными буквами, должны отделяться друг от друга одним пробелом. Если существует несколько подходящих вариантов, вывести один (любой) из них.
Пример ввода
Where family doctors study? I do not know where. Doctors acquired illegibly drugs from gypsies. You received F mark for illegibly perplexing handwriting.
Вывод для примера
i do not know where family doctors acquired illegibly perplexing handwriting
2. HTML
АвтоматыОлимпиадные задачи на русском языке
| 04/10/2002 | Личное первенство университета по программированию (2) |
| 10/10/2007 | Занятие 5 (задачи личного первенства 2002г) (B) |
| 29/05/2010 | Занятие 13 (B) |
| 12/03/2014 | Занятие 16 (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для опубликования текста задач этих соревнований в сети необходимо преобразовать текст в HTML-формат. Использование стандартного конвертера пакета MS Word привело бы к сложным и большим по объему страницам, но которые в точности соответствуют исходным документам. Если не требовать точного соответствия исходному документу, то следующие простые правила для преобразования текста позволят получить более компактные страницы.
- Тексты задач состоят из нескольких абзацев, каждый из которых записан на отдельной строке. Каждый абзац должен быть также записан на отдельной строке и окружен тегами <p> и </p>.
- В тексте могут встречаться обозначения, которые необходимо преобразовать в специальные HTML-коды. Символ "<" нужно записать в выходном файле как "<", символ ">" – как ">", а символ "&" – как "&". Последовательность символов "<=" – как "≤", ">=" – как "≥", а "/=" – как "≠".
- В тексте могут встретиться имена параметров задачи, которые обычно выделяются курсивом. Однобуквенные имена, например, "n" нужно записать в выходной файл как "<i>n</i>", а состоящие из нескольких букв, например, "aij" – как "<i>a<sub>ij</sub></i>".
Напишите программу для преобразования текста в HTML-формат.
Во входном файле в первой строке находится целое число `n` (`0\ ≤\ n\ ≤\ 50`). Далее следует `n` строк с именами параметров задачи, которые будут выделяться в тексте курсивом. Имена состоят из 1-3 латинских букв. Регистр букв является существенным, символы слева и справа от имен в тексте не являются латинскими буквами. Далее следует одна или более строк с текстом. В тексте могут встречаться русские и латинские буквы, знаки препинания и другие символы.
В выходной файл вывести преобразованный текст.
Пример ввода
3 M S n The first line of the input contains two integers M and S, separated by space. The following M lines contain a single integer n in a line (0<=n<=10000).
Вывод для примера
<p>The first line of the input contains two integers <i>M</i> and <i>S</i>, separated by space.</p> <p>The following <i>M</i> lines contain a single integer <i>n</i> in a line (0≤<i>n</i>≤10000).</p>
3. Упрощение номеров
Системы счисления с другим основаниемПолный перебор
Олимпиадные задачи на русском языке
| 04/10/2002 | Личное первенство университета по программированию (3) |
| 01/09/2007 | Основы программирования. Системы счисления (10) |
| 10/10/2007 | Занятие 5 (задачи личного первенства 2002г) (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Как, Вы не можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на экране телевизора?! С помощью специальной методики, описываемой далее, Вы превратитесь в ходячий телефонный справочник!
Очевидно, что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы в числе было как можно больше повторяющихся цифр. В качестве критерия сложности запоминания примем сумму количества цифр в числе и количества различных цифр в числе. Запоминаемое число можно записать в другой системе исчисления, возможно, тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной системе исчисления выглядит как FFFF. Таким образом, нужно подобрать основание системы исчисления для минимизации критерия сложности. Основание системы исчисления нужно выбирать в диапазоне от 2 до 36, тогда для представления числа можно использовать цифры 0-9 и латинские буквы A-Z.
Во входном файле в первой строке содержится целое число `n` (`1\ ≤\ n\ ≤\ 1000`). Далее следует `n` строк, каждая строка содержит целое число от 1 до 999999999.
В выходной файл для каждого числа вывести на отдельной строке основание системы исчисления (от 2 до 36), минимизирующее критерий сложности запоминания, и число в выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований дают одинаковое значение критерия, то выбрать наименьшее среди них.
Пример ввода
2 2 65535
Вывод для примера
3 2 16 FFFF
4. Secret Research
Задачи на идеюРазбор случаев
Олимпиадные задачи на английском языке
| 04/10/2002 | Личное первенство университета по программированию (4) |
| 10/10/2007 | Занятие 5 (задачи личного первенства 2002г) (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
At a certain laboratory results of secret research are thoroughly encrypted. A result of a single experiment is stored as an information of its completion: 'positive result', 'negative result', 'experiment failed' or 'experiment not completed'.
The encrypted result constitutes a string of digits S, which may take one of the following forms:
- positive result S = 1 or S = 23 or S = 2S3
- negative result S = 51S
- experiment failed S = 5S
- experiment not completed S = 2S1 or S = 24S
(A sample result 51S means that if we add digits 51 from the left hand side to a digit sequence then we shall get the digit sequence corresponding to a failed experiment)
You are to write a program which decrypts given sequences of digits.
Input
A integer `n` stating the number of encrypted results and then consecutive `n` lines, each containing a sequence of digits given as ASCII strings.
Output
For each analysed sequence of digits the following lines should be sent to output (in separate lines):
| + | for a positive result |
| - | for a negative result |
| * | for a failed experiment |
| ? | for a not completed experiment |
Sample Input
4 23 5123 222331 523
Sample Output
+ - ? *
