Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
1 1 1 1 1 0
1 1 1 0 1 1
Задание.
Создать программу для ввода закодированного текста по
строкам и расшифровки его с помощью данной сетки .
Технические требования.
Исходные данные - текст и сетка - задаются в виде
квадратных таблиц в текстовых файлах inp1.txt и inp2.txt, каждая
строка таблицы размещается в отдельной строке файла . Результат
выводится на экран .
Пример исходных данных Выходные данные
ж б в у н р бурямглоюнебокроетвихриснежныекрутя
и ы н е я е
к х м б р р
о г у р л к
т и р я о о
с е н ю е т
1 0 1 0 1 0
1 1 1 1 0 1
1 1 0 1 1 1
1 0 1 1 0 1
1 1 1 1 1 0
1 1 1 0 1 1
Задача 8. «Зоны»
Двумерная таблица Р[1:M,1:N] заполнена нулями и
единицами. Цепочкой будем называть последовательность
единичных элементов таблицы , в которой последовательно
расположенные пары элементов таблицы являются соседними по
горизонтали , вертикали или диагонали . Смыкаясь концами друг с
другом и с краями таблицы , цепочки делят таблицу на "зоны ",
заполненные нулями. Своими индексами P и Q задается элемент
таблицы . Требуется заполнить единицами зону таблицы , в котором
находится заданный элемент. Если заданный элемент окажется
единичным, то таблица не преобразуется.
Задание.
Создать программу для получения таблицы (из заданной), в
которой зона с заданным элементом заполнена единицами, если
заданный элемент - нулевой.
Технические требования.
Входными данными являются число строк М и столбцов N
таблицы , значения элементов таблицы и индексы задаваемого
элемента .
Входные данные берутся из текстового файла INP5.TXT, в
первой строке которого указывается числа M и N станций, в
каждой следующей строке - очередная строка таблицы , в
последней строке файла - числа P и Q.
Результат - новая таблица - выводится на экран .
Пример входных данных Выходные данные:
12 12
000000000000 000000000000
011000000000 011000000000
010111110000 011111110000
010000001000 011111111000
010011000100 011111111100
010101000010 011101111110
010011011110 011111111110
010000010000 011111110000
010010011000 011111111000
010101001000 011101111000
011000110000 011000110000
000000000000 000000000000
5 8
Задача 9. «Лист бумаги»
Имеется прямоугольный лист бумаги , длина которого равна N
сантиметров, а ширина M сантиметров. С листом можно
производить следующие операции: сгибать лист вдвое , cовмещая
противоположные стороны листа ; сгибать лист совмещая одну
строну с параллельной ей линией сгиба; разгибать лист, при этом
оставляя на нем линию сгиба . Написать программу, которая
определяет: можно ли его свернуть так, чтобы получился
прямоугольник длиной P сантиметров и шириной Q сантиметров.
В случае утвердительного ответа программа должна выдавать
минимальное количество операций с листом , необходимых для
этого .
Технические требования :
Входной файл: INPUТ.ТХТ
Выходной файл: О UTPUТ.ТХТ
Ограничение времени : 5 секунд
Формат входных данных:
В первой строке входного файла содержаться вещественные
числа N,M,P и Q в виде десятичных дробей.
Формат выходных данных:
Если лист свернуть можно, то первая строка текста должна
содержать строка должна содержать YES и минимальное число
операций, необходимых для этого . В противном случае , первая
строка текста должна содержать слово NO.
Пример файлов входных и выходных данных:
INPUT.TXT OUTPUT.TXT
1 2 1 0.75 YES 4
Задача 10. «Система счисления»
Множество символов I-ричной системы исчисления(2<=I<=36)
образуют символы 0,… ,9,A,B,… ,Z. Если I<36, то соответствующее
количество последних букв латинского алфавита в качестве цифр
не используются. Если I<10, то не используются соответствующие
цифры . Необходимо написать программу, которая по двум
текстовым строкам , означающим одно и тоже число в I-ричной и J-
ричной системе исчисления, определяет минимальные значения I и
J.
Технические требования :
Входной файл: INPUТ.ТХТ
Выходной файл: О UTPUТ.ТХТ
Ограничение времени: 10 секунд
Формат входных данных:
Во входном файле хранятся две строки символов, означающих
первое и второе числа . Длина строки не более 40 символов.
Формат выходных данных:
В выходном файле в текстовом виде должны содержаться
пары чисел I и J или слово NO, если заданные числа не равны ни в
каких из указанных ( 2<=I<=36 и 2<=J<=36) системах
исчисления..
Пример файлов входных и выходных данных:
INPUT.TXT OUTPUT.TXT
10 2 3
2
Задача 11. «Электрическая цепь»
В электрическую цепь включено N устройств . Устройство с
номером I реагирует на поступающие в сеть сигналы определенной
частоты (частота – неотрицательное вещественное число ), причем
само тоже генерирует сигналы и посылает их в цепь. Для каждого
устройства задан диапазон частот сигналов (A(I),B(I)) (A(I) и B(I)
– неотрицательные вещественные числа , причем A(I)<B(I) ) на
которые это устройство реагирует (исключая эти числа ) и посылает
в цепь сигнал с частотой равной C(I)*X+D(I) ( C(I) и D(I) -
вещественные числа ) , где X - частота поступившего сигнала .
Диапазоны различных устройств могут пересекаться, в этом случае
все генерируемые сигналы распространяются одновременно.
Работа цепи заканчивается, если ни один из распространяемых по
ней сигналов не попадает в диапазон ни одного устройства.
Написать программу, которая по описанию всех устройств
сети определят множество всех сигналов X, при подаче которых
работа цепи никогда не закончится.
Технические требования :
Входной файл: INPUТ.ТХТ
Выходной файл: О UTPUТ.ТХТ
Ограничение времени : 20 секунд
Формат входных данных:
В первой строке входного файла содержится число устройств
N (1<=N<=20). В последующих строках файла указываются
четверки вещественных чисел A(I), B(I), C(I), D(I) в виде
десятичных дробей. Каждая четверка занимает отдельную строку
файла .
Формат выходных данных:
В выходном файле указываются пары вещественных чисел –
начала и концы диапазонов частот сигналов, при подаче которых
цепь никогда не закончит свою работу . Если таких сигналов нет, то
файл должен содержать слово NO.
Пример файлов входных и выходных данных:
INPUT.ТХТ OUTPUT.TXT
2
0 5 2 10 0 5
10 15 1 –10 10 15
Задача 12. «Новые гвозди»
На прямоугольный стол разложили N одинаковых листков
бумаги со сторонами, параллельными краям стола . Необходимо
прибить листки к столу гвоздями так, чтобы в каждый листок был
вбит ровно один гвоздь, а каждым гвоздём прикреплялся к столу
хотя бы один листок. Гвозди нельзя забивать в границы листков
бумаги .
Технические требования
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени : 20 секунд
Формат входных данных
В файле исходных данных записано количество листков N
(1≤N≤100), длина листка L и его ширина W (1≤L,W≤1000). Далее
следуют описания N листков, заданных координатами левого
нижнего угла . Оси координат расположены по краям стола , начало
координат находится в левом нижнем углу стола . Координаты
точек – пары неотрицательных целых чисел, не превосходящих
1000. Все числа разделяются пробелами и/или символами перевода
строки .
Формат выходных данных
Если вбить гвозди требуемым в условии способом
невозможно, то необходимо поместить в выходной файл строку
«вбить гвозди невозможно». Если искомый способ существует, то
программа должна вывести в выходной файл координаты гвоздей в
произвольном порядке . Координаты гвоздей – вещественные числа .
Числа в выходном файле должны разделяться пробелами и/или
символами перевода строки .
Пример файлов входных и выходных данных
INPUТ.ТХТ OUTPUT.TXT
3 6 6
10 10 13 7.5
0 0 5 5 12 3
Задача 13. "ПРОБИРКИ"
Имеются три пробирки . Вместимость каждой из них - 100
миллилитров. На первых двух пробирках нанесены одинаковые
риски . Третья пробирка - без рисок. Возле каждой риски надписано
целое число миллилитров, которое вмещается в пробирку от дна до
этой риски .
Изначально одна из пробирок с рисками наполнена 100
миллилитрами кваса, а остальные две - пустые. Требуется
написать программу, которая выясняет, можно ли поместить в
пробирку без рисок один миллилитр кваса, и если да, то находит
минимально необходимое для этого число переливаний. Квас
можно переливать из одной пробирки в другую до тех пор, пока
либо первая из них не станет пустой, либо одна из пробирок не
окажется заполненной до какой-либо риски .
Технические требования :
Входной файл: INPUТ.ТХТ
Выходной файл: О UTPUТ.ТХТ
Ограничение времени : 20 секунд
Формат входных данных
В первой строке входного файла содержится число рисок N
(1<=N<=20) на каждой из первых двух пробирок. Затем в порядке
возрастания следуют N целых чисел V
1
,...,V
N
(1<=V
i
<=100),
приписанных рискам . Последняя риска считается сделанной на
верхнем крае пробирки (V
N
=100). Все числа разделяются
пробелами и/или символами перевода строки .
Формат выходных данных
В первой строке выходного файла должна содержаться строка
"Yes", если в третью пробирку возможно отделить один миллилитр
кваса, и "No" - в противном случае . В первом случае во вторую
строку необходимо вывести искомое количество переливаний.
Пример файлов входных и выходных данных
INPUT.ТХТ ОUTPUТ.ТХТ
4 Yes
13 37 71 100 8
Задача 14. «Точки»
Имеется N точек и известны расстояния между некоторыми из
них. Написать программу, которая проверяет, можно ли эти точки
расположить на плоскости так, чтобы указанные расстояния между
ними сохранились.
Технические требования
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени : 20 секунд
Формат входных данных
В файле исходных данных записано количество точек N
(1≤N≤100), и расстояния между некоторыми из них в виде:
N_первой_точки N_второй точки Расстояние. Расстояние –
вещественное неотрицательное число , не превосходящие 1000.
Номер точки – целое число из отрезка 1..N. Все числа разделяются
пробелами и/или символами перевода строки .
Формат выходных данных
Ответом должно быть слово Yes или No (Yes - точки можно
расположить, No – точки нельзя расположить).
Пример файлов входных и выходных данных
INPUТ.ТХТ OUTPUT.TXT
3 No
1 2 10
2 3 20
3 1 100
Следующие задачи предлагались на областных олимпиадах
школьников по информатике в 1998 – 2000 годах.
Задача 15. «Выражение»
Заданы два математических выражения, содержащие целые
числа , знаки сложения, вычитания и умножения, круглые скобки и
переменные, длина которых не более одного символа . Написать
программу, которая по заданным выражениям определяет, равны
ли они тождественно при всех значениях переменных.
Технические требования
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени : 20 секунд
Формат входных данных
В файле исходных данных записаны в отдельных строках два
выражения.