Задачи командных соревнований областной олимпиады школьников по информатике 2003

1. Последовательность

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

Последовательность строится следующим образом `S_0=X`, `S_1=Y`, `S_i=A*S_{i-1}+B*S_{i-2}`. Найдите остаток от деления `S_k` на `M`.

Во входном файле в первой строке содержатся четыре целых числа, разделенных пробелами – два первых элемента последовательности `X` и `Y` и коэффициенты `A` и `B` (`0\ ≤\ X\ ≤\ 1000`, `0\ ≤\ Y\ ≤\ 1000`, `0\ <\ A\ ≤\ 1000`, `0\ <\ B\ ≤\ 1000`). Во второй строке входного содержатся два целых числа, разделенных пробелом – номер элемента последовательности `k` и число `M` (`0\ ≤\ k\ ≤\ 10^9`, `2\ ≤\ M\ ≤\ 100`).

В выходной файл вывести одно целое число – остаток от деления `S_k` на `M`.

Пример ввода

0 1 2 1
7 10

Пример вывода

2. Магический квадрат

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

0	13	7	20
–9	4	–2	11
12	25	19	32
3	16	10	23

Квадрат на этом рисунке обладает интересным магическим свойством. Выберите любое из чисел, вписанных в клетки квадрата, и обведите кружком. Вычерните все числа, стоящие в той же самой строке и столбце, что и выбранное число. Снова выберите число из еще не вычеркнутых или не обведенных чисел и обведите его кружком, и снова вычерните числа, стоящие в той же строке и столбце, что и выбранное во второй раз число. Проделайте эту процедуру в третий раз, получив третье число. Обведите кружком оставшееся четвертое число. Сложите все четыре числа, обведенных кружком. Их сумма будет равна 46. Сколько бы вы раз не повторяли эксперимент, сумма всегда будет одной и той же, равной 46 – сумме чисел на диагонали квадрата.

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

Напишите программу, которая по числам, расположенным на главной диагонали квадрата, строит квадрат, обладающий указанным магическим свойством.

Во входном файле в первой строке содержится целое число `N` (`1\ <\ N\ ≤\ 100`) – размер квадрата, далее следует `N` строк; `(i+1)`-я строка (`1\ ≤\ i\ ≤\ N`) содержит одно целое число `a_"ii"` (`|a_"ii"|<1000`) – число, которое должно быть на главной диагонали магического квадрата. Все числа, расположенные на диагонали квадрата, различны.

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

Пример ввода

Пример вывода

0 13 7 20
-9 4 -2 11
12 25 19 32
3 16 10 23

3. Спрятанный текст

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

Недавно стало известно, что в романе "Война и мир" Л.Н.Толстой зашифровал много важных предсказаний, касающихся событий 20 и 21 века. Например, в 1 главе первого тома можно обнаружить слова, произнесенные Нилом Армстронгом, когда он ступил на Луну: "One small step for man, one giant leap for mankind". Для этого нужно взять 22 букву из 1 строки (O), затем 17 и 24 буквы из 2 строки (N и E), затем … Конечно, это шутка: если взять достаточно длинный текст, то можно найти любые требуемые сообщения. Хотя есть люди, которые ищут и находят предсказания, скрытые в библейских текстах.

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

Первая строка входного файла содержит от 2 до 100 прописных русских букв – это текст, который нужно найти. Во второй строке содержится последовательность прописных русских букв, в которой нужно найти спрятанный текст. Длина второй строки от 2 до 1000 букв.

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

Пример ввода

ТАЙНА
СПРЯТАННЫЙТЕКСТЗДЕСЬНЕНАЙТИ

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

5 6 10 23 24

4. Сокращение строки

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

Возьмем строку не более 255 букв, состоящую только из латинских букв a и b. Можно выполнять сокращение строки по следующему правилу: подстрока a#a или b#b, где символ # обозначает одну произвольную букву a или b, может быть сокращена до подстроки #. Требуется получить строку минимальной длины после нескольких таких сокращений. Например, из строки aaaaaab можно получить строку aab.

Напишите программу, которая определяет минимально возможную длину строки после выполнения сокращений.

Входной файл содержит начальную строку.

В выходной файл вывести одно целое число – минимальную длину конечной строки.

Пример ввода

aaaaaab

Пример вывода

5. Прогулка

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

Теплым солнечным днем Петя и Маша гуляли вместе по полям. Становилось поздно и, конечно же, они заблудились. Маша была немного напугана, но Петя успокоил ее: на этот случай они хорошо подготовились – Петя взял с собой карту и компас.

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

Известны координаты двух выбранных объектов и направление (угол от севера) между этими объектами. Написать программу, которая, используя эти данные, вычисляет координаты текущего местоположения Маши и Пети.

Во входном файле содержится две строки. В первой строке описывается первый объект, во второй – второй. Каждый объект описывается строчкой, содержащей три целых числа:

