Предисловие оргкомитета и жюри
Уважаемые участники олимпиады!
Предлагаем вашему вниманию задачи 3-го тура. Максимальное число баллов, которые можно набрать в этом туре- 300. Письма с решениями, оформленные по правилам(!), отправляйте по адресу olymp@olymp.vinnica.ua в любое удобное для вас время с 13 ноября 2000 г. по 4 декабря 2000 г.
Оргкомитет и жюри олимпиады.
Задача MILITARY3
(вновь предоставлена министерством обороны)
Сержант (теперь уже старший, звание повысили за задачу прошлого тура) по-прежнему настроен научить новобранцев правильно становиться в строй. Но на очередном занятии на плацу он с ужасом увидел, что строй неупорядочен. Ощущая бесполезность своих усилий, старший сержант мысленно выделил К подряд стоящих солдат и стал смотреть, сколько раз в строю встречается такая же "живописная картинка"... Помогите старшему сержанту, который видит строй из N солдат, найти в нем такую последовательность К подряд стоящих солдат некого роста, которая встречается в этом строю наибольшее число раз.
Ограничения:
1<N<=10000, 1<=K<=10.
Рост новобранцев измеряется в сантиметрах и не превышает 250. Если существует несколько решений, можно вывести любое из них.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки- числа N и K; со второй строки - N чисел, разделенных пробелами - рост новобранцев. Программа должна вывести строку из K чисел, разделенных пробелами.
Пример:
Ввод> 8 2
Ввод> 170 174 179 196 174 179 189 185
Вывод> 174 179
Задача GRAPH3
(вновь предоставлена дизайнером фирмы "GraphSoft")
Картинка размером H на W пикселей, обертка для конфет "Сосиска в шоколаде" по-прежнему не придумывалась... На экране была все та же красная замкнутая линия толщиной в 1 пиксель. Творческий кризис прогрессировал... Ткнул я мышкой в точку внутри области, ограниченной красной линией -- появился одинокий синий пиксель. Я от нечего делать стал ставить синие точки, образующие сплошную линию, пока последняя из них не перекрасила красную точку. После этого, естественно, обертка не получилась... Вернув все в начальный вид, я повторил эти же действия для всех остальных точек внутри области, каждый раз возвращая в исходное состояние картинку после "перекрашивания" красной точки.
Сколько за это время я поставил синих точек, если каждый раз количество поставленных точек было минимальным? Для тех, кто не знаком с компьютерной графикой -пиксель имеет форму квадратика.
Ограничения:
1<H,W<=100.
Пиксели, составляющие цветную линию (кроме начального и конечного), имеют общие стороны ровно с двумя пикселями того же цвета.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - два числа H и W, а со следующих H строчек по W чисел. Красный пиксель обозначается единицей, белый - нулем. Программа должна вывести на экран число поставленных синих точек.
Пример:
Ввод> 6 7
Ввод> 0 0 1 1 1 0 0
Ввод> 0 1 1 0 1 1 1
Ввод> 0 1 0 0 0 0 1
Ввод> 0 1 0 0 0 0 1
Ввод> 0 1 1 1 1 1 1
Ввод> 0 0 0 0 0 0 0
Вывод> 19
В этом примере для 8 внутренних пикселей поставлено 2 точки и для одного - 3. Всего получилось 2*8+3=19.
Задача TOWER3
(предоставлена прорабом треста "Монументстрой")
В нашем городе решили возвести до небес памятник Александру Македонскому. Постамент поручили строить моей бригаде. По проекту он представлял собой прямоугольную призму 4х4 метра в основании и высотой N метров (личность уж больно историческая!). Для постройки мы завезли достаточное количество бетонных блоков 1х1х1, 2х2х2, 3х3х3 и 4х4х4 метра. Сколькими различными способами рабочие могут уложить
блоки при постройке постамента?
Ограничения: 1<=N<=1000.
Ввод/вывод:
Программа должна прочитать с клавиатуры число N и
вывести на экран ответ.
Пример:
Ввод> 2
Вывод> 35
Задача Polyline3
(представлена ведущим чертежником треста "Монументстрой")
Для вычерчивания некоторых ломаных линий у меня есть набор картонных равносторонних треугольников всевозможных размеров. Я приложил их одной стороной к длинной деревянной линейке, зафиксировал и карандашом обрисовал получившийся контур, начиная от крайней левой точки самого левого треугольника и заканчивая самой правой точкой правого. Отличная получилась ломаная! Найдите координаты ее вершин, включая первую и последнюю точки. Считайте, что ось абсцисс
Совпадает с линейкой, а ось ординат направлена в ту же сторону, что и треугольники.
Ограничения:
Число треугольников не превышает 10000. Координаты вершин треугольников находятся в отрезке [0.00, 100.00].
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - количество треугольников M, а со следующих M строк по два числа -- координаты левой и правой вершин треугольника, лежащих на линейке. Программа должна вывести на экран: в первой строке - число вершин ломаной N, а в следующих N строках по два числа - координаты вершин ломаной.
Ответ должен быть получен с точностью до 0.01.
Пример:
Ввод> 3
Ввод> 4.00 9.00
Ввод> 10.00 12.50
Ввод> 2.00 6.00
Вывод> 8
Вывод> 2.00 0.00
Вывод> 4.00 3.46
Вывод> 5.00 1.73
Вывод> 6.50 4.33
Вывод> 9.00 0.00
Вывод> 10.00 0.00
Вывод> 11.25 2.17
Вывод> 12.50 0.00
Задача Game3
(предоставлена детективом-любителем)
Ловил я однажды бандита в лабиринте H на W клеток, часть из которых - стенки, а часть - коридоры. Стенами, естественно, окружен весь лабиринт, открытого выхода там не было. И у меня было гуманное оружие, которое стреляло иглами с парализующим на некоторое время ядом. Чтобы поразить бандита, мне нужно было оказаться с ним на одной горизонтали или вертикали так, чтобы между нами не было
стены. И он, и я шагать могли по очереди, и только на одну клетку, имеющую с той, в которой находится шагающий общую сторону. Если я не сумею поразить бандита за К шагов, то сам усну от усталости. Напишите программу, которая поможет мне усыпить бандита.
Ограничения:
1<H,W<=10; 1<K<=1000.
Начальные положения детектива и бандита таковы, что детектив не может сразу же поразить бандита.
Ввод/вывод:
Программа должна прочитать с клавиатуры: с первой строки - число K, со второй строки - два числа H и W, а со следующих H строчек по W чисел - карту лабиринта. Коридор обозначается числом 0, стена - числом 1, бандит - числом 2, детектив - числом 3. Затем начинается погоня. Программа должна по очереди на отдельных строчках выводить шаги детектива либо вводить шаги бандита. Шаги обозначаются буквами L, R, U, D, S, если участник погони ходит на клетку влево, вправо, вверх, вниз
или остается на месте соответственно. Погоня начинается ходом детектива и заканчивается, когда детектив оказывается на одной горизонтали или вертикали с преступником и между ними нет препятствий, или когда детектив сделает K-ый ход (детектив может подстрелить преступника и на K-ом ходу).
Пример:
Ввод> 10
Ввод> 5 7
Ввод> 1 1 1 1 1 1 1
Ввод> 1 0 3 0 0 0 1
Ввод> 1 1 1 1 1 0 1
Ввод> 1 0 0 0 2 0 1
Ввод> 1 1 1 1 1 1 1
Вывод> R
Ввод> L
Вывод> R
Ввод> L
Вывод> R
Ввод> L
Вывод> D
Ввод> S
Вывод> D
В этом примере детектив за пять ходов загнал бандита в тупик и на последнем ходу ловким выстрелом поразил преступника.