Глава 1. Задачи

Задача 1 «Расшифровка»

Задан исходный текст, который зашифрован заменой русских букв путем их циклического сдвига в алфавите на равное порядковому номеру зашифровываемой буквы в алфавите число позиций по кольцевому принципу (например: А меняется на Б (на 1 позицию), Б на Г (2 позиции), Я на Я(33 позиции)). Написать программу, расшифровывающую исходный текст.

Ввод: Строка – исходный, зашифрованный текст из русских букв.

Вывод: Строка – расшифрованный текст.

Пример:

Ввод: Вывод:

Гбгб Яжб Баба Яга

Задача 2 «Арифметика автомобильных номеров»

Автомобильный номер состоит из четырех цифр и двух латинских букв. Поставив между цифрами и буквами знак равно, будем рассматривать пару букв как число в римской системе нумерации, а между парами цифр разрешим ставить знаки математических действий: плюс, минус, умножить (ПРИМЕР: 00 +02). Знак между цифрами ставить не обязательно. Составить алгоритм, выводящий максимальное количество возможных различных, верных равенств, для введенной буквенной серии номеров.

Краткие правила римской нумерации: Числа от 1 до 10 : 1 - I; 6 - VI; 2 - II; 7 - VII; 3 - III; 8 - VIII; 4 - IV; 9 - IX; 5 - V; 10 - X. Десятки записываются по тем же правилам, только вместо I используется Х, вместо V используется L - 50, вместо Х используется : С - 100. Для записи сотен используются символы C, D - 500 и М - 1000 соответственно. Меньшая цифра стоящая слева от большей этого же разряда вычитается, а справа – прибавляется, число вычисляется как сумма разрядов. Вычитать разрешено не более одной младшей для данного разряда цифры. В случае ввода серии из букв, которым не соответствует корректного римского числа выдать результат «0».

Ввод: Строка из двух больших латинских букв.

Вывод: максимальное число возможных различных, верных равенств соответствующее введенной буквенной серии номеров.

Пример :

Ввод: Вывод:

CM 14

Задача 3 «Разрезание листа»

Прямоугольный лист бумаги складывают N раз пополам, сгибая параллельно сначала одной, а затем другой из взаимно перпендикулярных сторон, (т.е. пополам, получившуюся фигуру еще пополам и т.д.), а затем разрезают получившуюся в результате складывания фигуру по диагонали. Составить алгоритм, выводящий максимальное количество частей, на которое может распасться сложенный и разрезанный таким образом лист, если N – натуральное число не превосходящее 32.

Ввод : N – число складываний листа.

Вывод: максимальное число частей, на которое может распасться сложенный лист после разрезания.

Пример :

Ввод: Вывод:

5 23

Задача 4 «КВН»

В КВН участвовали три команды: “BIM”, “BOM” и “BUM”. В перечисленном порядке вводится количество баллов, набранное командами. Написать программу, которая выдавала название команды (или команд), которые заняли второе место в КВН, а при отсутствии таковых выдавала сообщение “NO”.

Ввод: B1 B2 B3 - разделенные пробелами количества баллов набранных командами BIM, BOM, BUM – соответственно.

Вывод: название команды (команд), занявших 2-е место, или сообщение “NO”.

Пример :

Ввод: Вывод:

10 12.5 16 BOM

Задача 5 «Поезд»

Последовательно вводятся количества пассажиров, которые едут в каждом из N одинаковых вагонов поезда. Написать программу, которая выдавала бы номера вагонов, в которых наибольшее количество свободных мест. Ввод корректен.

Ввод: N K – количество вагонов и количество мест в вагоне,

Х1 Х2 X3 Х4 Х5 Х6 Х7 - разделенные пробелами количества пассажиров в вагонах.

Вывод: разделенные пробелами номера вагонов с наибольшим количеством свободных мест.

Пример :

Ввод: Вывод:

55 33 44 55 77 32 55 6

Задача 6 «Спортсмен»

В этом месяце спортсмен пробегает на каждой тренировке дистанцию в М км.. Известно, что каждый месяц длина дистанции возрастает на Р %. Написать программу, которая вычисляет, сколько месяцев назад длина пробегаемой за тренировку дистанции составляла Y км., если входные данные не корректны - вывести сообщение “NO”.

Ввод: М Y Р - длины дистанций сейчас и некоторое время назад и процент их увеличения.

Вывод: число - сколько месяцев назад дистанция была Y км. или сообщение - NO

Пример :

Ввод: Вывод:

4.630400 4.000000 5.000000 3

Задача 7 «Вычитание дробей»

Заданы две правильные (числитель меньше знаменателя), несократимые арифметические дроби. Написать программу, которая вычисляла бы разность между большей и меньшей из дробей и выдавала ответ в виде правильной, несократимой арифметической дроби. Числители и знаменатели дробей - натуральные числа не превышающие 46340. Ввод корректен.

Ввод: С1 Z1 С2 Z2 - разделенные пробелами числители и знаменатели первой и второй дробей соответственно.

