Факультет математики и компьютерных наук, история

Задачи

Робот-минер новейшей конструкции способен провести разминирование местности, план которой должен быть представлен в виде прямоугольника с целыми длинами сторон n - высота прямоугольника, m - длина прямоугольника. Перед началом работы робота размещают перед левой верхней клеткой прямоугольника в направлении "слева - направо", после чего робот начинает обход и разминирование, двигаясь по спирали по часовой стрелке (см. рис.). При этом спираль постепенно "закручивается" вовнутрь, захватывая все клетки прямоугольника. Разминирование заканчивается, когда проверены все клетки.

Требуется написать программу, которая для заданных исходных данных определяет количество поворотов, которые должен выполнить робот в процессе разминирования.
Технические требования:
Имя входного файла: INPUT. TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит два целых числа, расположенных в одной строке в следующем порядке: n, m (1 < n, m<32767). Числа в строке разделены пробелами.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно целое значение - количество поворотов.
Пример файла входных и выходных данных:

2. "шыгревереП". атЭ ачадаз - яанноицидартен. ьседЗ ен о нас и пан, отч оннеми ыв ынжлод ьталедс с мындохси мывотскет молйаф, мищажредос еикснитал и еикссур ывкуб, а ежкат еигурд еынжомзов иканз (ырфиц, иканз яинаниперп и cte). ыМ окьлот мищбоос, отч ьседз доп моволс, мищажеддоп юинавозарбоерп, ястеаминоп ьтсоньлетаводелсоп хикснитал и хикссур (ациллирик) воловмис (омисивазен то артсигер), ясяащюавичнаказ обил моцнок икортс, обил моцнок алйаф, обил моловмис, мынчилто то ывкуб.
катИ, етишипан уммаргорп, яароток тедевирп тов йокат "йыннечропси" тскет к умоньламрон удив.

Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест
Формат входных данных: Входной файл содержит некоторый текст, содержащий не более 1000 строк, длина каждой из которых не превышает 255 символов. В тексте могут быть любые печатные символы.
Слово - это набор символов между разделителями. Разделителями в тексте могут быть пробелы, концы строк, знаки препинания, цифры.
Формат выходных данных: Выходной файл содержит закодированный текст.
Пример файлов входных и выходных данных:

3. "Магическая математика" В связи с новейшими исследованиями в области нетрадиционных наук в школе Хогварц появился новый предмет - магическая математика. На нем юных магов начали учить, как использовать математические знания дня колдовства.

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

Требуется оказать шефскую помощь ученикам школы Хогварца - написать программу, которая выполняет требуемые вычисления для любой заданной магической прямоугольной таблицы чисел.

Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на каждый тест
Формат входных данных:
Входной файл INPUT.TXT состоит из следующей последовательности строк. В первой строке записаны числа N и M (1 < N, M <= 100) - число строк и число столбцов в магической таблице. Затем в N строках описывается сама магическая таблица (элементы таблицы - целые числа, по модулю не превышающие 1000). В последующих строках содержатся описания прямоугольников внутри матрицы, сумму чисел в которых требуется посчитать: сначала идет строка с числом таких прямоугольников - К (1 < K <= 500000), после этого идут строки, задающие сами прямоугольники. Каждый прямоугольник задается в отдельной строке четырьмя числами - L, V, R, D, где (L, U) - координаты левой верхней клетки прямоугольника (сначала задается номер строки, затем - номер столбца), (R,D) - координаты правой нижней клетки прямоугольника. Столбцы нумеруются, начиная с единицы, слева направо, строки - сверху вниз. Числа в каждой строке файла разделены одним пробелом.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать суммы чисел для заданных во входном файле прямоугольников в том же порядке, в котором они там описаны. Названные элементы в выходном файле должны размещаться на отдельных строках.

Пример файлов входных и выходных данных:

4. "Укладка кирпичей"

Строители должны вымостить кирпичами очередную прямоугольную площадку размером m*n. В целях надежности эта площадка должна быть вымощена таким образом, чтобы ни один ее кирпич полностью не соприкасался с каким-либо, кирпичом предыдущей площадки. Если кирпич представить в виде прямоугольника размером 1*2, на каждой половинке которого указан его порядковый номер, то расположение кирпичей на площадке можно изобразить, как показано на рисунке. При этом в левой части рисунка изображена исходная (нижняя) площадка размером 2*4, а справа - площадка, которую строители могут вымостить с учетом сделанных ограничений (верхняя площадка).

Требуется написать программу, которая по расположению кирпичей в исходной площадке определяет их возможное расположение в очередной площадке, которую необходимо вымостить строителям над исходной площадкой.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест
Формат входных данных:
Входной файл INPUT.TXT содержит следующую последовательность строк. В первой строке записаны два целых числа n и m, определяющие размеры площадки (n,m - четные числа, не превосходящие 100). Далее следуют n строк, в каждой их которых содержится по m чисел, указывающих расположение кирпичей в исходной площадке. При этом каждый кирпич представляется двумя одинаковыми числами, расположенными в клетках площадки, покрытых данным кирпичом. Все кирпичи пронумерованы натуральными числами от 1 до их общего количества. Числа в каждой строке файла разделены пробелами.
Формат выходных данных: OUTPUT.TXT должен содержать одно число "-1", если решение не существует. В противном случае, он должен содержать n строк, в каждой из которых должно находиться по m чисел, указывающих в вышеуказанном формате расположение кирпичей в площадке, которую строителям необходимо вымостить. Числа в каждой строке файла должны быть разделены одним пробелом.

Пример файлов входных и выходных данных:

УДАЧИ ВАМ!

ИвГУ: Математический факультет. Главная страница