ЗАДАЧИ И РЕШЕНИЯ
СБОРНИК-6 (ПАСКАЛЬ)

Сборник задач с решениями на языке
паскаль "Олимпиадные задачи"

Задачи и решения: Сборник-6

В разделе "Задачи и решения" находятся тексты различных задач по информатике без решений.
     Решения к ним можно купить посредством SMS.
После отправки SMS Вы получаете пароль, который разрешает закачку.

 

Цена: 150 тенге = 1 у.е.



  • "Олимпиадные задачи".  Сборник-6

Задача 1   "Счастливые билеты"

Автобусные билеты в рулоне пронумерованы от 000001 до 999999.
Составить программу, выводящую на экран количество и номера (в несколько столбиков) всех счастливых билетов в некотором диапазоне, организовав запрос начального и конечного номера билета диапазона.
Примечание: Счастливым считать тот билет, у которого сумма первых трех цифр равна сумме трех последних.
-----------------------------------------------------------------------------------------------------------------------------


Задача 2   "Прямоугольники" - 2 уровень

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

Написать программу, которая считает число этих прямоугольников.
Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит массив 100х100, в котором элемент A[i,j]=1, если клетка [i,j] принадлежит какому-либо прямоугольнику, и A[i,j]=0, в противном случае.
Формат выходных данных:
В файл OUTPUT.TXT необходимо вывести единственное число - количество прямоугольников.
-----------------------------------------------------------------------------------------------------------------------------


Задача 3   "Игра в города" - 5 уровень

Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т.д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных.
Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано ровно столько раз, сколько оно в нём встречается.
Технические условия:
Во входном файле на первой строке записано число N - количество слов в списке (1<=N<=1000), а в последующих N строках - сами слова. Каждое из них является последовательностью не более, чем 10 строчных английских букв.
Выведите в выходной файл слова в исходном порядке, либо сообщение "NO", если такого порядка не существует. Каждое слово должно быть выведено в отдельную строку выходного файла.
-----------------------------------------------------------------------------------------------------------------------------


Задача 4   "Квадрат" (20 баллов)

Задано прямоугольная таблица из нулей и единиц размером N (количество строк) на M (количество столбцов) (1PdN, MPd1000). Строки и столбцы нумеруются с единицы, начиная с левого верхнего угла.
Требуется написать программу, которая находит размер и расположение максимального квадрата, состоящего из одних единиц.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке числа N и M, записанные через пробел. В следующих N строках записано по M символов (0 или 1).
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записываются: в первой строке длина стороны, а во второй через пробел - номера строки и столбца левого верхнего угла наибольшего квадрата.
Пример файла входных данных:
3 4
1111
1111
0111
Пример файла выходных данных (для приведенного выше входного файла):
3
1 2
-----------------------------------------------------------------------------------------------------------------------------


Задача 5   "Остаток" (20 баллов)

Дано число в K-ичной (KPd37) системе счисления, состоящее из N (1PdNPd100000) цифр - a-NaN-1:a1. Для записи последнего числа кроме цифр 0, 1, :, 9, если требуется, используются заглавные латинские буквы A, B, ,Z. Также задано натуральное число M.
Требуется написать программу, которая находит остаток от деления первого ч
исла на второе.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке числа K, N и M, записанные в десятичной системе счисления через пробел. Во второй строке записаны цифры заданного числа.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается найденный остаток от деления.
Пример файла входных данных:
16 2 2
FF
Пример файла выходных данных (для приведенного выше входного файла):
1
-----------------------------------------------------------------------------------------------------------------------------


Задача 6   "Матрица" (20 баллов)

Задана прямоугольная таблица A размером N (количество строк) на M (количество столбцов) (1PdN*MPd30000), элементами которой являются натуральные числа, меньшие 30000. Строки и столбцы нумеруются с единицы, начиная с левого верхнего угла.
Требуется написать программу, которая находит таблицу B такого же размера, элемент bi,j которой равен максимальному из элементов части таблицы A, ограниченной снизу проходящими через i, j диагоналями. Например, для i=3, j=2 часть таблицы, в которой ищется максимальный
элемент, показана на рисунке:


Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке числа N и M, записанные через пробел. В следующих N строках записано через пробел по M чисел.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается по строкам найденная матрица, в строках числа разделяются пробелами.
Пример файла входных данных:
2 2
1 3
4 2
Пример файла выходных данных (для приведенного выше входного файла):
1 3
4 3
-----------------------------------------------------------------------------------------------------------------------------


Задача 7   "Последовательность чисел" (20 баллов)

Рассмотрим бесконечную в обе стороны последовательность целых чисел Fi, в которой для любого целого i элемент Fi+2 вычисляется с использованием следующего условия Фибоначчи: Fi+2= Fi+1+Fi. Пусть заданы два различных члена этой последовательности - Fi и Fj с соответствующими номерами i и j, а также некоторое целое число n. Необходимо восстановить элемент этой последовательности Fn, соответствующий номеру n.
Требуется написать программу, которая по заданным числам i, Fi, j, Fj, n вычисляет искомый элемент Fn описанной выше последовательности.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест
Формат входных данных:
Входной файл INPUT.TXT содержит в одной строке разделенные пробелами следующие числа: i, Fi, j, Fj, n. Для этих чисел справедливы следующие ограничения:
-1000<=i, j, n<=1000;
-2000000000<=Fk<=2000000000 для всех k, удовлетворяющих условию min(i,j,n)<=k <=max(i,j,n).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать искомое число Fn.
Пример файла входных данных:
3 5 -1 4 5
Пример файла выходных данных (для приведенного выше входного файла):
12
-----------------------------------------------------------------------------------------------------------------------------


Задача 8   "Число" (20 баллов)

Задано целое число N (1<=N<=2147483647).
Требуется написать программу, которая определяет наименьшее натуральное число с произведением цифр равным N.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит одно целое число N.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число - искомое наименьшее
натуральное число. Если такого числа не существует, то записать в выходной
файл значение 0.
Пример файлов входных и выходных данных:
INPUT.TXT
10
OUTPUT.TXT
25
-----------------------------------------------------------------------------------------------------------------------------


Задача 9   "Сообщение" (20 баллов)

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а символ пробел - нулем.

Требуется написать программу, которая по заданной последовательности цифр (не более 100) находит количество исходных сообщений, из которых она могла бы получиться.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит последовательность цифр.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число - искомое количество исходных сообщений.
Пример файла входных данных:
1025
Пример файла выходных данных (для приведенного выше входного файла):
4
(Пояснение: 1сообщ-(1 0 25); 2сообщ-(1 0 2 5); 3сообщ-(10 25); 4сообщ-(10 2 5);)
-----------------------------------------------------------------------------------------------------------------------------


Задача 10   "Последняя цифра" (20 баллов)

Задано натуральное число N (1<=N<=9999).
Требуется написать программу, определяющую последнюю ненулевую цифру числа N!=1*2*3*...*N.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит число N.
Формат выходных данных:
В выходной файл OUTPUT.TXT найденная цифра.
Пример файла входных данных:
5
Пример файла выходных данных (для приведенного выше входного файла):
2
-----------------------------------------------------------------------------------------------------------------------------


Задача 11   "Наименьшее из больших" (20 баллов)

Дано натуральное число N.
Требуется написать программу для определения наименьшего из больших чисел, составленных из тех же цифр.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит заданное N (10<=N<=10100).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одну строку - найденное число или 0, если такого числа не существует.
Пример файла входных данных:
132
Пример файла выходных данных (для приведенного выше входного файла):
213
-----------------------------------------------------------------------------------------------------------------------------


Задача 12   "Бутылки" (30 баллов)

