24 12 Night winter
Задача 43 «Сказка»
Иван Царевич сражается со Змеем Горынычем, у которого N (N<30333) голов, которые Иван отрубает так: если у змея четное число голов - он отрубает 9 голов, а если нечетное - 11 голов одним ударом. После каждого удара, если у Змея осталась не срубленной хотя бы одна голова, то отрастает еще 8 новых голов. Змей побежден, если после очередного удара мечом у него не осталось ни одной головы. Написать программу, которая вычисляла бы, какое количество ударов понадобится Ивану Царевичу для победы над Змеем Горынычем, и сколько при этом он отрубит голов у Змея.
Вход:N - начальное число голов у Змея Горыныча.
Выход: Разделенные пробелом два числа: первое – число ударов, второе - число срубленных при этом голов.
Пример :
Ввод: Вывод:
33 13 129
Задача 44 «Гномы»
Семь гномов имеют каждый по одной кружке, емкостью от 100 до 1000 грамм (емкость кружки - вещественное число из указанного диапазона, заданное в формате с шестью знаками после запятой). Для приготовления своих волшебных смесей гномы используют живую и мертвую воду, источники которой находятся возле их жилищ. Воду из источников брать и выливать обратно можно в не ограниченных количествах, но приготовление волшебных смесей требует очень большой точности (до долей миллиграммов, или шести знаков после запятой). Написать программу, которая по заданным семи емкостям кружек, определяла с точностью до шести знаков после запятой, минимальный объем воды, который можно точно отмерить данным набором кружек.
Вход: в строке 7 чисел, разделенных пробелами - емкости кружек.
Выход: Число – решение в формате вида: ####.######.
Пример: Вход:
100.000000 125.125000 250.125000 250.250000 500.000000 750.125000 1000.000000
Выход:
0.125000
Задача 45 «Пятница,13»
Необходимо написать программу, которая по введенным: номеру дня недели начальной даты, начальной и конечной датам, вычисляла бы количества дней между введенными датами (сами даты включаются в интервал) на которые приходились понедельник 13 числа и пятница 13 числа. Дни номеруются с понедельника (имеет номер 1); Начальная дата меньше конечной; Даты задаются в формате: ДД/ММ/ГГГГ , где ДД - две цифры - число месяца, ММ- две цифры - номер месяца, ГГГГ- четыре цифры – номер года; Данные, даты и ввод - корректны.
Вход: 1-я строка: находится число N (номер дня недели начальной даты); 2-я строка - начальная дата; 3-я строка – конечная дата.
Выход: два числа, разделенные пробелом, – первое - количество понедельников 13, второе - количество пятниц 13, между введенными датами.
Пример :
Ввод: Вывод:
1 1 2
01/01/2001
31/12/2001
Задача 46 «Вписанный квадрат»
В треугольник с длинами сторон А В С вписали квадрат так, что одна из сторон квадрата лежит на большей из сторон треугольника, а две оставшиеся вершины квадрата лежат на других сторонах треугольника. Написать программу, которая вычисляла бы периметр вписанного квадрата.
Вход:А В С - разделенные пробелами длины сторон треугольника.
Выход:одно число - периметр вписанного квадрата.
Пример:
Ввод: Вывод:
4.00 2.4 2.4 3.985
Задача 47 «Контрольные суммы»
При зашифровке текста для каждого слова в тексте вычисляется его контрольная сумма, равная сумме порядковых номеров в алфавите букв из которых состоит слово, например: для слова ABba контрольная сумма равна (1+2+2+1)= 6. Написать программу, которая вычисляла бы количество различных отличных от нулевой контрольных сумм, встречающихся в заданном тексте. В исходном тексте до 25000 слов, слова разделены одним или несколькими пробелами, длина слова до 80 символов, для большой и малой букв порядковые номера в алфавите считать одинаковыми, в контрольную сумму слова считать только номера латинских букв, для других символов номер в алфавите считать равным нулю.
Вход: Исходный текст.
Выход: число - результат.
Пример:
Ввод: Вывод:
Good BYE, MY LoVe! 4
Задача 48 «Слово в слове»
Вводятся два слова. Написать программу, выдающую, сколько раз одно из слов встречается в другом. Слова вводятся большими латинскими буквами, длина слов до 255 букв, любая буква входит не более чем в одно вхождение одного слова в другое(см. пример теста). Ввод и данные корректны.
Вход: две строки: первая - одно слово, вторая - другое слово.
Выход: Число - количество вхождений одного слова в другое.
Пример:
Ввод: Вывод:
ABRAKADABRABRABRA 3
ABRA
Задача 49 «Гирлянда»
Новогодняя елочная гирлянда состоит из соединенных последовательно разноцветных лампочек. Гирлянда состоит из N лампочек (0<N<125) семи различных цветов, которые мы будем обозначать числами от 1 до 7 соответственно. Вводятся количество лампочек и порядок следования их цветов в гирлянде. Написать программу, подсчитывающую наибольшее количество идущих подряд в гирлянде лампочек одного цвета. Ввод и данные корректны.
Вход: две строки: первая - N количество лампочек в гирлянде, вторая - разделенные пробелами N чисел (от 1 до 7) - порядок следования цветов ламп в гирлянде.
Выход: Число - наибольшее количество идущих подряд лампочек одного цвета.
Пример:
Ввод: Вывод:
17 4
1 3 3 2 4 4 4 7 7 7 5 5 5 5 6 6 5
Задача 50 «Чемпионат»
В чемпионате принимают участие N команд, которые встречаются по одному разу друг с другом, за победу дается 3 очка, за ничью 1 очко, за поражение 0 очков. Написать программу, вычисляющую какое наибольшее число раз мог сыграть вничью в этом чемпионате «Локомотив», если он набрал Х очков. Ввод корректен, корректность данных предусмотреть, при некорректности данных вывести NO.
Вход: два числа: первое - число команд в чемпионате, второе - очки, набранные “Локомотивом” в чемпионате.
Выход: Число - максимальное количество ничьих или NO - если данные не корректны.
Пример:
Ввод: Вывод:
7 12 3
Задача 51 «Новый дом»
Три поросенка Нуф-Нуф, Наф-Наф и Ниф-Ниф имеют каждый по одному дому, которые не могут гарантировать им надежную защиту от Волка. Для надежной защиты поросята собираются построить новый дом-крепость и разместить его так, чтобы он был равноудален от их жилищ. Написать программу, которая по заданным координатам домов (все три дома различны), определяла с точностью до трех знаков после запятой, координаты нового дома.
Вход:в 3 строках по 2 числа, через пробел - координаты домов поросят.
Выход:2 числа , разделенные пробелом - координаты нового дома.
Пример:
Ввод: Вывод:
125.125 109.329 187.554
250.125
250.250
Задача 52 «Космическое горючее»
В межгалактической лаборатории изобрели новый вид компактного топлива для звездолетов, энергии одного атома которого хватает звездолету, чтобы преодолеть расстояние в полтора световых года. В ознаменование этого выдающегося открытия устраивается праздник, в программу которого входят большие гонки на звездолетах, с огромным призовым фондом. Организаторы праздника отправили N приглашений на участие в гонках. Для демонстрации нового топлива предполагается заправить им все звездолеты , участвующие в гонках, причем, чтобы все участники были в равных условиях, им необходимо выделить одинаковое количество атомов нового горючего. Организаторы не знают точного числа участников гонок (некоторые из тех, кому разосланы приглашения, могут не принять участия в гонках). Организаторы хотят заготовить К атомов нового топлива, при этом К должно нацело делиться на любое число участников от 2 до N. Новое топливо очень дорогое, поэтому организаторы хотят, чтобы число К, удовлетворяя первому требованию, было наименьшим. Необходимо написать программу, которая по числу разосланных приглашений N (натуральное, 2<=N<=1000), вычисляла бы наименьшее число атомов нового горючего - К, которое без остатка делится на любое число участников от 2 до N.
Вход: число N (количество участников, натуральное 2<=N<=1000);
Выход: длинное число – результат.
Пример:
Ввод: Вывод:
33 144403552893600
Задача 53 «Ярмарка»
Между населенными пунктами Дубово и Клиново имеется железнодорожная ветка длиной S километров и с N остановочными пунктами, прономерованными по порядку возрастания номеров по пути следования из Дубово в Клиново. Приближается ярмарка. Организаторы желают провести ее в таком месте, чтобы сумма расстояний, которые преодолели по пути на ярмарку все ее участники, была наименьшей.О каждом остановочном пункте имеются следующие сведения: Ri -расстояние от i-го пункта до Клиново ( по железной дороге ), Ki -количество участников ярмарки, проживающих в i-м пункте.Из Дубово на ярмарку поедет Z , а из Клиново - Y человек.Написать программу, выводящую номер пункта, в котором следует проводить ярмарку ( если ярмарка в Дубово - вывести 0 , если в Клиново - вывести число N+1, если возможны несколько пунктов - вывести их номера в порядке возрастания). Ввод корректен. 0 < N < 1001, 0 < Ri, S < 9001, 0 <= Ki, X, Y<= 100 000 .
Вход: N+1 строка: в 1-й строке : N- число остановок, S - расстояние между селениями, Z, Y - число участников ярмарки из Дубово и Клиново, в каждой из следующих N строк: Ri, Ki- сведения о i-м пункте.
Выход: номер или номера (в порядке возрастания) пункта(ов), где следует проводить ярмарку.
Пример:
Ввод: Вывод:
3 13 3 1 2
12 2
8 2
1 3
Задача 54 «Номератор»
Для печатания номеров пользуются 15-ти разрядным номератором, который печатает по порядку, начиная с заданного начального числа, пятнадцатизначные номера, если число имеет меньше 15-ти разрядов то вместо отсутствующих разрядов печатаются ноли. На печатание каждой цифры расходуется краска, ее расход пропорционален длине ломаной линии, изображающей цифру. Высота цифры в два раза больше ее ширины, цифры имеют следующие формы:
Н
аписать
программу, которая вычисляла бы
минимальный, из заданного интервала
(А В), номер, начиная с которого
для печати серии из К номеров
расходуется минимальное количество
краски. 0 <= А, B
< 1 000 000 000 000 000 ; 0 < K
<= 100 000 ; A
<=B;
0 <= (B-A)
< = 1000 000; границы интервала входят
в интервал, а печатуемые номера
могут выходить за границы интервала.
Вход: 1-я строка - число А – начало интервала; 2-я строка - число В - конец интервала; 3-я строка - число К - количество номеров в серии.
Выход: одно число - результат.
Пример:
Ввод: Вывод:
987654320123456 987654321101001
987654321123456
78987
Задача 55 «Саранча»
На посевы напала саранча, каждые 8 часов ее численность утраивается, а каждые 7 часов: сначала, если ее в этот момент нечетное количество – уменьшается на 1, а затем уменьшается в 2 раза. Ее можно победить, если в момент истечения целого числа суток, с момента появления саранчи, сжечь листок с магическим числом, делящимся без остатка на 11, и равным кол-ву саранчи в момент сожжения листка. Найдите минимальное такое число, если в момент появления численность саранчи была - М. 0<М<1000 000. При совпадении моментов уменьшения и увеличения - сначала происходит уменьшение, а потом - увеличение.
Ввод: М - численность саранчи в момент ее появления.
Вывод: число-результат.
Пример :
Ввод: Вывод:
10001 648714
Задача 56 «Акр»
Одна страна состояла из одинаковых абсолютно во всем княжеств, которые были настолько одинаковыми, что различить их не было никакой возможности, возникавшие из-за этого всевозможные проблемы, неудобства и казусы можно описывать долго. Для преодоления этих трудностей король придумал ввести в каждом княжестве свою систему счисления, отличную от всех других систем счисления остальных княжеств, что и было сделано. Княжества стали называться по основанию системы счисления, принятой в данном княжестве для измерений и обозначений абсолютно во всем, при этом для обозначения и записи цифр стали использовать круглые скобки, оставили десять знаков арабских цифр (0 - 9 ), а для обозначения цифр больших 9 стали использовать соответствующие десятичной записи цифры числа, взятые в круглые скобки, например цифру 15 записывали так: (15) . Чтобы не обидеть ни какое из княжеств, их нумерацию начали с основания 11 (основания от 2 до 10 не были приняты ни в одном из княжеств). Шейх решил купить себе по одному акру земли во всех княжествах. Чтобы узнать, сколько это будет стоить, он послал по княжествам своего визиря, который, зная только десятичную систему счисления, все вычисления, выполнял в ней. Проезжая по княжествам, он - читал цены за акр земли (написанные в принятых в княжествах системах, а на самом деле - везде одинаковые, только записанные по-разному). Подсчитывал их общую сумму, опуская при этом скобки (считая скобки простой особенностью записи чисел в данной стране), и, рассматривая получившиеся, таким образом числа, как десятичные. В конце путешествия оказалось, что визирь забыл посетить какое-то одно княжество. Необходимо написать программу, которая по получившийся у визиря сумме S , количеству княжеств в стране – N и цене одного акра земли в десятичной системе счисления, определяла номерa княжеств, в которых мог не побывать визирь. Названия княжеств - натуральные числа из интервала [11 1000]. Цена акра земли не превосходит 160 000.00
Ввод: три числа, разделенные пробелом - S - сумма, получившаяся у визиря, N- количество княжеств в стране, С - цена акра земли в 10-ной системе счисления.
Вывод: числа-результаты,-названия, возможно не посещенного визирем, княжества.
Пример :
Ввод: Вывод:
1739.000 7 177.000 13
Задача 57 «Космос»
В галактике II-GV-101 в звездной системе "ZX-2000", состоящей из N объектов, некоторые из которых могут иметь совпадающие (т. е. одинаковые ) координаты в пространстве ( все три координаты различных звездных объектов одинаковы, так как координаты измеряются в световых годах, а все эти различные звездные объекты расположены, например на одном и том же маленьком астероиде, размеры которого пренебрежимо малы, по сравнению со световым годом). В звездной системе заканчивается регламентный срок эксплуатации центральной координационной станции, которая является началом отсчета внутренней координатной системы, и через станцию поддерживается координация всех коммуникационных процессов в звездной системе "ZX-2000". С момента строительства действующей координационной станции в звездной системе произошло много различных, существенных изменений, что привело к ощутимому изменению координатной конфигурации всей звездной системы (создано много новых объектов, разрушен ряд устаревших объектов). Действующая станция перестала удовлетворять, как техническим, так и координатным требованиям, по отношению к существующей на текущий момент звездной системе. В связи с этим, руководство звездной системы на совете приняло решение: в новом месте построить новую координациоонную станцию. сумма расстояний от нее до всех объектов системы должна быть минимальной, если выполняется это условие для нескольких различных мест в звездной системе, то среди них нужно выбрать такое, которое ближе всего расположено по отношению к старой, действующей сейчас, координационной станции. Составить программу, которая по вводимым данным: числу объектов в системе - N и их координатам (Xi,Yi,Zi), вычисляла бы X,Y,Z - координаты места для строительства новой станции, чтобы они удовлетворяли всем предъявляемым к месту расположения новой станции условиям. расстояния вычислять по общепринятой геометрической формуле для трехмерного пространства. Станцию можно строить только на имеющихся в системе объектах (ее координаты должны совпадать с координатами одного из объектов). Старую станцию объектом системы не считать. 0<N<1001. В случае множества решений – выдать одно любое.
Ввод: 1-я строка – N – число объектов в системе; в каждой следующей из N строк – по три координаты очередного объекта.
Вывод: три координаты, где должна располагаться новая станция.
Пример :
Ввод: Вывод:
4 1 1 0
1 1 1
0 0 1
1 1 0
0 1 0
Задача 58 «Простые гороскопы» (100 баллов)
Будем считать, что у события «простой гороскоп», если - число, месяц, год даты его начала и, а так же продолжительность в днях (дни начала и окончания включать в это число) - выражаются простыми числами (числами не имеющими других делителей кроме самих себя и единицы, число 1 - простым не является). Написать программу, которая, по введенным начальной и конечной датам, вычисляла бы наибольшее количество различных событий (события различны, если у них различен хотя бы один из временных признаков: продолжительность, дата начала или окончания) с «простыми гороскопами», продолжительностью не более Z дней, которые могли произойти между введенными датами (сами даты включаются в интервал). Данные, даты и ввод - корректны. Начальная дата меньше конечной ; 0 <Z<=10000; даты задаются в формате: ДД/ММ/ГГГГ, где ДД - две цифры - число месяца, ММ- две цифры - номер месяца, ГГГГ- четыре цифры – номер года;
Вход:1-я строка - начальная дата; 2-я строка – конечная дата; 3-я строка – максимальная продолжительность события в днях (Z) .
Выход: одно число - результат.
Пример :
Ввод: Вывод:
01/01/1900 9492
31/12/2010
3737
Задача 59 «Карнавал»
Для участия в праздничном карнавальном шествии отобраны N участников, которых сначала выстраивают в одну шеренгу по росту, а затем, по порядку следования в шеренге, перестраивают в виде прямоугольника А на В человек так, что при их перестроении все колонны и шеренги заполнены полностью и при этом ни один участник не остается вне строя. Составить программу, находящую количество различных участников, которые не могут оказаться соседями К-того по счету, от начала шеренги участника, в результате всех возможных перестроений участников. Соседями участника считать участников построения, стоящих справа, слева, впереди и позади от него в данном варианте перестроения.
Ввод: два числа: N и K – количество участников и номер участника.
Вывод: число - результат.
Пример :
Ввод: Вывод:
16 1 8
Задача 60 «Иероглифы»
Шаблон, для написания иероглифов, задается в виде матрицы смежности вершин не ориентированного (возможно псевдографа, но не мультиграфа) графа шаблона. Под иероглифом будем понимать любой (кроме нулевого) подграф, из допустимых матрицей, заданного шаблона-графа. Составить программу находящую количество различных иероглифов, которые можно нарисовать при помощи заданного шаблона. М - число вершин графа, 1<М <31 ; ввод корректен.
Ввод: 1-я строка М – число вершин графа, далее М строк - строки матрицы смежности вершин графа.
Вывод:. число - результат.
Пример:
Ввод: Вывод:
7
0 1 1
1 0 1
1 1 0
Задача 61 «Ребус»
Вводится строка – ребус, состоящая из трех слов и знаков равно и плюс (каждый матеметический знак встречается в строке ровно один раз). Написать программу, которая выдавала бы все различные целые не отрицательные решения ребуса. При поиске решений ребуса считать, что одинаковым буквам соответствуют одинаковые цифры, а разным буквам - разные, не различая при этом больших и малых букв одного алфавита.
Ввод: строка – ребус.
Вывод:. все решения ребуса.
Пример:
Ввод: Вывод:
Я+Я=МЫ 5+5=10
6+6=12
7+7=14
8+8=16
9+9=18
Задача 62 «Наибольшее простое»
Вводится натуральное число, не превосходящее числа 2147 000 000.
Написать программу, которая выдавала бы наибольшее простое число, которое возможно получить из .заданного числа вычеркиванием цифр. Можно вычеркивать любое количество (и ноль тоже) цифр. Если решения нет выдать - число 0.
Ввод: М – число.
Вывод:. число - результат.
Пример:
Ввод: Вывод:
123456 23
Задача 63 «Римское уравнение»
Составить алгоритм решения уравнения:
A*Z - B = 0 , где
A, B, Z - натуральные числа в римской нотации, не превышающие 3000, результат вывести в римской нотации. Краткие правила римской системы счисления. Числа от 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 соответственно. Меньшая цифра стоящая слева от большей этого же разряда вычитается, а справа – прибавляется, число вычисляется как сумма разрядов. Вычитать разрешено не более одной младшей для данного разряда цифры.
ПРИМЕР: СМLХХIХ = 900 + 70 + 9 = 979.
Ввод: в первой строке число - A, во второй число - B.
Вывод: решение уравнения или сообщение NO - если натурального решения нет.
Пример:
Ввод: Вывод: