Задачи открытого командного чемпионата 2002

1. Экзамен

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

ля получения водительских прав Фраю необходимо продемонстрировать экзаменатору свои навыки управления автолетом. Автолет – это низко летящее транспортное средство, широко распространенное в 3000 году. При движении по прямой автолет не требует внимания водителя, автоматически избегает столкновений и соблюдает правила движения. Водитель управляет автолетом только на поворотах, задавая направление дальнейшего движения. Для сдачи экзамена Фраю необходимо проехать на прямоугольном учебном полигоне из точки А в точку Б, при этом возможно только движение в направлениях, параллельных сторонам полигона. Фраю хочется сдать экзамен, затратив минимальные усилия, и он выбирает путь из А в Б с минимальным количеством поворотов, а не самый короткий.

Во входном файле в первой строке содержатся два целых числа, разделенных пробелом – размеры полигона `N` и `M` (`1\ <\ N\ ≤\ 100`, `1\ <\ M\ ≤\ 100`). В следующей строке содержатся четыре целых числа, разделенных пробелом – координаты начальной и конечной точки `x_{A}`, `y_{A}`, `x_{Б}`, `y_{Б}` (`1\ ≤\ x_{А}\ ≤\ M`, `1\ ≤\ y_{А}\ ≤\ N`, `1\ ≤\ x_{Б}\ ≤\ M`, `1\ ≤\ y_{Б}\ ≤\ N`). Далее следует `N` строк по `M` символов в строке – план полигона. Одна клетка на плане соответствует размерам автолета. Левый нижний угол плана полигона имеет координаты `(1,1)`. Препятствие обозначается символом '#', а свободное место – символом '.' (точка). Путь из А в Б по свободным клеткам всегда существует.

В выходной файл в первой строке вывести минимальное количество поворотов `P`, а затем `P` строк c координатами клеток, в которых необходимо выполнять повороты, в виде пары чисел, разделенных пробелом. Если существует несколько путей с минимальным количеством поворотов, нужно вывести один (любой) из них.

Пример ввода

5 5
1 5 5 1
....#
....#
....#
.#...
.#...

Вывод для примера

2
3 5
3 1

2. Матрица

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

рофессор Хьюберт Дж. Фарнсворт, пра-пра-…правнучатый племянник Фрая, изобрел “кубитовую матрицу”, состоящую из элементов трех типов: увеличителя (увеличивающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо), уменьшителя (уменьшающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо) и сохранителя (передающего значение, полученное сверху или слева, без изменений соответственно вниз или вправо). При подаче на входы кубитовой матрицы одинаковых значений на выходах все значения будут различны. Профессор, используя свой недюжинный интеллект, сумел без помощи компьютера построить кубитовые матрицы размером `2\ times\ 2` и `4\ times\ 4`. Напишите программу, которая поможет профессору построить матрицы большего размера.

В первой строке входного файла содержится целое четное число `N` (`2\ ≤\ N\ ≤\ 200`) – размеры кубитовой матрицы, которую нужно построить.

В выходной файл вывести кубитовую матрицу – `N` строк по `N` символов. Для обозначения увеличителя используйте символ ‘+’ (плюс), уменьшителя – символ ‘–‘ (минус), сохранителя – символ ‘0’ (нуль). Так как существует несколько вариантов кубитовой матрицы заданного размера, образуемых перестановкой строк и столбцов матрицы, то нужно вывести один (любой) из них.

Пример ввода

Вывод для примера

0+++
++++
--00
---0

3. Доставка посылки

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

чередную посылку команде “Планетарной экспресс-доставки” пришлось доставлять на планету Хичкок, сплошь покрытую острыми скалами. Корабль приземлился на небольшом плато немного в стороне от почтового ящика. Путь между кораблем и ящиком пролегал по вершинам острых скал, и опасную миссию по доставке посылки большинством голосов (Лила и Фрай – за, Бендер – против) поручили Бендеру. Бендер должен допрыгать по вершинам скал до почтового ящика и вернуться обратно. Так же, как и Фрай, Бендер всегда стремится минимизировать свои усилия при выполнении любой работы, поэтому требуется найти способ сделать это за минимальное количество прыжков. Бендер может с большой точностью регулировать угол (направление) прыжка, но механизм регулировки силы прыжка из-за проглоченных накануне часов Лилы не работает. Таким образом, начальная скорость Бендера в момент прыжка всегда постоянна и равна `V` м/с. Ускорение свободного падения на планете Хичкок равно 10 м/с`^2`, а сопротивлением воздуха можно пренебречь. Прыжок со скалы на скалу считается успешно выполненным, только если траектория полета приводит Бендера точно на вершину скалы, и он не сталкивается в полете с другими скалами, иначе Бендер может разбиться или застрять между двумя скалами. Напишите программу, которая рассчитает путь Бендера до ящика и обратно.