Вывод: С и Z - разделенные пробелом числитель и знаменатель дроби-результата.

Пример :

Ввод: Вывод:

5 24 3 16 1 48

Задача 8 «Разные отрезки»

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

Ввод:Х1 Y1 X2 Y2 - разделенные пробелами координаты концов отрезка.

Вывод: число - результат.

Пример :

Ввод: Вывод:

0.5 0.5 -3.3 -3.3 6

Задача 9 «Шифр»

Заданы три натуральных числа: два исходных числа и номер члена, который является ключом к шифру. Каждый последующий член последовательности получается путем прибавления к сумме двух предыдущих членов, суммы цифр суммы двух предыдущих членов. Написать программу, которая определяла бы ключ к шифру. Исходные данные - натуральные числа до 1000. Ввод корректен.

Ввод: С1 С2 N - разделенные пробелом исходные числa и номер искомого члена.

Вывод: число-результат.

Пример :

Ввод: Вывод:

39 11 5 140

Задача 10 «Ход конем»

На клетчатой доске размером N*N клеток в клетке с координатами А, В (координаты отсчитывать от левого нижнего угла), стоит шахматный конь. Конь за один ход перемещается одновременно на две клетки вперед и одну в сторону в любом горизонтальном или вертикальном направлении в пределах заданной доски. Написать программу, которая вычисляла бы количество клеток, в которые конь не сможет попасть за М и менее М ходов. Ввод корректен, М и N: 1<N<101, 0<=M<1001.

Ввод: N A B М - : размер доски, координаты коня и количество ходов.

Вывод: число - результат.

Пример:

Ввод: Вывод:

5 1 1 3 3

Задача 11 «Ближайшее число»

Для заданного числа M ( 0<М<2 000 000 000 ), заменой в нем одной любой цифры, найти ближайшее, отличное от М число, которое нацело делилось бы на количество различных знаков, необходимых для записи искомого числа в N-ричной системе счисления (1<N<100). Заданное и искомое числа представляются в десятичной системе счисления. При наличии двух решений - взять меньшее из них, при отсутствии решения - выдать: ‘NO’. Пример, M=17, N=2; решения два: 16 (в двоичной системе 10000 для его записи нужны два знака {0,1}; 16 делится на 2 без остатка ), второе решение- 18 (в двоичной системе 10010 для его записи нужны два знака {0,1}; 18 делится на 2 без остатка), выбираем меньшее из них в качестве ответа : 16 .

Ввод: М N - разделенные пробелами: число и основание системы счисления.

Вывод: число - результат.

Пример:

Ввод: Вывод:

90372 13 90370

Задача 12 «Паралеллопландия»

Страна Параллелопландия имеет форму прямоугольного параллелепипеда размера А на В на С, состоящего из кубиков с единичной длиной ребра. Гражданами этой страны являются все прямоугольные параллелепипеды, расположенные в пределах ее границ и состоящие из целого числа единичных кубиков. Родственниками в этой стране считаются те параллелепипеды, которые имеют хотя бы один общий единичный кубик. Еще в Параллелопландии есть общество кубов, членами которого являются граждане, имеющие все три одинаковых размера. Необходимо написать программу, которая поможет одному маленькому кубику, расположенному по адресу А1, В1, С1 ( число А1 - это номер ряда, в размере А страны, в котором расположен этот единичный кубик, аналогично числа В1 и С1), подсчитать сколько в Параллелопландии граждан не являющихся членами общества кубов не являются родственниками маленького куба. А,В,С,А1,В1,С1 - натуральные числа не превосходящие 50..

Ввод: А В С - разделенные пробелами - размеры страны, в первой строке и –

А1 В1 С1 - три числа, разделенные пробелами - адрес кубика - вo второй строке.

Вывод: число - результат.

Пример:

Ввод: Вывод:

2 1 2 2

1 1 2

Задача 13 «Число ходов»

На клетчатой доске размером N на N клеток расставлено K белых коней и один черный конь. Один ход коня: на две клетки вперед и на одну в сторону в любом направлении в пределах доски (как в шахматах ). Клетка находится под боем коня, если он может стать в нее за один (следующий) ход. Составить программу, подсчитывающую за какое наименьшее число ходов черный конь, может пройти в клетку с заданными координатами X, Y , не становясь по пути в клетки, находящиеся под боем белых коней, и в клетки, в которых стоят белые кони. Белые кони стоят неподвижно. Если пройти невозможно вывести сообщение: NO. Координаты - натуральные числа, отсчитываются от левого нижнего угла доски: первая координата - номер вертикали, вторая - номер горизонтали, в которой находится клетка. Ввод корректен. Начальное положение черного коня может быть под боем белого коня, если конечная точка под боем - то пройти невозможно.

2 < N < 100, K<=N .

Ввод: из К+1 строки: в 1-й строке: N- размер доски, Х1, У1 -начальные координаты черного коня, Х, У - координаты конечной точки, К - количество белых коней, в каждой из следующих К строк: Хi, Yi- координаты i-го белого коня..

