Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 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 и

Технические требования :

Входной файл: INPUТ.ТХТ

Выходной файл: О UTPUТ.ТХТ

Ограничение времени: 10 секунд

Формат входных данных:

Во входном файле хранятся две строки символов, означающих

первое и второе числа . Длина строки не более 40 символов.

Формат выходных данных:

В выходном файле в текстовом виде должны содержаться

пары чисел I и J или слово NO, если заданные числа не равны ни в

каких из указанных ( 2<=I<=36 и 2<=J<=36) системах

исчисления..

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

INPUT.TXT OUTPUT.TXT

10 2 3

Задача 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

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

,...,V

(1<=V

<=100),

приписанных рискам . Последняя риска считается сделанной на

верхнем крае пробирки (V

=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 секунд

Формат входных данных

В файле исходных данных записаны в отдельных строках два

выражения.