Во входном файле в первой строке содержатся два целых числа, разделенных пробелом – количество скал `N` и скорость `V` (`2\ ≤\ N\ ≤\ 1000`, `1\ ≤\ V\ ≤\ 100`). Далее следует `N` строк с параметрами скал, по два целых числа в строке – расстояние от скалы до корабля `X_i` в метрах и высота скалы `H_i` в метрах (`0\ =\ X_1\ <\ X_2\ <\ …\ <\ X_N\ ≤\ 100000`, `10\ ≤\ H_i\ ≤\ 10000`, `1\ ≤\ i\ ≤\ N`). Бендер находится на первой скале, а почтовый ящик на `N`-й.

В выходной файл в первой строке вывести минимальное количество прыжков, необходимое для выполнения миссии, а во второй строке – номера скал, на которые совершаются прыжки, разделенные одним пробелом. Если существует несколько вариантов, то вывести один (любой) из них. Если выполнение миссии невозможно, то вывести в первой строке сообщение "MISSION IMPOSSIBLE" (без кавычек).

Пример ввода

Вывод для примера

4
3 6 5 1

4. Формовка

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

ила решила для увеличения эффективности ракетного топлива придать ему с помощью специальной машины другую форму, отличную от шарообразной. Основными элементами этой машины являются два колеса, имеющими на внешнем ободе соответствующие форме продукта канавки и выпуклости. Чтобы результат формовки не застрял в машине, профиль колес не должен иметь элементов, наклоненных к поверхности обода более чем на 90 градусов. Для определения профиля формовочных колес достаточно рассмотреть плоскость, проходящую через оси колес, и свести задачу к двумерной. Проведя прямую через многоугольник, задающему поперечный профиль результата, нужно разделить его на две части, определяющие профиль колес. Напишите программу, которая по многоугольнику, задающему требуемый поперечный профиль для ракетного топлива, определяет возможность формовки с помощью этой машины и профиль формовочных колес.

Во входном файле в первой строке содержится число `N` (`3\ ≤\ N\ ≤\ 50`) – количество углов многоугольника, не имеющего самопересечений. Далее следует `N` строк, содержащие по два целых числа через пробел, – координаты вершин многоугольника `X_i` и `Y_i` (`0\ ≤\ X_i\ ≤\ 1000`, `0\ ≤\ Y_i\ ≤\ 1000`, `1\ ≤\ i\ ≤\ N`), в порядке обхода их по часовой или против часовой стрелки.

В выходной файл вывести три целых числа `A`, `B`, `C` через пробел – параметры прямой `"Ax"+"By"+C=0`, по которой можно разделить многоугольник на две части, определяющие профиль колес. Если существует несколько вариантов, то вывести один (любой) из них. Если разделение невозможно, вывести слово "IMPOSSIBLE" (без кавычек).

Пример ввода

Вывод для примера

1 0 –30

5. Сортировка

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

тудентка Марсианского университета Эми изучает в рамках курса “Архаические БД и ЭС” пакет TopSpeed’s Clarion`™` for Windows`™`, который появился на заре компьютерной эры и основывался на широком использовании настраиваемых шаблонов для быстрой разработки программ, а не объектно-ориентированного подхода, который появился в то же время. Как и в большинстве других языков программирования, программа на языке Clarion состоит из набора ключевых и резервированных слов, чисел, строковых констант, скобок, знаков операций и других лексем. Регистр букв в ключевых и резервированных словах и идентификаторах игнорируется. Между лексемами можно вставлять произвольное количество пробелов. Конец строки завершает оператор. Слишком длинный оператор можно разбивать на несколько строк, указывая последним символом в строке символ продолжения ‘|’ (вертикальная черта), но лексему при этом нельзя разбивать на две части. Строковые константы заключаются в апострофы, а апострофы в строке удваиваются, например, ‘It’’s a string’. Элементы окна или отчета описываются в программе в следующем виде:

тип_элемента[(параметры)],AT(`X`, `Y`[,[`W`],[`H`]])[, свойство[(параметры)]]…

В качестве параметров могут быть указаны строки (или конкатенация строк), числа, форматы, идентификаторы переменных. Свойство AT задает координаты `X` и `Y` элемента (координаты являются целыми числами в диапазоне от 0 до 10000), а также, возможно, его ширину `W` и высоту `H`. Описание других свойств элемента имеет аналогичную форму. Для редактирования окон и отчетов в пакете применяются специальные визуальные редакторы, генерирующие необходимые описания. При работе с пакетом Эми обнаружила, что порядок описаний элементов в структуре окон и отчетов зависит от порядка добавления элементов в редакторе. Это является существенным недостатком, если требуется скопировать некоторую связанную группу элементов в другое окно или отчет. Напишите программу, выполняющую сортировку описаний элементов по возрастанию координаты `Y`, а затем `X`. При совпадении `Y` и `X` оставить описания элементов в порядке их следования во входном файле.

Во входном файле содержится от 1 до 1000 строк длиной не более 80 символов – набор синтаксически корректных описаний элементов окна или отчета. Некоторые описания могут быть разбиты на несколько строк (не более 10 строк).

В выходной файл вывести упорядоченные по возрастанию координаты `Y`, а затем `X` описания элементов, при этом содержание строк не должно измениться, только их порядок.