Вывод: число - результат или сообщение - NO.

Пример:

Ввод: Вывод:

1 3 3 1 2 4

2 2

3 2

Задача 14 «Хакер»

Хакеру при помощи подслушивающего устройства удалось подслушать пароль доступа к секретной компьютерной базе данных, который был продиктован по телефону посимвольно ( в звуковой форме наименование букв и цифр, например: буква М произносилась как 'эм', а записывалась хакером в виде одного символа ). Хакер записал пароль в виде строки, состоящей из заглавных букв и цифр. Но радость хакера была преждевременной, так как по телефону ни слова не было сказано большие или маленькие, русские или латинские буквы используются в пароле, а система защиты базы данных различает буквы по этим признакам, кроме этого, записывая буквы, в спешке, хакер записывал услышанные знаки, не учитывая, что некоторые из них в различных алфавитах пишутся одинаково, но звучат по-разному ( например: Р "эр"(рус.) и "пэ" (лат.)). Составить программу, подсчитывающую за какое число попыток ввода пароля, хакеру гарантированно удастся проникнуть в интересующую его базу данных. Ввод корректен. В пароле могут использоваться латинские и русские буквы и цифры, других символов в пароле нет. Длина пароля не превышает 80 символов. Уточнение: одинаково произносиосимыми в различных алфавитах считать буквы:

русские - АБВД ЕЖИКЛМНОПРСТУФЦ

латинские - ABVDE G I KLMNO PRSTU FC

одинаковыми по написанию в различных алфавитах считать буквы:

русские - АВЕКМНОРСТХ

латинские - ABEKMHOPCTX.

Ввод:. строка-пароль, записанная цифрами и заглавными буквами.

Вывод: число - результат.

Пример:

Ввод: Вывод:

AB12 32

Задача 15 «Разноделящиеся числа»

Будем называть два целых числа «разноделящимися», если большее по модулю делится без остатка на меньшее по модулю и нет ни одной такой цифры, которая входила бы в десятичную запись обоих этих чисел. Меньшее по модулю из этих чисел будем называть «разноделящимся» делителем большего по модулю числа. Составить программу находящую на заданном интервале число (максимальное) имеющее наибольшее количество различных «разноделящихся» делителей. Вывести это число и количество его различных «разноделящихся» делителей. В отдельно взятом одном из «разноделящихся» чисел цифры могут повторяться; А и В - границы интервала числа, не превосходящие по модулю число 2 000 000; границы входят в интервал, задаются и вводятся в произвольном порядке; длина интервала не превосходит 202; если на заданном интервале несколько чисел имеют равное наибольшее количество различных «разноделящихся» делителей, то взять максимальное из них; число «1» считать делителем (обычным) любого числа; знак числа цифрой не считать;

Ввод: два числа: А и В - границы интервала.

Вывод: два числа: первое - на заданном интервале число, имеющее наибольшее количество различных «разноделящихся» делителей, второе - количество различных «разноделящихся» делителей первого числа.

Пример :

Ввод: Вывод:

9 16 16 6

Задача 16 «Муравейник»

Вначале сезона из переполненного муравейника уходят М муравьев, которые строят свой новый муравейник, развивающийся по законам:

• количество родившихся за сезон молодых муравьев равно увеличенному в К раз количеству муравьев в муравейнике, возраст которых на начало сезона не превышал двух сезонов;

• продолжительность жизни муравья G сезонов;

• когда численность родившихся за сезон муравьев более чем в В раз превысит их начальное количество, из муравейника уходит 1/В часть муравьев, возраста один сезон (родившихся в прошлом сезоне), чтобы организовывать свои новые муравейники (уход происходит в том же сезоне за который подсчитывается число родившихся).

Составить программу находящую количество муравьев в муравейнике через Т сезонов после его основания. Все события, происходящие в муравейнике, (рождения, смерти, уходы) происходят в течении сезона, но итоги подводятся только по окончании сезона, и весь следующий сезон до его окончания действуют цифры прошлого сезона.Возраст родившегося в текущем сезоне муравья до наступления следующего сезона равен нолю.

Количество уходящих муравьев округляется до целого по правилам арифметики. М,G,К,Т и В - натуральные числа, 1<М <1000, G,К,Т,В не превосходят 255 ; ввод корректен.

Ввод: числа М,K,G,В,T- в перечисленном порядке.

Вывод:. число муравьев в муравейнике после Т сезонов.

Пример :

Ввод: Вывод:

2 3 3 2 5 1005

Задача 17 «Составь перевертыш»

Вводится строка до 255 символов. Написать программу составляющую из символов этой строки наибольшей возможной длины «перевертыш» (строка одинаково читаемая справа налево и слева направо), в левой половине которого символы упорядочены по порядку возрастания их ASCII кодов .

Ввод: строка до 255 символов.

Вывод: 1-я строка: длина «перевертыша»

2-я строка: «переветыш».

Пример :

Ввод: Вывод: