|
Рис. 4
Если N = 3, то требуется обойти уже все целочисленные точки прямоугольного параллелепипеда P 1 3 будем поступать подобным же образом. Сначала обойдем все точки N-мерного параллелепипеда, за исключением тех, у которых координата x равна 1, заканчивая обход в точке (2, 1, 1, :, PN ), а затем возвращаемся в начальную точку, обходя все точки с x = 1.
Задача g6_1050: Лесной пожар (XIII Всероссийская олимпиада по информатике)
В МЧС поступило сообщение о возможном лесном пожаре в заданном квадрате тайги. Для поиска места возгорания было послано N самолетов. Однако ни один из экипажей пожара не обнаружил.
Известно, что с самолета видна полоса тайги, границы которой находятся на расстоянии 50 км справа и слева от той линии на поверхности Земли, над которой пролетает самолет (см. рисунок), причем точки, находящиеся на расстоянии ровно 50 км от этой линии, все еще видны. Донесение с каждого самолета содержало информацию о том, в каких двух различных точках (xb , yb ) и (xe , ye ) самолет входил в заданный квадрат и покидал его соответственно. Между этими точками самолет двигался строго по прямой.
Рис. 5
Требуется
Написать программу, которая определит, действительно ли весь заданный квадрат тайги был просмотрен с самолетов. Если это не так, то программа должна находить координаты какой-нибудь точки, лежащей внутри или на границе квадрата и не попавшей ни в одну из просмотренных полос.
Входные данные
Входной файл с именем FIRE.IN состоит из N + 2 строк.
В первой строке записано натуральное число L - размер заданного квадрата тайги в километрах (0
Выходные данные
Выходной файл с именем FIRE.OUT должен содержать одну строку. Если заданный квадрат был просмотрен полностью, то эта строка должна состоять из слова OK, написанного заглавными латинскими буквами. В противном случае в этой строке должны быть записаны через пробел координаты x и y какой-либо точки, которая не попала ни в одну из просмотренных полос. Координаты нужно выводить в километрах с ошибкой не более одного метра.
Пример входного файла
245
1
26.1 0 193.568 245
Пример выходного файла для приведенного примера входного файла
155.123 100
Примечание. Будут отдельно оцениваться решения, сделанные в предположении, что каждый самолет летел параллельно одной из сторон квадрата.
Решение g6_1050: предоставлено Е.В. Андреевой
Несмотря на то, что ширина каждой из полос составляет 100 км, непросмотренный участок может быть как угодно малым, то есть его размер по каждой из координат может быть менее одного метра. Поэтому искомый результат следует трактовать так: в окрестности найденной при решении точки должна действительно находиться по крайней мере одна непросмотренная точка, и каждая из координат этой непросмотренной точки должна отличаться не более чем на один метр от координат найденной точки. Поиск такой точки можно осуществлять следующим образом. Рассмотрим набор отрезков, который состоит из четырех сторон квадрата и 2N отрезков, образованных в результате пересечения границ полос с квадратом. Найдем все попарные пересечения этих 2N + 4 отрезков. Если непросмотренная точка существует, то она находится в окрестности одной из найденных точек пересечения.
Рассмотрим 4 угла, образованные в результате пересечения двух отрезков, обозначив точку их пересечения A (если хотя бы один из отрезков является стороной квадрата, то рассматривать следует лишь углы, лежащие внутри квадрата). Для каждого из углов найдем точки пересечения их биссектрис с ближайшим отрезком, не проходящим через точку A, обозначим их B1 , B2 , B3 , B4 (см. рис. 6). Тогда, для того чтобы проверить, не является ли один из рассматриваемых углов в некоторой окрестности точки A непросмотренным с самолетов, достаточно проверить принадлежность полосам середин отрезков [A; Bi ], i = 1..4. Причем, если в точке A пересекаются более чем 2 отрезка, то опять же достаточно рассматривать лишь попарные их пересечения, так как если непокрытый угол в окрестности точки A существует, то он образован в результате пересечения какой-либо пары отрезков и предложенный выше способ анализа углов позволит обнаружить точку, непокрытую полосами. Если же непросмотренных областей нет в окрестности ни одной из точек пересечения отрезков, то их нет вообще.
Задачу можно решать и численно. Проверим, не покрыты ли все 4 вершины квадрата одной из полос или не является ли одна из вершин квадрата непросмотренной ни из одного самолета. В любом из этих двух случаев задача решена (квадрат просмотрен полностью с одного самолета в первом случае и непросмотренная точка найдена - во втором). В противном случае делим исходный квадрат на 4 части (разделив пополам каждую из сторон) и анализируем вершины каждого из этих четырех квадратов, и т.д. Причем квадраты, все четыре вершины которых покрыты одной и той же полосой, из дальнейшего рассмотрения исключаются. В результате либо будет найдена непокрытая точка, либо размер квадрата достигнет величины, которой можно пренебречь в сравнении с машинной точностью вычислений, и тогда его можно считать просмотренным. Данный метод будет особенно эффективным, если исключить из рассмотрения касания полос, то есть считать две и более касающихся полосы за одну и ту же полосу (что по условию задачи является верным).
Задача g6_1051: Замок (XIII Всероссийская олимпиада по информатике)
В замке Stonehandge юный принц не поладил со своей гувернанткой в комнате, где они завтракали. Для избежания наказания принц решил спрятаться в одной из комнат замка. Двигаясь из комнаты в комнату, принц обязательно закрывал на ключ дверь, через которую он прошел, после чего ни он, ни гувернантка не могли воспользоваться этой дверью. Через любую комнату (в том числе и через ту, в которой находится гувернантка) принц может проходить несколько раз, если это позволяют еще не запертые им двери. Изначально все двери замка не заперты.
Между двумя комнатами замка не более одной двери. Общее количество дверей не превосходит 5000.
Гувернантка начинает искать принца только после того, как он спрятался. Избежать наказания принц может только в том случае, если гувернантка, проходя через оставшиеся незапертыми двери, не сумеет попасть в комнату, где он спрятался.
Требуется
Написать программу, которая определяет, сможет ли принц спрятаться от гувернантки, и если укрыться удается, то предлагает ему любой из возможных путей спасения.
Входные данные
Во входном файле CASTLE.IN содержится план замка.
В первой строке входного файла находится натуральное число N (1
Во второй строке входного файла содержится натуральное число K (1
В последующих N строках содержатся списки смежных комнат: в i-й строке перечислены через пробел номера комнат, смежных с i-й комнатой. Каждая такая строка заканчивается нулем.
Выходные данные
Выходной файл с именем CASTLE.OUT должен содержать следующую информацию. Если принц не сможет избежать наказания, в единственной строке файла выводится сообщение No. В противном случае в первой строке файла выводится сообщение Yes, во второй строке - количество дверей, закрытых принцем, а в третьей строке - последовательность номеров комнат, разделенных пробелами, в которых побывал принц.
Пример входного файла
4
1
2 4 0
4 1 3 0
2 4 0
1 2 3 0
Пример выходного файла для приведенного примера входного файла
Yes
3
1 4 2 3
Примечание. Будут отдельно оцениваться решения для частного случая N
Решение g6_1051: предоставлено Е.В. Андреевой
Несмотря на то что условие задачи легко переформулировать в терминах теории графов, ее решение не сводится полностью ни к одному из стандартных алгоритмов на графах, а основано на здравом смысле. Во первых, следует исключить из рассмотрения комнаты, до которых невозможно добраться из комнаты, в которой принц завтракал с гувернанткой, т.е. выделить компоненту связности графа, например, с помощью ее обхода в глубину или в ширину. Если выделенная компонента связности графа состоит только из начальной комнаты или содержит эйлеров цикл, то есть комнаты возможно обойти, обязательно проходя через каждую из дверей ровно один раз (при этом в любой из комнат можно бывать сколько угодно раз), то спрятаться в таком замке невозможно. Согласно известной теореме, несложно проверить, обладает ли граф таким свойством - необходимым и достаточным условием наличия эйлерова цикла в графе является условие четности степеней всех его вершин, то есть в каждой из комнат, включая начальную, должно быть четное число дверей.
В противном случае в замке спрятаться можно. Если в начальной комнате нечетное число дверей, то двигаться принцу можно в произвольном направлении либо до тех пор, пока он не окажется в комнате, все двери в которую уже заперты, либо пока принц не вернется в комнату, с которой он начал движение, и в ней незапертой останется ровно одна дверь. Тогда ему следует войти в эту дверь, и изолированной окажется уже гувернантка, что также является для принца спасительным вариантом. Если же в начальной комнате четное число дверей, то принцу следует сначала добраться до любой из комнат, количество дверей в которой нечетно, затем пройти по всем существующим циклам, которые начинаются и заканчиваются в этой комнате. В результате либо принц уже окажется запертым в такой комнате, либо по крайней мере одна из оставшихся двух, четырех и т.д. дверей уже не будет связана с начальной комнатой. Когда принц пройдет через нее и запрет ее за собой, гувернантка добраться до него уже не сможет. Если бы такой двери не существовало, то есть из всех оставшихся незапертыми дверей все еще можно было бы вернуться в исходную комнату, то это означало бы наличие по крайней мере еще одного цикла. Таким образом, задача решена для всех случаев.
Задача g6_1052: Олимпиада (XIII Всероссийская олимпиада по информатике)
Оргкомитет Всероссийской олимпиады по информатике выделил для некоторой области два места для участников. Однако на олимпиаду поехала делегация из N школьников.
Представители Оргкомитета при встрече на вокзале выдали членам делегации два бейджа. По Положению об олимпиаде для участия в ней надо зарегистрироваться во Дворце молодежи, куда можно пройти только по бейджам.
Для того чтобы все члены делегации проникли во Дворец молодежи, один из них предложил действовать следующим образом. Двое из членов делегации проходят с бейджами через пункт контроля, а затем кто-то из членов этой делегации, уже проникших во Дворец, тайно выносит оба бейджа назад на улицу. Эта процедура повторяется до тех пор, пока не пройдут все делегаты от этой области.
Известно, что i-й делегат тратит на проход через пункт контроля ti секунд, включая выход на улицу. Для прохода одной пары делегатов требуется время, равное времени прохода менее расторопного из этой пары.
Для каждого члена делегации время, требуемое для выхода из здания, такое же, как и для входа.
Требуется
Написать программу, определяющую, за какое наименьшее время и каким образом все делегаты области смогут проникнуть во Дворец молодежи.
Входные данные
В первой строке входного файла OLYMP.IN задается натуральное число N (2
В последующих N строках находятся натуральные числа t1 , t2 , ..., tN (по одному в строке) - времена прохода членов делегации через пункт контроля в секундах, 1 i
Выходные данные
В первой строке выходного файла OLYMP.OUT необходимо выдать наименьшее возможное время (в секундах), через которое вся делегация окажется во Дворце молодежи.
В последующих строках указывается какой-нибудь порядок прохода членов делегации за это наименьшее время, а именно тройки целых чисел, из которых первые два задают номера членов делегации, проходящих во Дворец, а третье - номер члена делегации, выносящего из Дворца два бейджа. В последней строке указываются только два числа - номера членов делегации, проходящих во Дворец последними. Все числа разделяются пробелами.
Пример входного файла
3
5
5
10
Пример выходного файла для приведенного примера входного файла
20
1 2 2
2 3
Решение g6_1052: предоставлено Е.В. Андреевой
При решении поставленной задачи можно действовать исходя из двух разумных соображений. Либо самый быстрый член делегации проводит через пропускной пункт всех остальных, причем в любом порядке (назовем этот способ стратегией А), либо два самых медленных члена делегации проходят во Дворец вместе, а бейджи затем вынесет один из двух наиболее быстрых школьников, прошедших во Дворец ранее (стратегия В), после чего задача сводится к той же, но размерностью на 2 меньше. Используя перестановочный прием, можно проверить, что любой другой порядок прохода делегации в здание можно улучшить, заменяя его на комбинацию этих двух стратегий. Остается определить, в какой комбинации следует применять стратегии А и В в том или ином случае.
Для определенности отсортируем времена прохода членов делегации через контроль по неубыванию. Теперь можно говорить, что наиболее быстрым является первый член делегации, а наиболее медленным - последний. Так как для стратегии А порядок прохода членов делегации в паре с первым не важен, а в стратегии В, наоборот, сначала надо организовать совместный проход двух самых медленных участников, то выбор начальной стратегии нужно проводить, сравнивая результирующее время прохода во Дворец двух самых медленных участников в каждом из двух случаев. В стратегии А это время равно tN + t1 + tN-1 + t1 (два самых медленных участника окажутся по очереди во Дворце, а самый быстрый вернется к делегации), а в стратегии В - t2 + t1 + tN + t2 (два самых быстрых участника проходят во дворец, затем первый возвращается и через контроль идут два самых медленных участника, а второй возвращается к делегации). В обоих случаях два самых медленных участника оказываются во Дворце, а остальная делегация - на улице. Очевидно, что для выбора стратегии нужно найти минимум из t1 + tN-1 и 2t2 (именно на это время две стратегии и отличаются друг от друга). После применения лучшей стратегии для провода двух последних участников та же задача решается уже для N-2-го и N-3-го участника. Причем заметим, что если на каком-то шаге была выбрана стратегия А, то только ее и придется использовать в дальнейшем, так как если t1 + tN-1 2 , то это же неравенство тем более будет справедливо и при замене tN-1 на tN-3. Поэтому фактически требуется лишь определить, когда со стратегии В следует переключиться на стратегию А.
Задача g6_1053: Конфуз (XV Всеукраинская олимпиада по информатике)
Пусть A - массив, состоящий из N элементов A1,...,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S = A1 + A2 + ... + AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai := S - Ai, 1
Задание
Напишите программу CONFUSE, которая по массиву B, полученному в результате K-кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).
Входные данные
Первая строка входного файла CONFUSE.DAT содержит целые числа N и K, где N - количество элементов массива B (2 Выходные данные
Единственная строка выходного файла CONFUSE.SOL должна содержать целое число, которое есть разностью max(A) и min(A).
Пример входных данных
4 2
45 52 47 46
Пример выходных данных
7
Решение g6_1053:
Пусть x - начальный массив. Сумма его элементов - S. Пусть y - массив, который получаем после преобразования, тогда S - max(x) = min(y), т.к. отнимая от константы наибольшое значение из возможных получаем наименьшее. Следовательно max(y) = S - min(x). Остальные значения массива y будут лежать в пределах от min(y) до max(y).
Найдем разницу max(y) - min(y) = S - min(x) - S + max(x) = max(x) - min(x). Применяя эту операцию K раз получим, что max(y) - min(y) = max(a) - min(a). Т.е. нам достаточно найти наибольший и наименьший элемент массива, а затем найти их разность.
Временная сложность этого алгоритма O(n). Нам достаточно одного прохода по массиву. Необходимо завести две переменных min и max и первоначально инициализировать их первым элементом массива. Затем, если очередной элемент массива больше max, то заменяем значение max на его значение, точно также для min.
Задача g6_1054: Автобусный диспетчер (XIV Всероссийская олимпиада по информатике)
На кольцевом маршруте №54 протяженностью S, проходящем мимо пансионата "Энергетик", работает N автобусов. Автобусы пронумерованы числами от 1 до N в порядке их следования по маршруту. Автобус с номером 1 движется за автобусом с номером N. Расписание составлено таким образом, что автобусы движутся с одинаковой скоростью V0 и с равными интервалами между ними. Движение автобусов контролирует диспетчер.
В 12 часов дня некоторые K автобусов одновременно снимаются с маршрута и отправляются на обед. Для восстановления равенства интервалов между автобусами, продолжающими движение по маршруту, потребуется некоторое время Т и, возможно, изменение скорости некоторых автобусов по команде диспетчера. В течение этого времени автобусы должны двигаться с постоянными скоростями из интервала [Vmin, Vmax], назначенными диспетчером. Изменение скорости движения автобуса происходит мгновенно. По истечении времени Т автобусы возобновляют движение по маршруту со скоростью V0.
Требуется написать программу для автоматического диспетчера, которая вычисляет минимальное время Tmin, за которое интервалы движения между оставшимися автобусами станут равными, и скорости движения каждого из них в течение этого времени.
Входные данные
Входной файл bus.in содержит две строки.
В первой строке находятся натуральные числа N, К, S, Vmin, Vmax и V0, где K
Во второй строке расположены в порядке возрастания K чисел - номера автобусов, снятых с маршрута. Все данные в строках разделены пробелами.
Выходные данные
В первой строке выходного файла bus.out должно находиться значение Tmin.
В каждой из последующих N - K строк должны быть по два разделенных пробелом числа - номер автобуса на маршруте и скорость его движения в течение времени Tmin. Номера автобусов упорядочить по возрастанию. Значения Tmin и скоростей выводить с точностью до 4-х значащих цифр после десятичной точки.
Пример 1
Входной файл bus.in
4 1 60 21 70 60
3
Выходной файл bus.out
0.2041
1 45.5
2 21
4 70
Пример 2
Входной файл bus.in
4 2 40 30 80 50
2 4
Выходной файл bus.out
0
1 50
3 50
Решение g6_1054: предоставлено С.В. Густокашиным
При решении этой задачи не обошлось без пеньков, о которые я споткнулся, ну а число этих пеньков, как обычно - роковое: три.
Начну со второго, как наиболее крупного и наиболее часто встречающегося. Когда программа уже отлажена и начинаю сверять решение с контрольным примером - числа сходятся, но их порядок другой. Недоумение, поиск ошибок в алгоритме - ничего.
Читаю задачу близким, убеждаю их, что ответы должны идти именно в таком порядке, а иначе автобусы должны ехать задом наперед и тут при очередном прочтении условия осеняет - О, Боже!
Они действительно едут не первый за вторым, второй за третьим и т.д., а второй за первым, третий за вторым и т.д. А это значит мною была невыполнена первая заповедь: внимательно читать условие задачи и не додумывать того, чего нет. Да и рисунки делать только сверяясь с каждым предложением задачи, я ведь нарисовал колечко и написал номера автобусов, только номера-то надо было подписывать согласуясь с условиями, а не просто используя стандартный числовой ряд - 1, 2, 3, 4. Теперь сам разбор и по ходу об остальных "граблях".
Из чего исходим: автобус, проезжающий за время TMin самый длинный путь должен иметь скорость VMax. Значит определив самый длинный путь и имея VMax из условия задачи можно рассчитать TMin. Ну, а имея время и пройденные пути за это время для других автобусов, определить скорости не составит труда.
До определения пройденных путей за время TMin сначала определим расстояния между автобусами после снятия некоторых из них с маршрута. Заодно совместим эту процедуру с запоминанием номеров оставшихся автобусов:
J:= N - K + 1;
for I:= N downto 1 do
if M[I] = 0 then inc(MDist[J])
else begin dec(J); MDist[J]:= 1; MNum[J]:= I; end;
MDist[1]:= MDist[1] + MDist[N - K + 1];
Необходимо отметить, что расстояние между оставшимися автобусами MDist[J] рассчитываем как число первоначальных интервалов между автобусами. Это первый пенек, о который я споткнулся. Сначала, не мало сумняшись, был объявлен массив MDist: array[1..10000] of real; и расчет реального расстояния, возникшего между автобусами. Понятно, что Turbo Pascal 7.0 такого громадного массива вкупе с другими (M[I] и MNum[J]) не потянул, потому появилось объявление MDist: array[1..10000] of integer; и подсчет расстояния в виде числа первоначальных интервалов между автобусами. (этой проблемы можно избежать, если использовать компилятор FreePascal)
Далее привожу текст расчета минимального времени.
Исходим из того, что первый автобус неподвижен (едет с минимальной скоростью), и рассчитываем пути пройденные остальными автобусами, запоминая максимальный и минимальный, чтобы в конце по полученным значениям рассчитать время.
MaxWeg:= 0; MinWeg:= 0; D:= 0; Flag:= false; T:= 0; VVV:= V0;
for I:= 2 to N - K do begin
Work:= MDist[I] * FInt - LInt + D;
if abs(Work)
if Work MaxWeg then Flag:= true;
if Work > MaxWeg then MaxWeg:= Work;
if Work
|