Пример ввода

    STRING('(описание вып. работ, оказанных услуг)'),AT(2,84,|
      62,5),FONT(,8,,),USE(?String29:2),TRN,CENTER,#ORIG(?String29)
    LINE,AT(29,68,227,0),USE(?Line24),COLOR(00H),#ORIG(?Line24)
    STRING(@s50),AT(136,69,106,6),USE(GLB_OPLSPB),TRN,#ORIG(GLB_OPLSPB)
    STRING('Сумма налога'),AT(168,84),FONT(,8,,),USE(?String94),|
      TRN,#ORIG(?String94)

Вывод для примера

    LINE,AT(29,68,227,0),USE(?Line24),COLOR(00H),#ORIG(?Line24)
    STRING(@s50),AT(136,69,106,6),USE(GLB_OPLSPB),TRN,#ORIG(GLB_OPLSPB)
    STRING('(описание вып. работ, оказанных услуг)'),AT(2,84,|
      62,5),FONT(,8,,),USE(?String29:2),TRN,CENTER,#ORIG(?String29)
    STRING('Сумма налога'),AT(168,84),FONT(,8,,),USE(?String94),|
      TRN,#ORIG(?String94)

6. Слова и числа

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

лавный бюрократ компании "Планетарная экспресс-доставка" Гермес Конрад после написания очередного отчета или распоряжения обязательно подсчитывает количество слов и чисел в документе, так как владелец компании, профессор Х.Дж.Фарнсворт, не любит лишних слов, а любит только числа. Напишите программу, которая поможет Гермесу подсчитать количество слов и чисел в документе.

Во входном файле содержится от 1 до 100 строк длиной не более 80 символов. Словом или числом будем называть непрерывную последовательность печатных символов. При этом число в отличие от слова содержит одну или более цифр от 0 до 9. Слова и числа в документе разделены последовательностями пробелов, табуляций и переходов на новую строку.

В выходной файл вывести количество слов и чисел в документе в виде "2 word(s), 1 number(s)".

Пример ввода

                REPORT
In 1st quarter the margin was $20.02.

Вывод для примера

6 word(s), 2 number(s)

7. Slurpys

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

r. Zoidberg is a ET.

A Slurpy is a word in his language that has certain properties.

Your program will read in strings of characters and output whether or not they are Slurpys.

A Slump is a character string that has the following properties:

Its first character is either a 'D' or an 'E'.
The first character is followed by a string of one or more 'F's.
The string of one or more 'F's is followed by either a Slump or a 'G'. The Slump or 'G' that follows the F's ends the Slump. For example 'DFFEFFFG' is a Slump since it has a 'D' for its first character, followed by a string of two 'F's, and ended by the Slump 'EFFFG'.
Nothing else is a Slump.

A Slimp is a character string that has the following properties:

Its first character is an 'A'.
If it is a two character Slimp then its second and last character is an 'H'.
If it is not a two character Slimp then it is in one of these two forms:
a) 'A' followed by 'B' followed by a Slimp followed by a 'C'.
b) 'A' followed by a Slump (see above) followed by a 'C'.
Nothing else is a Slimp.

A Slurpy is a word that consists of a Slimp followed by a Slump.

Examples

Slumps: DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG

Not Slumps: DFEFF, EFAHG, DEFG, DG, EFFFFDG

Slimps: AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC

Not Slimps: ABC, ABAH, DFGC, ABABAHC, SLIMP, ADGC

Slurpys: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG

Not Slurpys: AHDFGA, DFGAH, ABABCC

The first line of input contains an integer `N` between 1 and 10 describing how many strings of characters are represented. The next `N` lines each contain a string of 1 to 60 alpha characters.

Each of `N` lines of output should consist of either YES or NO depending on whether or not the corresponding input line is a Slurpy.

Input Sample

2
AHDFG
DFGAH

Output Sample

YES
NO

01/03/2002	Открытый командный чемпионат по программированию (1)
09/12/2010	Сборы 31 (5C)
09/12/2010	Сборы: Общий итог (5C)
06/01/2011	Сборы: Интернет-соревнование (C)
04/07/2011	Лето 2011 - дорешивание (06A)
11/07/2011	Лето 2011 - 6 (A)
30/06/2017	Лето 2017 (командное) - 4 (G)

01/03/2002	Открытый командный чемпионат по программированию (2)
04/07/2011	Лето 2011 - дорешивание (06B)
11/07/2011	Лето 2011 - 6 (B)
30/06/2017	Лето 2017 (командное) - 4 (D)
01/07/2020	Летние сборы - 2 (C)

01/03/2002	Открытый командный чемпионат по программированию (3)
04/07/2011	Лето 2011 - дорешивание (06C)
11/07/2011	Лето 2011 - 6 (C)

01/03/2002	Открытый командный чемпионат по программированию (4)
04/07/2011	Лето 2011 - дорешивание (06D)
11/07/2011	Лето 2011 - 6 (D)

01/03/2002	Открытый командный чемпионат по программированию (5)
04/07/2011	Лето 2011 - дорешивание (06E)
11/07/2011	Лето 2011 - 6 (E)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задачи открытого командного чемпионата 2002

1. Экзамен

2. Матрица

3. Доставка посылки

4. Формовка

5. Сортировка

6. Слова и числа

7. Slurpys