Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Пятнадцатая тренировка

содержание задачника

Задача 15А. Игра с калькулятором

В калькулятор вводится натуральное число K и нажимается клавиша «+». Калькулятор все еще показывает К. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для ее достижения можно производить только одно действие — нажимать на клавишу «=» (возможно, 0 раз). После первого нажатия получается результат К + К, после очередного нажатия результат увеличивается на К. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек — тоже.
Ограничения: 1 $\le$ К $\le$ 999, время 1 с.
Ввод из файла calcgame.in. В первой строке находится одно число — К. Вывод в файл calcgame.out. Если цели достичь невозможно, вывести «Impossible», если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.
Примеры
Ввод
37
Вывод
1 3

Задача 15B. Площадь треугольника

Даны длины трех отрезков. Если возможно, требуется построить треугольник, в котором один из этих отрезков был бы высотой, один — биссектрисой и один — медианой; все отрезки должны исходить из одной вершины. Ограничения: длина каждого из трех отрезков от 0,01  до 100, точность результата должна быть 0,001, время 1 с.
Ввод из файла tria-abm.in. Вводятся три положительных числа, разделенных пробелами, — длины отрезков. Вывод в файл tria-abm.out. Выводится одно число — площадь треугольника. Если треугольник нельзя построить, вывести -1. Если может быть построено несколько треугольников с разными площадями, вывести 0.

Примеры
Ввод
4.349 4.0 5.0
Вывод
16.0
Ввод
3.1 3.1 3.1
Вывод
0

Задача 15С. Формирование поезда

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определенного числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцепления на каждом конце. У компании также есть один локомотив. Сцепления и для локомотива, и для вагонов обозначены буквой А или В. Повернуть вагон или локомотив противоположной стороной невозможно. Дана информация о вагонах и локомотиве. Требуется найти число способов сформировать разные поезда заданной длины из имеющихся видов вагонов. Дополнительным требованием является то, что тип сцеплений на каждом конце состава должен соответствовать типу сцепления локомотива.
Поезда считаются различными, если при их сравнении от одного конца к другому выявляется хотя бы одно отличие.
Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, ВА и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: ВААААВВА и ВААВВААА. Локомотив можно присоединить к поезду как с левого (используя сцепление В), так и с правого конца (используя сцепление А).
Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, ВА, BB) и локомотив AA, а поезд должен состоять из трех вагонов. Существует три способа сформировать поезд: AAABBA, АВВААА и ABBBBA.
Ввод из файла train-ab.in. В первой строке находятся N — число вагонов, находящихся в распоряжении компании, и К — требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцепления вагонов. Описания даны как AB, AA, ВВ или ВА.
Ограничения: 1 <K<N< 40, время 1 с.
Вывод в файл train-ab.out. В первой строке выводится слово «YES», если можно сформировать хотя бы один поезд, или «N0» — в противном случае. Если поезд сформировать возможно, во второй строке должно указываться количество способов это сделать.
Примеры
Ввод
4 4
АВ
АА
АВ
ВА
ВА
Вывод
YES
2

Задача 15D. Стена

Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество
ресурсов (смотрите рисунок).  Ваша задача — помочь бедному Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.
Задача слегка упрощается тем, что замок Короля представляет собой многоугольник и расположен на плоской поверхности. Архитектор уже сопоставил замку прямоугольную декартову систему координат и точно определил координаты каждого угла замка в футах.
Ввод из файла wall.in. Первая строка содержит два целых числа N и L, разделенных пробелом: N — число углов в замке Короля, a L — минимальное число футов, на которое Король разрешил приблизить стену к замку. Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа х_i и у_i разделенных пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.
Ограничения: 3 $\le$ N$\le$1000, 1 $\le$ L $\le$ 1000, -10 000 $\le$ х_i, у_i $\le$ 10 000, время 2 с. Вывод в файл wall.out. Выводится единственное число — минимальная длина стены в футах, которая может быть построена вокруг замка согласно требованиям Короля. Представить Королю длину стены нужно в виде целого числа футов, потому что вещественные числа еще не изобретены. Однако результат нужно округлить так, чтобы он отличался не более чем на 8 дюймов от правильного (1 фут = 12 дюймов), потому что большей неточности Король не потерпит.
Пример
Ввод
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
Вывод
1628

Задача 15E. Семечки

На базаре есть ряд из N мест, где продаются семечки подсолнечника. Потенциальные покупатели идут вдоль ряда, затем в некоторый момент останавливаются и покупают семечки. Качество семечек от места к месту различается незначительно, так что разница только в цене семечек и положении места. Перед тем как выйти на рынок в качестве еще одного продавца семечек, вы провели исследование рынка, чтобы найти зависимость числа покупателей от двух названных факторов. Исследование показывает, что большинство покупателей следуют одному и тому же шаблону. Они проходят мимо нескольких мест, замечая и запоминая цены, а затем после обхода К мест возвращаются к месту с наименьшей замеченной ценой, совершают там покупку, затем покидают базар. Если есть несколько мест с одинаковой ценой, покупатель выбирает ближайшее.
Предположим, что есть пять мест с ценами 37, 34, 34, 35, 33. Если покупатель с К = 4 идет слева направо, он видит семечки по ценам 37, 34, 34, 35. В этот момент он решает, что видел достаточно, возвращается к третьему месту и покупает семечки там. Хотя на втором месте цена та же, что и на третьем, покупателю до него идти дальше. Если бы тот же покупатель зашел справа, он бы увидел цены 33, 35, 34, 34, затем остановился и вернулся бы к пятому месту. Число мест, пройденных до принятия решения (К), является функцией жадности и терпеливости покупателя, и, очевидно, различается у разных покупателей.
Исследование выявило средний процент В_к покупателей для всех значений К (1$\le$N$\le$N, $0\le B_K\le 99$, $B_1+B_2+...+B_N=100$.
Вам следует определить оптимальную стратегию на этом рынке (то есть цену и положение нового места, которое максимизирует ожидаемый средний доход) в предположении, что половина клиентов идет в направлении от первого места к N-му, а другая половина — от N-то места к первому, и они следуют описанному шаблону.
Ввод из файла seeds.in. В первой строке находится число существующих мест N, во второй строке — N целых чисел — цены на каждом месте, в третьей строке — N целых чисел в диапазоне от 0 до 99 — значения В_к для каждого К. Все числа в строках разделены пробелами.
Ограничения: 2 $\le$ N $\le$ 100, исходные цены — целые числа от 1 до 9999, время 2 с. Вывод в файл seeds.out. Выводятся два целых числа — L и P. L (0 < L < N) — это число существующих мест, после которых должно быть размещено новое (вам не разрешается устанавливать свое место первым или последним). Число Р— оптимальная цена. Если существует более чем одно оптимальное решение, вы должны выбрать решение с минимальным L, а среди них — с минимальным Р.
Пример
Ввод
5
37 34 34 35 33
10 20 30 30 10
Вывод
2 33

Задача 15F. Умножение многочленов

Ввести в символьной форме два многочлена от х с целыми коэффициентами и вывести их произведение в порядке убывания степеней — также в символьной форме. Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 104, время 1 с.
Ввод из файла polymul.in. В двух строках находятся многочлены. Вывод в файл polymul.out. В единственной строке выводится многочлен.
Примеры
Ввод
0
0
Вывод
0
Ввод
-5
x^2+x+x-2x^3
Вывод
10x^3-5x^2-10x

содержание задачника