Областная олимпиада по информатике 2003 года
Задача 1. "Спираль" (30 баллов)
Робот-минер новейшей конструкции способен провести разминирование местности, план которой должен быть представлен в виде прямоугольника с целыми длинами сторон (n-высота прямоугольника, m-длина прямоугольника). Перед началом работы робота размещают перед левой верхней клеткой прямоугольника в направлении "слева-направо", после чего робот начинает обход и разминирование, двигаясь по спирали по часовой стрелке (см. рисунок) При этом спираль постепенно "закручивается" вовнутрь, захватывая все клетки прямоугольника. Разминирование заканчивается, когда проверены все клетки.
Требуется написать программу, которая для заданных исходных данных определяет количество поворотов, которое должен совершить робот в процессе разминирования.
Технические требования. Имя входного файла INPUT.TXT выходного OUTPUT.TXT Ограничение по времени тестирования 1 секунда на один тест.
Формат входных данных Входной файл INPUT.TXT содержит два целых числа, расположенных в одной строке в следующем порядке n, m (1<=n,m<=32767). Числа в строке разделены пробелами.
Формат выходных данных Выходной файл OUTPUT.TXT должен содержать одно целое число - количество поворотов.
Пример файлов входных и выходных данных
INPUT.TXT OUTPUT.TXT
3 5 4
Задача 2. "шытревереП" (30 баллов)
атЭ ачадаз - яанноицидартен. ьседЗ онасипан, отч оннеми ыв ынжлод ьталедс с мындохси молйаф, мищажредос еикснитал и еикссур ывкуб, а ежкат еигурд еынжомзов иканз (ырфиц, иканз яинаниперп) ыМ окьлот мищбоос, отч ьседз доп моволс, мищажелдоп юинавозарбоерп, ястеаминоп ьтсоньлетаводелсоп хикснитал и хикссур (ациллирик) воловмис (омисивазен то артсигер), ясяащюавичнаказ обил моцнок икортс, обил моцнок алйаф, обил моловмис, мынчилто то ывкуб.
катИ, етишипан уммаргорп, яароток тедевирп тов йокат "йыннечропси" тскет к умоньламрон удив.
Технические требования. Имя входного файла INPUT.TXT выходного OUTPUT.TXT Ограничение по времени тестирования 3 секунды на один тест.
Формат входных данных. Входной файл содержит некоторый закодированный текст (не более 1000 строк, длина каждой из еоторых не превышает 255 символов. В тесте могут быть любые печатные символы).
Формат выходных данных. Выходной файл содержит восстановленных текст.
Пример файлов входных и выходных данных
INPUT.TXT
отЭ ремирп оготсорп атсет. илсЕ ыВ еще ен иляноп, от етишипаз ывкуб огоджак аволс в монтарбо екдяроп. итатсК, еиненемирп амтирогла "яинавичаровереп" волс ыджавд тидовирп к юинелвонатссов огондохси атсет.
OUTPUT.TXT
Это пример простого теста. Если Вы еще не поняли, то запишите буквы каждого слова в обратном порядке. Кстати, применение алгоритма "переворачивания" слов дважды приводит к восстановлению исходного текста.
Задача 3. "Массив" (30 баллов)
Во многих языках программирования программист может использовать как одномерные, так и многомерные массивы. Например, в Паскале для записи массива Х запись array[0..2,0..1,0..3] означает трехмерный массив с граничными парами: 0..2,0..1,0..3. Здесь мы ограничились только нулевыми значениями нижних границ, хотя Паскаль допускает использование и других значений.
Для многомерного массива всегда, можно определить порядок пересечения его элементов. Для дальнейшего рассмотрения будем считать, что этот порядок определяется правилом "чем правее индекс, тем быстрее он изменяется". То есть, сначала последний индекс 2пробегает" все возможные значения, затем предпоследний индекс изменяется на одну единицу и вновь последний индекс изменяется от минимального значения к максимальному и т.д. Например, элементы упомянутого массива перечисляются в следующем порядке: X[0,0,0], X[0,0,1], X[0,0,2], X[0,0,3], X[0,1,0], X[0,1,1], X[0,1,2], X[0,1,3], X[1,0,0], X[1,0,1], X[1,0,2], X[1,0,3], X[1,1,0], X[1,1,1], X[1,1,2], X[1,1,3], X[2,0,0], X[2,0,1], X[2,0,2], X[2,0,3], X[2,1,0], X[2,1,1], X[2,1,2], X[2,1,3].
Пусть n-мерный массив Х задан описанием array[0..k1, 0..k2,...,0..kn]. Тогда, как легко проверить, порядковый номер Р любого i-го элемента Х[i1,i2,...,in] этого массива в описанном перечислении можно вычислить по формуле: P(i1,i2,..in)=1+D1*i1+D2*i2+...+Dn*in, где D1,D2,...,Dn - так называемые индексные множители. В частности, для вышеприведенного массива индексные множители соответственно равны: D1=8, D==4, D3=1, а порядковый номер элемента X[1,0,3] будет вычисляться по формуле: P(1,0,3)=1+8*1+4*0=1*3=12.
Требуется написать программу, которая вычисляет неизвестные верхние границы массива (k1,k2,...,kn) при заданных значениях индексных множителей и общего количества элементов массива.
Технические требования. Имя входного файла INPUT.TXT выходного OUTPUT.TXT Ограничение по времени тестирования 2 секунды на один тест.
Формат входных данных. Входной файл состоит из следующих строк. В первой строке содержатся два целых числа: n-размерность массива (1<=n<=20), s - общее количество элементов массива (1<=n<=Maxlongint). Далее в n строках располагаются соответствующие индексные множители D1, D2, ..., Dn. Числа в каждой строке файла разделены пробелами.
Формат выходных данных. Выходной файл должен содержать верхние границы всех граничных пар k1, k2, ..., kn (1<=ki<=1000) в указанном здесь порядке. названные элементы в этом файле могут разделяться пробелами и/или размещаться на отдельных строках.
Пример файлов входных и выходных данных
INPUT.TXT OUTPUT.TXT
3 24 2 1 3
8
4
1
Задача 4. "Шоу" (30 баллов)
В процессе разработки сценария открытия олимпиады главный режиссер задумал небольшое шоу с перестроением его участников в различное число колонн ровно N способами. Для достижения наибольшего эффекта нужно было, чтобы при любом перестроении количество людей в каждой колонне было одинаковым. чтобы решить эту задачу режиссеру необходимо знать, какое минимальное число участников М ему для этого понадобиться. Например, для случая N=3 потребуется пригласить всего четыре человека, которые могут выстроиться в 1,2 и 4 колонны. Если же для некоторых N потребуется более 109 человек, то режиссер должен отказаться от задуманной идеи, так как необходимое число участников собрать невозможно.
Требуется написать программу, которая решает поставленную перед режиссером задачу, т.е. для заданного количества способов построения N определяет минимальное количество участников шоу.
Технические требования. Имя входного файла INPUT.TXT выходного OUTPUT.TXT Ограничение по времени тестирования 5 секунды на один тест.
Формат входных данных. Входной файл содержит одно натуральное число N (N<=1000) определяющее количество необходимых режиссеру способов построения участников.
Формат выходных данных. Выходной файл должен содержать число М, равное минимальному количеству участников, необходимых режиссеру для осуществления N способов построения в процессе шоу. Если найденное число М превосходит 109 то выходной файл должен содержать только число 0.
Пример файлов входных и выходных данных
INPUT.TXT OUTPUT.TXT
5 16
6 12
24 360
Test-the-Best.by соревнования по спортивному программированию
Скачать задания в Word
Сайт открыт 1 мая 2006г.