В цех вторичной переработки поступают бутылки N (1<=N<=8) видов: A, B, C, ... (первые N заглавных букв латинского алфавита). Бутылки поступают на переработку партиями из N контейнеров, причем в каждом контейнере могут находиться бутылки различных видов. Перед вторичной переработкой бутылок специальные рабочие сортируют их по видам таким образом, чтобы после сортировки в каждом из поступивших контейнеров остались бутылки только одного вида. В каждом из контейнеров может помещаться неограниченное количество бутылок.
Требуется написать программу, которая определяет минимальное количество перемещений бутылок, обеспечивающих их сортировку по видам, причем за каждое перемещение можно переместить только одну бутылку из одного контейнера в другой.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT состоит из N+1 строк. В первой строке записано число N. Во второй строке располагаются разделенные пробелами N целых числа, соответствующие количеству бутылок вида A, B, C, ... в первом контейнере. В последующих строках содержится аналогичная информация для второго, третьего, ..., N-го контейнеров соответственно. Известно, что количество бутылок в каждом из контейнеров не превосходит 32767.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен состоять из двух строк. В первой располагается последовательность из символов A, B, C, ..., которая определяет какого вида бутылки находятся после сортировки в 1-м, 2-м, ..., N-м контейнерах. Во второй строке располагается число, определяющее искомое количество перемещений бутылок. Если возможно несколько вариантов ответа, то необходимо выдать любой из них.
Пример файла входных данных:
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Пример файла выходных данных (для приведенного выше входного файла):
ABCD
102
-----------------------------------------------------------------------------------------------------------------------------


Задача 13   "Шахматная" (20 баллов)

На шахматной доске стоит ферзь и конь. Расположение каждой фигуры задано ее координатами в шахматных обозначениях.
Требуется написать программу, которая определяет количество полей, которые находятся под боем этих фигур.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT состоит из 2-х строк. В первой строке записаны координаты ферзя, во второй - коня.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен состоять из одной строки, в которой записано найденное количество полей.
Пример файла входных данных:
a1
h8
Пример файла выходных данных (для приведенного выше входного файла):
22
-----------------------------------------------------------------------------------------------------------------------------


Задача 14   "Фибоначчиева система счисления" (20 баллов)

Числа Фибоначчи U1, U2, ... определяются начальными значениями и соотношением:
U1=1; U2=2; Un=Un-1+Un-2.
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, ..., а числа Фибоначчи 1, 2, 3, 5, 8, 13, ... . В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в фибоначчиевой системе счисления, находила строку, представляющую число A+B также в этой системе счисления.
Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Технические ограничения: строки могут быть столь длинны, что числа A и B превысят максимально допустимое в вашем компьютере целое число. Длина записи чисел A, B и их суммы A+B в фибоначчиевой системе счисления не превышает 255 знаков.
Формат входных данных:
В текстовом файле INPUT.TXT в первой строке записано первое число, а во второй - второе.
Формат выходных данных:
Вывести в текстовый файл OUTPUT.TXT полученную сумму.
Пример файла входных данных:
10101
100
Пример файла выходных данных (для приведенного выше входного файла):
100010
-----------------------------------------------------------------------------------------------------------------------------


Задача 15   "Оставшееся число" (20 баллов)

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


Задача 16   "Умножение дроби" (20 баллов)

Задана некоторая правильная периодическая дробь Q и натуральное число N. Q и N таковы, что количество цифр, используемых для их записи, не превосходит 100. При изображении дроби Q периодическая часть заключается в круглые скобки.
Требуется написать программу, которая определяет результат умножения Q на N, то есть непериодическую часть и минимальный период числа QxN. В случае получения результата умножения в виде конечной дроби скобки опускаются.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит две строки. В первой строке задается дробь Q, а во второй - число N.
Формат выходных данных:
В единственной строке выходного файла OUTPUT.TXT должен содержаться результат умножения Q на N.
Пример файла входных данных:
0.1(6)
3
Пример файла выходных данных (для приведенного выше входного файла):
0.5
-----------------------------------------------------------------------------------------------------------------------------


 

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 |



Сборник-6 с решениями - купить посредством SMS    Цена: 150 тенге = 1 у.е.



В начало страницы  





Copyright © 2008

Rambler's Top100         Resurs.kz: сайты Казахстана и раскрутка сайта