`х` – координата объекта на карте (`0\ ≤\ х\ ≤\ 100`). Ось абсцисс соответствует направлению запад-восток на карте с увеличивающимися значениями к востоку.
`y` – координата объекта на карте (`0\ ≤\ у\ ≤\ 100`). Ось ординат соответствует направлению юг- север на карте с увеличивающимися значениями к северу.
Направление `d` на объект в градусах (`0\ ≤\ d\ <\ 360`). `0°` соответствует северу, `90°` – востоку, `180°` – югу, `270°` – западу.

Чтобы выполнить вычисление позиции точно, Петя каждый раз убеждался, что он с Машей не находятся на прямой, проходящей через объекты, используемые в качестве ориентиров.

Выходной файл содержит одну строку – результат вычисления местоположения: два числа, отделенные друг от друга пробелом. Каждое число имеет 4 цифры после десятичной точки. Эти числа представляют `х` и `у` координаты местоположения Пети и Маши (`0\ ≤\ х\ ≤100`, `0\ ≤\ у\ ≤\ 100`).

Пример ввода

30 50 90
20 40 180

Пример вывода

20.0000 50.0000

Источник: ACM ICPC NWERC 2002

6. Тестирование

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

Для крупной строительной фирмы была написана программа "TILE", которая выдавала варианты замощения пола прямоугольных комнат декоративной плиткой разного размера.

Напишите программу, которая проверяет результаты работы разработанной программы "TILE", выясняя для каждого выданного ей варианта наличие ошибок замощения пола:

плитки накладываются друг на друга;
плитки лежат вне комнаты;
плитки не полностью покрывают пол комнаты.

Входной файл с результатами работы тестируемой программы содержит несколько комнат. Первая строка задает число комнат. Каждая комната описывается несколькими строчками входного файла. Первая строка содержит два положительных целых числа: длину и ширину комнаты в миллиметрах. Максимальные размеры комнаты `40\ 000` на `40\ 000` мм. Следующая строка содержит единственное число `t` – количество плиток, используемых для замощения (`1\ ≤\ t\ ≤\ 100`). Следующие `t` строк описывают каждую плитку. Размещение плитки задается 4 целыми числами: `x_1\ y_1\ x_2\ y_2`, где `(x_1,y_1)` координаты нижнего левого угла плитки, `(x_2,y_2)` координаты верхнего правого угла плитки (`-100\ 000\ ≤\ x_1\ <\ x_2\ ≤100\ 000,\ -100\ 000\ ≤\ y_1\ <\ y_2\ ≤\ 100\ 000`).

Выходной файл для каждой комнаты должен содержать единственную строку, содержащую одно из следующих слов:

`NONDISJOINT`	если встречаются перекрывающиеся плитки;
`NONCONTAINED`	если нет перекрывающихся плиток, но некоторые плитки выходят за пределы комнаты;
`NONCOVERING`	если нет перекрывающихся плиток и нет плиток, выходящих за пределы комнаты, но некоторая часть комнаты не покрыта;
`OK`	если ошибок в замощении нет.

Пример ввода

Пример вывода

NONDISJOINT
NONCONTAINED
NONCOVERING
OK

Источник: ACM ICPC NWERC 2002

10/01/2003	Областная олимпиада школьников по информатике (командные соревнования) (1)
03/10/2013	Занятие 5 для начинающих (D)
28/06/2017	Лето 2017 - 2 (C)

10/01/2003	Областная олимпиада школьников по информатике (командные соревнования) (2)
24/04/2010	Занятие 12 (D)
07/10/2015	Занятие по теме "Задачи на идею" (C)
01/07/2020	Летние сборы - 2 (A)
14/07/2023	Лето 2023-9 (командное) (E)

10/01/2003	Областная олимпиада школьников по информатике (командные соревнования) (3)
24/10/2007	Занятие 7 (A)
26/12/2008	Подготовка к олимпиаде. Занятие 3. Последовательности символов, массивы (4)
19/11/2011	Занятие 6 (D)
30/04/2014	Занятие 23 (A)
30/06/2017	Лето 2017 (1 курс, командное) - 2 (D)
02/07/2021	Лето 2021-3 (командное) (H)
01/07/2022	Лето 2022-3 (командное) (E)

10/01/2003	Областная олимпиада школьников по информатике (командные соревнования) (4)
19/11/2010	Занятие 10 (G)
30/06/2017	Лето 2017 (1 курс, командное) - 2 (C)

10/01/2003	Областная олимпиада школьников по информатике (командные соревнования) (5)
25/06/2012	1 курс, дорешивание (5F1)
29/06/2012	1 курс, день 5, группа 1 (F1)
02/07/2014	Лето 2014 1 курс (20)
30/06/2017	Лето 2017 (1 курс, командное) - 2 (B)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи командных соревнований областной олимпиады школьников по информатике 2003

1. Последовательность

2. Магический квадрат

3. Спрятанный текст

4. Сокращение строки

5. Прогулка

6. Тестирование