В первой строке файла rain.in расположены натуральное число N (1
Числа в строках разделены пробелами.
Выходные данные
Выходной файл rain.out должен содержать единственное число - искомую глубину с точностью до 4-х знаков после десятичной точки.
Пример
Входной файл rain.in
7 7.000
-5 10
-3 4
-1 6
1 -4
4 17
5 3
9 5
12 15
Выходной файл rain.out
15.8446
Решение g6_1060: предоставлено С.В. Густокашиным
Начнем с того, что добавим две крайних точки. Координата X первой точки совпадет с координатой x0, координата X последней - с координатой xN. Координаты Y дополнительных точек зададим заведомо больше возможной высоты слоя воды 100010000.
Запомним координаты Y и номера точек вершин и низин. Вершиной будем считать ту точку, для которых координаты Y соседних точек слева и справа меньше. Естественно за низину - ту, у которой координаты Y соседних точек слева и справа больше.
Да, крайние, искусственно добавленные точки, причислим к вершинам.
Таким образом, у каждой низины будет две соседних вершины. Рассчитаем "объем" (площадь) воды первоначально попадающей в низину как разность координат X соседних вершин умноженную на H.
При этом, не обращаем внимание на возможный переизбыток воды - наливаем "с горкой", потом разберемся с излишками.
Каждой вершине и низине поставим в соответствие "принадлежащие ей трапеции" и рассчитаем их площади. Координаты трапеций для низин начинаем с рассмотрения ближайших точек слева и справа. Естественно первая трапеция - вырожденная и представляет собой треугольник. Двигаемся до тех пор, перебирая координаты соседних точек слева и справа и рассчитывая площади трапеций, пока одна из точек не совпадет с координатой одной из вершин.
Координаты трапеций для вершин начинаем с рассмотрения ближайших точек слева и справа, координаты Y которых больше координаты вершины. Движемся от найденных точек влево и вправо до тех пор, пока одна из точек не совпадет с координатой одной из вершин.
После таких действий все рабочее поле должно быть разбито на трапеции, принадлежащие вершинам и низинам, и для каждой вершины и низины будет рассчитана ее площадь как сумма площадей принадлежащих ей трапеций.
А теперь закрутим бесконечный цикл "переливов" с двумя внутренними циклами просмотра низин.
Первый цикл назовем "перелив влево" с просмотром низин справа налево.
Если "объем" воды в низине больше ее собственного "объема" и координата Y вершины слева меньше координаты Y вершины справа, то убавляем "объем" воды, принадлежащей низине до ее собственного "объема", а излишек добавляем низине слева.
По окончании "перелива влево" запускаем цикл "перелива вправо" с "поглощением". Просмотр низин ведем слева направо. Условия перелива похожи, если "объем" воды в низине больше ее собственного "объема" и координата Y вершины справа меньше координаты Y вершины слева, то убавляем "объем" воды, принадлежащей низине до ее собственного "объема", а излишек добавляем низине справа. Если после перелива мы видим, что координата Y правой вершины меньше координаты Y следующей вершины справа, то производим "поглощение". Т.е. мы имеем случай, когда две низины с вершиной между ними зажаты между более высокими вершинами и обе низины полны.
Оставляем более глубокую низину, присваиваем ей "объем" "поглощаемой" вершины, а объем воды в преобразившейся низине будет составлять получившийся излишек при переливании. Набор трапеций "поглощенной" вершины также будет принадлежать теперь оставшейся низине. Устанавливаем флаг, что было "поглощение" чтобы после продолжить бесконечный цикл "переливов".
Если при очередном проходе не будет ни одного "поглощения", значит можно закончить бесконечный цикл "переливов" и приступать к определению самой глубокой из оставшихся низин.
Для каждой низины у нас имеется координата Y, "объем" воды и набор трапеций, принадлежащих низине. Для каждой трапеции, проверяем, залита ли она полностью и если да, то просто добавляем ее высоту к расчетной высоте воды в низине. Если трапеция залита не полностью, рассчитываем высоту воды исходя из ее "объема" в трапеции.
После просмотра всех оставшихся низин определяем самую глубокую низину.
При решении задачи возникла у меня небольшая проблема при расчете высоты воды между искусственными крайними вершинами, поскольку это вырожденная трапеция - прямоугольник. Выскочила ошибка "деление на ноль", но, я думаю, зная об этом, вы правильно решите вырожденное квадратное уравнение.
Разбор получился несколько затянутым, но задача того стоит, не обессудьте.
А теперь, самое интересное: вначале предполагалась другая задача, в которой координаты Y точек могут быть равны, а координаты X могут быть произвольны, т.е. возможны гроты и равнины. Это бы сильно усложнило задачу, но подождем олимпиаду следующего 2003 года. Спасибо за терпение.
Задача g6_1061: K-ичные числа (acm.timus.ru)
Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких, что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 Входные данные.
Во входном файле INPUT.TXT содержатся числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Вывод.
Программа должна выдать в файл OUTPUT.TXT искомое число в десятичной записи.
Пример входного файла:
2
10
Пример выходного файла:
90
Решение g6_1061:
Эта задача на acm.timus.ru предлагается в 3 вариантах. В первом ограничение N+K
Для первого варианта в принципе возможен полный перебор, но существование 2 других задач, с такими жесткими условиями, говорит нам о том, что здесь его применять нельзя. Придется подумать... что, в общем-то, нам не свойственно...
Вспомним задачу #1043 Принцип компании. Если там представить газету как 1, а буклет как 0, то получим решение нашей задачи для частного случая, когда K = 2. Попробуем применить этот метод для произвольного K.
Последовательность из 0 элементов у нас одна. Из одного элемента - K. А вот над последовательностями из двух и более элементов придется призадуматься.
Мы получим корректную последовательность длиной t если к корректной последовательности длиной t - 1 допишем любую из K - 1 цифры (кроме нуля). Т.е.:
0, 1, 2 - последовательность из 1 элемента.
Для них корректны последовательности из двух элементов:
01, 02, 11, 12, 21, 22
Однако мы не учли, что последней цифрой может быть 0, но для этого необходимо, чтобы t-1 цифра не была нулем. Как же этого добиться?
Взглянем, что у нас получилось. У нас получились последовательности длиной t, у которых последняя цифра - не ноль. Их количество равно количеству последовательностей из t-1 элемента [f(t-1)] умножить на k-1.
Получается:
f(t) = (k-1)*f(t-1) + (k-1)*f(t-2)
К любой последовательности длины n-1 мы можем дописать любую из k-1 ненулевых цифр, отсюда (k-1)*f(t-1). К любой последовательности длины n-2 мы можем дописать любую ненулевую цифру и ноль, т.е. (k-1)*f(t-1)
Ну а числа Фибоначчи мы искали уже много раз, например в задаче #1025 Домино
Задача g6_1062: Черепаха (XIV Всероссийская олимпиада по информатике)
Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики - ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.
Черепаха может ползти со скоростью, не превосходящей величины vmax. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.
Требуется определить, в какой момент времени черепаха сможет вернуться домой, съев все одуванчики и затратив на путешествие наименьшее время.
Входные данные
В 1-й строке файла turtle.in находятся 2 целых числа, разделенные пробелом: vmax (в см/мин) и d (в минутах), 0
Во 2-й строке находится число N - количество одуванчиков (в штуках). 0
В каждой из последующих N строк расположены: целое число xi - расстояние от одуванчика до начала грядки (в сантиметрах), 0
Входные данные гарантируют, что черепаха может съесть все одуванчики и вернуться домой в течение суток.
Выходные данные
Файл turtle.out должен содержать момент времени возвращения черепахи домой (в формате hh:mm), округленный до целых минут в большую сторону.
Пример
Входной файл turtle.in
3 1
1
100 00:01
Выходной файл turtle.out
01:08
Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Частичные решения для случая d = 0 будут оцениваться.
Решение g6_1062:
Опять задачка со Всероссийской олимпиады 2002 года. И опять там я ее решил только наполовину :( эвристически. Кстати мое эвристическое решение получилось длиннее и запутанней правильного.
Теперь перейдем к изложению основной идеи решения.
Во-первых необходимо считать входные данные. Время прорастания я преобразовывал в минуты, а расстояние от начала грядки - как расстояние от предыдущего одуванчика до этого. Т.е. у меня от расстояния от начала до данного одуванчика отнималось расстояние от предыдущего одуванчика до начала грядки.
Ввод данных в этой задаче достаточно муторное дело - писал минут 10-15.
Теперь подумаем над алгоритмом, по которому черепаха должна есть одуванчики. Естественно, что по пути к последнему одуванчику она должна есть все, что уже проросли, потом съесть последний одуванчик, а затем возвращаться и есть все (они уже проросли раньше последнего). Но возникает одна проблема: а что если мы придем, а последний одуванчик еще не вырос? Надо ждать, причем ждать не у последнего одуванчика, а в самом начале грядки. Это объясняется тем, что, задержавшись в начале грядки, мы сможем съесть больше одуванчиков по пути туда и меньше оставить на обратный путь.
Задача решается дихотомией. Минимум - нулевая задержка, максимум - время прорастания последнего одуванчика - условие выхода - если пришли ровно к всходу последнего одуванчика или максимум минус минимум меньше 0.1 минуты (для верности). У нас будет переменная, отвечающая за задержку, значение которой будет равно (max + min) / 2 (обозначим эту переменную wait). Также у нас будет переменная, в которой храниться значение времени в данный момент (time). При входе в цикл считаем wait, а затем time := wait. Теперь идем по всем одуванчикам от первого до предпоследнего. К времени прибавляем время проползания от предыдущего одуванчика к следующему (time := time + x[i] / vmax). Если получилось, что время, в которое мы подползли к одуванчику больше либо равно времени прорастания этого одуванчика, то увеличиваем счетчик количества съеденных одуванчиков и к времени прибавляем d.
После того, как прошлись по всем одуванчикам, кроме последнего, прибавляем к общему времени, время, за которое черепаха проползет расстояние от предпоследнего до последнего одуванчика. Теперь, если время равно времени прорастания одуванчика - то на выход, если больше - то max := wait, если меньше - min := wait.
Теперь мы определили нужную задержку и нам известно время, затраченное на путь до последнего одуванчика. Также известно, что к этому времени он уже пророс. Чтобы получить итоговое время, надо к этому времени прибавить время на съедение оставшихся одуванчиков (мы знаем, сколько мы съели на пути туда) и время на обратную дорогу (просто разделить расстояние от начала до последнего одуванчика на скорость). Ответ готов. Осталось только преобразовать его к нужному формату.
Моя программа прошла все тесты, кроме одного. Там у жюри ответ получился 19:00, а у меня 19:01. Оказывается жюри округляло число по двум знакам после запятой, а различие пошло в третьем знаке. Моя программа верно посмотрела, что количество минут не целое и прибавило еще одну дополнительную минуту. А, оказывается, не надо было. Пришлось это обработать отдельно.
Задача g6_1063: Михаил Густокашин против бюрократии
Задача классическая. Формулировка: Михаил Густокашин.
Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.
Все было бы хорошо, но вот некоторые врачи отказываются ставить подписи на справке до тех пор, пока на ней не распишется другой врач. Например, стоматолог отказался ставить мне подпись, пока я не принесу справку от психиатра, потому, что однажды его укусил один психически неуравновешенный мальчик, да так, что бедному врачу пришлось два месяца сидеть на больничном. Теперь он у всех своих пациентов требует справку об отсутствии психических расстройств. Много странностей у врачей...
Закончилось тем, что я составил список, какому врачу нужны какие справки. В первой строке моего списка (input.txt) содержится общее количество врачей (1
Если подписи всех врачей собрать невозможно, то в выходной файл (output.txt) следует вывести "NO". Если же все справки собрать возможно, то в первой строке выходного файла должно содержаться "YES", а в следующих K строках - последовательность, в которой нужно получать справки.
Пример входного файла:
4
1 2
0
2 1 4
1 1
Пример выходного файла:
YES
2
1
4
3
Решение g6_1063:
Эта задача - классическая. Именно с нее я начал свое изучение теории графов (никогда их не знал). Связи удобно представить в виде ориентированного графа:
Логично, что кружочек, в который не входит стрелочек можно смело убрать (записав его в список обхода, предварительно). Этот врач ничего не требует. Вместе с кружочком уберем и стрелочки, которые ведут от него. Эту операцию будем повторять, до тех пор, пока совсем не останется кружочков (я добыл все автографы!) или пока в результате операции не будет удалено ни одного кружочка (где-то возник цикл), т.е. все подписи получить невозможно.
Требования врачей удобно хранить в двумерном массиве K * K (таблице смежности). Если элемент a[x, y] = 1 - значит врачу x требуется справка врача y, если a[x, y] = 0, то врачу x справка врача y не требуется. Первоначально просматриваем все строки и ищем строки, в которых совсем нет единиц. Допустим, мы нашли, что такой строкой будет строка x. Теперь просматриваем столбец, с номером x, и все единицы заменяем в нем на нули (необходимая подпись получена).
Задача g6_1064: Агенты (Польская олимпиада по информатике 2000)
Из-за участившихся раскрытий своих агентов, Комитет Государственной Безопасности Бутыляндии решил провести реформу, направленную на улучшение их деятельности. Первым делом необходимо обеспечить безопасность встреч агентов. Ваша программа должна помочь в решении этой проблемы. Вам дано описание путей в Бутыляндии и начальные положения двух агентов. Ваша программа должна ответить, возможно ли безопасная встреча этих агентов.
Чтобы быть в безопасности агенты должны соблюдать такие условия:
- Агенты двигаются в течение дня, и встречаются вечером,
- Агент должен изменять место пребывания каждый день,
- Агенты могут путешествовать только по дорогам, соединяющим города (в Бутыляндии, имеются односторонние дороги),
- Агент не может двигаться слишком быстро (это может выглядеть очень подозрительным) - в течение одного дня, он не может путешествовать дальше, чем в соседний город,
- Расстояние между двумя связанными городами настолько коротко, что агент, отправившись от одного города утром, достигнет другого вечером,
- Встречей называется такое состояние, когда два агента находятся в том же самом городе в тот же самый вечер.
Задача
Ваша программа должна
- Читать число городов и описания сети путей в Бутыляндии и стартовые положения агентов из входного файла AGE.IN,
- Проверять, возможна ли безопасная встреча, и если так, то, через сколько дней,
- Выводит результат в файл AGE.OUT.
Входные данные
В первой строке файла AGE.IN, имеются два целых числа n и m, разделенные пробелом, где 1
Во второй строке даны два целых числа a1 и a2, разделенные пробелом, 1 a2. a1 и a2 стартовые положения агентов Номер 1 и Номер 2.
В m следующих строк даны пары чисел a и b, разделенные пробелом, 1 b. Эти числа означают, что имеется путь от города a к городу b.
Выходные данные:
Единственная строка файла AGE.OUT должна содержать:
- Одно положительное целое число, которое является минимальным временем (в днях) необходимым, чтобы устроить безопасную встречу двух агентов, если она возможна,
- Слово NIE (НЕ в Польском) - если такая встреча не возможна.
Пример
AGE.IN:
6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6
AGE.OUT
3
Решение g6_1064:
Во-первых, разберемся с входными данными. Естественно, что сеть дорог в Бутыляндии (в польском оригинале она называлась Byteland) представляет собой ориентированный граф, заданный списком ребер. Нам будет удобнее пользоваться таблицей смежности (двумерным массивом, который хранит в ячейке [x, y] 1 - если существует путь из x в y и 0 - в противном случае). Это делается на этапе чтения данных.
Заведем два одномерных булевских массива, с размером, равным количеству городов. Первый будет указывать, в каких городах может находиться первый агент, а второй - в каких может быть второй агент, в определенный день. Переменную, которая указывает, какой сегодня день, первоначально инициализируем нулем, а в массивах обозначим, что агенты могут находиться исключительно в начальных городах.
Теперь переходим к следующему дню. Здесь надо использовать два swap-массива, которые будут временно хранить информацию, в каких городах мы окажемся сегодня вечером. Для того, чтобы получить этот список городов, надо пройти по нашим булевским массивам и, если мы нашли, что мы можем находиться в городе x в день n, то в день n + 1 мы можем находиться в любом из городов, в который мы можем добраться из x. Занесем всю информацию об этих городах в swap-массивы, а затем заменим наши массивы на swap (наступил день n + 1). Если хоть один элемент и в первом и во втором массивах равен true (т.е. оба агента оказались в одном и том же городе), то выводим номер дня.
Гораздо сложнее все обстоит с ответом NIE. Во-первых, его надо давать в случае, если мы не можем оказаться ни в одном городе (т.е. все пути завели нас в тупик). Но возможно, что такой ситуации не будет, например, если агенты двигаются по кругу друг за другом. Здесь надо придумать какое-то другое условие выхода с ответом NIE. Самый простой вариант - поставить ограничение на количество дней, но его сложно определить. Например, если существует два кольца длиной 113 и 127 и один общий город соединяет их, то может понадобиться больше 14000 итераций для того, чтобы агенты встретились. Я не придумал эффективного способа. Разве что, поставить ограничение на количество итераций (n^2)/2. Работать это будет долго... Единственный способ улучшить такой вариант - уменьшить константу пропорциональности, т.е. выкинуть абсолютно все лишнее. Можно, конечно, поступить по другому - поставить ограничение не (n^2)/2, а n * 20, например, хотя есть шанс, что некоторые ответы будут не правильные, но по времени все должно уложиться.
Задача g6_1065: Игра в слова (II открытая Кировская командная олимпиада)
Надеемся, что вам знакома следующая игра. Выбирается слово и из его букв составляются другие осмысленные слова, при этом каждая из букв исходного слова может быть использована не более такого количества раз, которое она в нем встречается.
Напишите программу, помогающую играть в эту игру.
Входные данные
В первой строке входного файла записано выбранное для игры слово. В последующих строках задан "словарь" - множество слов, которые мы считаем осмысленными. Их количество не превышает 1000. Слово - это последовательность не более чем 255 маленьких латинских букв. Каждое слово записано в отдельной строке. Заканчивается словарь словом "ZZZZZZ" (состоящим из заглавных букв), которое мы не будем считать осмысленным. Слова в словаре, как это ни странно, не обязательно располагаются в алфавитном порядке.
Выходные данные
В выходной файл необходимо выдать список слов, которые можно получить из исходного слова. Слова должны быть выданы в том же порядке, в котором они встречаются в словаре. Каждое слово должно быть записано в отдельной строке. Список слов должен заканчиваться все тем же неосмысленным словом "ZZZZZZ".
Примеры входного и выходного файлов
C.IN
soundblaster
sound
sound
blaster
soundblaster
master
last
task
sos
test
bonus
done
ZZZZZZ
C.OUT
sound
sound
blaster
soundblaster
last
sos
bonus
done
ZZZZZZ
C.IN
windowsmustdie
summer
informatics
school
rules
olympiadisstarting
goodbymylovegoodby
exit
ZZZZZZ
C.OUT
ZZZZZZ
Решение g6_1065:
Мы уже решали подобную задачку (#1037 - Анаграммы).
Создадим два массива от a до z, в которых будем хранить, сколько раз встречается та или иная буква в слове. Первый массив отдадим на первое слово, а второй будем заполнять очередным проверяемым словом. Первоначально инициализируем первый массив нулями и пройдем по первому слову от начала до конца. Если в слове встретилась какая-то буква, то увеличим соответствующей ей элемент на 1.
Затем, заведем цикл repeat - until, условием выхода из которого будет прочтение строки ZZZZZZ. Если строка не равна ZZZZZZ, то инициализируем второй массив нулями, а затем также для всех букв этого слова будем увеличить соответствующие элементы второго массива. Теперь сравним все элементы от a до z в обоих массивах. Любой элемент первого массива должен быть не меньше элемента второго массива (иначе получилось бы, что мы использовали при составлении слова букву, которой нет в данном слове, или использовали больше букв, чем есть).
Задача g6_1066: Ездец (II открытая Кировская командная олимпиада)
В 2010 году, когда старое здание лицея, наконец, отремонтировали, вместо школьной столовой в лицее открылось кафе "Колобок" с автоматическим и абсолютно бесплатным обслуживанием школьников. Кафе было круглое, в центре располагалась весьма аппетитная статуя Колобка, а вдоль стены на одинаковом расстоянии друг от друга стояли столики. Вкусная еда, приятный полумрак, цветы на столиках: Неудивительно, что лицеисты любили проводить там свое время.
Когда лицеист заходил в кафе, он выбирал себе свободный столик, садился за него, и с помощью специального пульта, расположенного над столиком, делал заказ. Заказы исполнялись специальным устройством, которое лицеисты прозвали "ездец". Ездец представлял собой простейшего робота, который умел перемещаться вдоль стены. Он подъезжал к нужному столику и выдавал заказанное. Естественно, что на это уходило какое-то время.
Директор лицея заинтересовался эффективностью такого обслуживания. Его волновал вопрос: не слишком ли долго просиживают лицеисты за пустыми столиками в ожидании еды. Он обратились к лучшим программистам лицея с просьбой написать программу, вычисляющую среднее время выполнения заказа:
"История Лицея", Москва, Мир, 2040 г.
Постановка задачи
Вам дан список заказов: время, когда заказ поступил, и номер столика, с которого он сделан (столики пронумерованы по часовой стрелке от 1 до N).
Ездец устроен следующим образом:
Вначале он находится напротив столика номер 1 в состоянии "свободен".
Когда поступает заказ, ездец переходит в состояние "обслуживание заказа". Он выбирает кратчайший из двух путей (по часовой или против часовой стрелки) от своего текущего положения до столика, который надо обслужить. На то, чтобы переместиться к соседнему столику, ездец тратит T1 секунд. (Таким образом, если, например, ему надо переместиться от 1-го столика к 5-му по часовой стрелке, то это займет 4*T1 секунд). Подъехав к нужному столику, он тратит еще T2 секунд на выдачу заказа. Затем он снова переходит в состояние "свободен" и остается у только что обслуженного столика.
Если какой-то заказ поступает в момент, когда ездец уже обслуживает другой заказ, то вновь поступивший заказ помещается в очередь и будет обслужен, как только ездец освободится. Если за время обслуживания заказа накопится несколько вновь поступивших заказов, то они будут выполняться в порядке очередности их поступления. Никакие два заказа не поступали одновременно.
Время ожидания (удовлетворения) заказа - это время между его поступлением и временем завершения его обслуживания. Среднее время ожидания - это сумма времен ожидания для всех заказов, деленная на количество заказов.
Входные данные
Во входном файле задано число N - количество столиков (1 Затем идет число M - количество заказов (1
Выходные данные
В выходной файл вы должны поместить только одно число - среднее время ожидания заказа с тремя знаками после запятой.
Примеры входного и выходного файлов
D.IN
10
2 11
6
10 1
21 1
22 7
23 2
200 2
201 1
D.OUT
22.333
Решение g6_1066:
Вообще-то достаточно простая задача. Будем считывать заказы по одному. У нас будет переменная, указывающая на настоящий момент времени, первоначально приравняем ее к нулю. Если время поступления заказа больше чем настоящий момент, то присваиваем настоящему моменту время поступления заказа (у робота не разработана система предсказания заказов). Если же настоящий момент больше времени заказа, то прибавляем к общему времени ожидания разность, между настоящим моментом и временем заказа (робот обслуживал не нас).
Теперь будем определять время, затраченное на собственно наше обслуживание. Сначала нам необходимо определить - какое расстояние меньше - по часовой или против часовой стрелки. Это уместно вынести в отдельную функцию, которая будет выбирать минимум между abs(a - b) [едем, не проезжая через первый столик] и ((n - a + b) mod n) [проезжаем мимо первого и последнего столиков]. Прибавим к настоящему моменту и времени ожидания минимум, умноженный на t1. Теперь просто добавим к времени ожидания и настоящему моменту t2.
Осталось только вывести результат: (время ожидания) / m
Задача g6_1067: Метро (Белорусская олимпиада по информатике 2002)
В некотором городе есть метро, состоящее из N (1
В связи с изобретением принципиально нового вида транспорта метро стало убыточным, и его работу решили прекратить. На заседании мэрии города было постановлено закрывать каждый год по одной станции, но так, чтобы связность метро каждый раз сохранялась. При закрытии какой-либо станции, линии, ведущие из этой станции в другие, естественно, тоже перестают функционировать.
Задание. По введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным. Например, пусть метро выглядит так, как показано на рисунке. Тогда станции можно закрывать, например, в порядке 1, 2, 4, 3, 5. А порядок 3, 1, 2, 4, 5 - не подходит, так как после закрытия 3-й станции метро распадется на четыре не связных между собой части.
Ввод. Первая строка входного файла будет содержать числа N и M. В следующих M строках находится информация о линиях. Каждая из этих строк содержит через пробел числа Ai и Bi (Ai Bi) - две станции, которые соединяет i-я линия.
Вывод. Выходной файл должен состоять из N строк. Каждая строка должна содержать одно число - номер станции. Вывести станции нужно в порядке их закрытия.
Пример
input.txt
5 4
3 1
3 2
3 4
3 5
output.txt
1
2
4
3
5
Решение g6_1067:
Сначала я вспомнил самарское метро и решил, что эта задача очень похожа на #1063 - Михаил Густокашин против бюрократии. Но потом я вспомнил московское метро (кольцевую линию) и понял, что этот метод не пройдет. По крайней мере, не пройдет с теми входными данными, которые нам даны.
Ну и ладно. Придется решить задачу по-другому.
Воспользуемся поиском в глубину или в ширину на графе. Я пользовался поиском в глубину, т.к. время написание процедуры поиска в глубину меньше времени написания процедуры поиска в ширину. Естественно я использовал рекурсивную процедуру, а на выходе из нее, заносил номер вершины в специальный массив. Чтобы получить ответ, необходимо просто вывести этот массив с начала.
Как же это работает? Допустим, мы рассматриваем какую-то станцию, у которой в остовном дереве есть потомки. В силу порядка заполнения нашего массива, все ее потомки будут стоять перед ней, т.е. и удаляться раньше нее. С остальными станциями она будет иметь связь - например, через станцию №1 (если начинать обход с нее). После того, как все ее потомки будут удалены - можно спокойно удалять и ее - даже если кроме потомков в остовном дереве, она была связана с другими станциями, то в них существует другой путь (по маршрутам остовного дерева).
Сложность алгоритма, в зависимости от реализации, либо O(N2), либо O(M). А вот памяти он потребляет O(N2).
Задача g6_1068: Террористы (Украинские учебно-тренировочные сборы 2001. Оригинальное название "Игра")
В стране есть несколько аэропортов, и рейсы между ними. Можно долететь с одного аэропорта до другого, возможно с пересадками, но для любой пары аэропортов существует единственный маршрут перелета.
Два террориста играют в такую игру. Они делают ходы по очереди. Каждый ход состоит из таких операций. Игрок минирует аэропорт, выбирает рейс и улетает вместе с коллегой. После взлета он активирует взрывное устройство, в результате чего аэропорт взрывается и все рейсы до и из этого аэропорта отменяются. После приземления в другом аэропорту ход переходит к другому игроку. Проигрывает тот, кто не может сделать ход.
Задача
Напишите программу GAME которая по начальному списку рейсов и номеру аэропорта где в начале игры находятся террористы определит кто победит, если каждый игрок будет придерживаться оптимальной стратегии.
Входные данные
Первая строка входного текстового файла GAME.DAT содержит два целых: N - количество аэропортов (N
Выходные данные
Единственная строка выходного текстового файла GAME.SOL должна содержать 0, если первый игрок проигрывает, или номер аэропорта, в который необходимо полететь, если первый игрок выигрывает. Если есть несколько "выигрышных" аэропортов, необходимо найти аэропорт с минимальным номером.
Пример входных данных
4 3
3 2
3 1
1 4
Пример выходных данных
2
Решение g6_1068:
Веселая задача! Во-первых, прочитаем первое условие: "для любой пары аэропортов существует единственный маршрут". Ясно, что структура данных, используемая в этой задаче - дерево. Его можно хранить, как динамический список сыновей, например, для каждой вершины указывая на левого сына и правого брата. Но структура данных - не самое главное в этой задаче, а самое главное - сама суть решения.
Теперь я приведу свой рисунок дерева для входных данных (ну не умею я рисовать!), а потом объясню, что означают цифры слева и справа от кружков:
Итак, перейдем к значению левой цифры: она означает четность вершины, т.е. расстояние от корня дерева, до этой вершины. Это понадобиться нам в некоторых случаях для определения того, какой игрок выиграл. Если вершина не имеет сыновей (т.е. лететь больше некуда), и ее четность равна 0 (ход первого игрока), то первый игрок, летя таким маршрутом, проигрывает; если же четность равна 1 и у вершины нет сыновей, то проигрывает второй игрок. Кстати, какой игрок выигрывает или проигрывает показывает цифра справа от кружка - если выигрывает первый игрок, то эта цифра равна 1, если проигрывает -1.
Теперь будем определять, выиграет или нет игрок в вершине, у которой есть сыновья. Если вершина имеет 0 четность (ход первого игрока), то, естественно, он должен выбрать среди сыновей такой маршрут, который обеспечивает ему выигрыш - т.е. если среди его сыновей есть сын с числом 1 справа, то первый игрок может выбрать выигрышный маршрут и этой вершине также присваивается значение 1. Если же четность вершины равна 1 (ходит второй игрок), то он должен стараться выбрать наихудший вариант для первого игрока, т.е. если у вершины есть сын с выигрышем -1, то и этой вершине присваивается -1.
Технически это реализуется с помощью рекурсивной процедуры и динамического массива. Если значения потомков не определены, то для них запускается рекурсивная процедура, если вершина не имеет потомков, то в динамический массив записывается выигрыш исходя из определенного нами правила. Если же значения всех потомков определены, то среди них выбирается наибольший или наименьший, соответственно четности вершины, и этот результат также записывается в массив.
Здесь было бы уместно применить альфа-бета отсечение, т.е. если при 0 четности мы нашли сына с выигрышем 1, то можно не искать других сыновей, однако нам надо найти наименьший номер аэропорта, в который надо полететь, а альфа-бета отсечение может "отсечь" этот вариант, так что придется обходиться без него.
Кстати, поиск номера выигрышного аэропорта надо осуществлять так: идем по всем аэропортам, начиная с наименьшего, и, если этот аэропорт имеет выигрыш 1 и не имеет сыновей, проверяем, все ли его предки имеют выигрыш 1 (для этого в списке надо хранить также указатель на предка). Если все предки имеют выигрыш 1, то выводим номер этого аэропорта. Поиск такого аэропорта можно организовать и по-другому.
Задача g6_1069: Школы (XIV Всеукраинская олимпиада по информатике)
С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии "Майбуття" к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником "Майбуття", либо с одной из тех школ, которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Задание
Напишите программу SCHOOLS, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла SCHOOLS.DAT находятся два натуральных числа, разделенных пробелом: N (3
Пример входного файла
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Выходные данные
В единственной строке выходного файла SCHOOLS.SOL должны содержаться два натуральных числа S1 и S2, разделенных пробелом - две наименьшие стоимости схем (S1
Пример выходного файла
110 121
Решение g6_1069:
Ясно, что мы имеем дело с графом, из которого нужно выделить некоторую компоненту, такую, что каждая вершина графа входит в эту компоненту. Сумма всех ребер этой компоненты должна быть наименьшей. Назовем эту компоненту остовным деревом минимального веса.
Существует два основных алгоритма нахождения остовного дерева минимального веса - алгоритм Прима (работает за O(n2), n - количество вершин в графе) и алгоритм Крускала (O(e*loge), e - количество ребер в графе). Первый алгоритм реализуется проще, поэтому задачу будем решать пользуясь им.
Цепляем электропитание к любой школе (это бесплатно, так как каждая школа должна быть элементом дерева, то стартовой можно выбрать любую, для определенности первую). Теперь нужно поговорить о структуре данных, хранящую связи между школами. Я использовал две таблицы смежности размером 100*100 (это даже в BP укладывается). Теперь перейдем к построению остовного дерева. Обозначим множество всех вершин буквой G, а множество вершин дерева - T. На каждом шаге к множеству T будем присоединять одну вершину из множества G/T (G исключая T), такую, что стоимость соединения этой вершины с T меньше, чем стоимость соединения любой другой вершины с множеством T. Для приведенных входных данных порядок включения вершин будет такой: 1, 2, 4, 5, 3.
Множество вершин T можно представить в виде одной вершины, т.е. завести для нее одномерный массив, хранящий стоимости соединения ее с вершинами, не входящими в T. Первоначально множество связей T будет совпадать с множеством связей первой школы, затем, выбираем из этого множества связь с наименьшим значением (самую дешевую линию) и добавляем к T вершину, на которую указывает эта связь. Теперь, если для какой-либо вершины из G/T стоимость проложения линии от добавленной вершины меньше, чем от T, то заменим стоимость проложения линии от T до этой вершины на стоимость проложения линии от этой вершины до вновь добавленной.
Может быть немножко путано, но я старался избежать теории, показав только практику.
Информацию о том, от какой вершины (кроме массива со стоимостями связей T надо хранить также массив, указывающей из какой вершины T исходит эта связь) до какой была проложена линия будем заносить во второю таблицу смежности.
После первого выполнения процедуры поиска мы получим первый вариант прокладки линий во второй таблице смежности. Теперь нам нужно найти второй вариант. Ясно, что второе остовное дерево должно отличаться от первого, т.е. не содержать хотя бы одного ребра, которое принадлежит второму остовному дереву. Эти мы и воспользуемся - будем по одному удалять ребра первого остовного дерева из данного графа и искать другое остовное минимального веса, не забывая после этого поиска восстанавливать ребро.
Задача g6_1070: Блокада (Всероссийская командная олимпиада среди школьников 2001)
Государство Флатландия представляет собой прямоугольник размером M * N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2
Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.
Король соседнего с Флатландией королевства Ректилания решил завоевать Флатландию. Для этого он хочет захватить столицу Флатландии. Однако он знает, что сил его армии недостаточно, чтобы сделать это сразу. Поэтому сначала он хочет окружить столичную провинцию, чтобы ослабить силы противника долгой блокадой, а потом захватить столицу.
Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.
Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить. Захватывать столичную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.
Формат входных данных
Первая строка содержит M и N (3
Формат выходных данных
Выведите в выходной файл единственное число - количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите "-1".
Примеры
input.txt
5 6
BBBBBZ
BCCCBZ
BCAbbZ
BDDDbZ
ЗЗЗЗЗZ
output.txt
4
Решение g6_1070:
Да... Первый новый разбор за 2 месяца. Но ничего, привезу компьтер в общагу - может быть ситуация проясниться, а сейчас - каникулы.
Представим связь между провинциями в виде двумерной таблицы смежности от chr(31) до chr(255), заполненной 255. Теперь эту таблицу надо заполнить. Если мы пишем на FP (а теперь мы пишем только на нем, т.к. теперь это официальный язык личной и командной олимпиад школьников), то проблем не возникает - загоняем все символы в массив char 200*200. Если мы все же пишем на BP, то заведем двумерный массив, [1..200, 1..2], где будем хранить предыдущую и нынешнюю строку. Тоже очень несложно реализуется. Условимся, что Флатландию полностью окружает провинция chr(31). Теперь будем устанавливать связи между провинциями. Пройдемся по всему массиву, в котором храниться карта Ректаландии и для каждой клеточки определим ее соседей. В таблице смежности обозначим, что существует связь между провинцией имеющей код клетки, в которой мы находимся и ее соседкой. Для граничных клеток (они легко определяются по координатам) установим, что они граничат с chr(31). Это можно реализовать по-другому, например, расширив карту на 1 в каждую сторону и предварительно заполнив chr(31) - меньше писанины, что архиважно, особенно на командных олимпиадах.
Теперь у нас есть таблица смежности. Найдем все провинции, с которыми граничит столица, и отметим их в булевском массиве. Теперь воспользуемся алгоритмом Флойда (пишется очень быстро, но работает медленнее чем Дейкстра, но в данном случае это неважно - главное побыстрее наколотить программу).
for k := chr(31) to chr(255) do
if k 'A' then for i := chr(31) to chr(255) do
for j := chr(31) to chr(255) do
if (a[i, j] 1) and (a[i, k] 0) and (a[k, j] 0)
then a[i, j] := a[i, k] + a[k, j];
Заметим, что через провинцию A мы не можем пройти к границе, т.к. мы не можем ее захватить.
Теперь пойдем по всем провинциям, которые граничат со столицей. Если для какой-либо из них расстояние до chr(255) равно 255, то выводим -1 - эта провинция окружена столичной. Если же такой ситуации не происходит, то из всех расстояний выберем наименьшее - оно и будет минимальным количеством провинций, которые необходимо захватить, чтобы добраться до провинций, окружающих столичную. Правда, в силу того, что мы считали chr(31) провинцией от этого результата надо отнять единицу. Теперь сложим количество провинций, окружающих столичную, с количеством провинций, которые необходимо захватить, чтобы добраться до них от границы. Это будет окончательный ответ.
Кстати, эту задачу также разбирал Андрей Станкевич - человек намного более опытный в олимпиадных задачах и обучении методам их решения, чем я. Можете поискать его вариант разбора на сайте neerc.ifmo.ru/school. Посмотрите комментарии к задачам Всероссийской командной олимпиады 2001.
Задача g6_1071: Форум (Всероссийская командная олимпиада среди школьников 2002)
Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.
После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.
Формат входных данных
Первая строка входного файла содержит целое число N - количество сообщений в форуме
(1
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.
Длина всех сообщений не превышает 100 символов.
Формат выходных данных
Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке.
Пример
forum.in
7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи
forum.out
Олимпиада по информатике
Решение g6_1071:
Каждую тему в форуме можно представить в виде дерева, т.е. первое сообщение - это корень дерева, остальные - ветви и листья. Нам необходимо найти дерево с максимальным количеством элементов и вывести тему, которая соответствуют корню этого дерева.
Я делал это таким методом: каждое дерево я преобразовывал в другое дерево, не имеющее ветвей. Т.е. ответ на какое-то сообщение, принадлежащее данной теме, делал ответом на первое сообщение в теме.
Такое преобразование делается очень просто: создаем массив, для каждого элемента содержащий номер его предка; если сообщение - начало новой темы (т.е. ответ на сообщение 0), то номер предка этого сообщения - его собственный номер, если же сообщение не является началом новой темы, то его номер предка равен номеру предка его отца. Т.е. на рисунке у сообщения 1 предок равен самому себе, у сообщения 2 отец - 1 сообщения, следовательно, предок 2 также 1, у 3 сообщения отец - 2 сообщение, его предок - 1, значит и предок 3 - 1 и т.д.
Теперь есть много способов подсчитать наиболее популярную тему, я делал это прямо по ходу преобразования деревьев. У меня был заведен массив, в котором содержалось количество элементов в дереве, корнем которого является элемент массива. Затем следует найти максимальный элемент массива (это также можно делать по ходу преобразований) и вывести соответствующую ему тему. Темы надо хранить в массиве строк с длиной 30 (он хорошо помещается в памяти), а сообщения вообще хранить не надо, а считывать их readln.
Задача g6_1072: Столица (Всероссийская командная олимпиада среди школьников 2002)
В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.
Император решил построить n+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.
Формат входных данных
Первая строка входного файла содержит число N - количество городов (1
Формат выходных данных
Выведите в выходной файл два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.
Примеры
capital.in
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2
capital.out
1 1
capital.in
4
0 0
1 1
0 1
1 0
capital.out
0 2
Решение g6_1072:
Рассмотрим проекцию на ось x (координата y не влияет на расстояние по x, т.к. все дороги параллельны осям координат). Возьмем два крайних города (с наибольшей и наименьшей координатой). Если бы были только два этих города, то столицу можно было бы расположить в любой точке, между этими городами - суммарное расстояние до них равно расстоянию между городами. Если же столицу расположить вне отрезка, ограниченного двумя крайними городами, то суммарное расстояние будет больше расстояния между городами, а этого нам не надо.
Теперь рассмотрим пару предпоследних городов: для нее также должно выполняться это условие. Точно также оно должно выполняться для всех пар городов. Получается, что координата столицы по x должна лежать в отрезке между двумя средними городами (если городов нечетное количество, то столица должна быть в окрестностях среднего города). Т.е. нужно отсортировать координаты по x и выбрать за координату столицы средний элемент. Точно также нужно поступить и с y проекцией.
Мы знаем приблизительные координаты столицы (средние элементы отсортированных массив координат городов), попытаемся получить ее точные координаты. В клетке, которую мы выбрали, может находиться другой город, а столицу надо построить на свободном месте, так что этот вопрос надо как-то решать.
Это проблема решается небольшим перебором в окрестности этой точки, которая имеет заведомо большую площадь, чем могут занимать все города вместе взятые. Я использовал квадрат со стороной 23 и центром в точке с приблизительными координатами столицы. Мы должны перебрать все точки в этой окрестности и, если в некоторой точке нет города, посчитать сумму расстояний от нее до всех городов и выбрать среди всех точек такую, сумма расстояний для которой будет наименьший.
На олимпиаде мы так и не решили эту задачу, несмотря на то, что Андрей Шулятьев придумал правильный алгоритм, но я тогда смог разубедить его в правильности такого решения. Сила слова, что называется...
Задача g6_1073: Три города (Всероссийская командная олимпиада среди школьников 2002)
В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.
Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).
Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).
Формат входных данных
Первая строка входного файла содержит число N - количество городов (3
Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.
Формат выходных данных
Выведите в выходной файл три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них.
Примеры
three.in
5
1 3
1 3
3 1 2 4
2 3 5
1 4
three.out
1 2 5
three.in
5
1 3
1 3
4 1 2 4 5
1 3
1 3
three.out
1 2 4
Решение g6_1073:
Наверно, "Три города" - самая интересная задача командной олимпиады 2002. Перед тем как ее решать, придется подумать (это нам не свойственно, поэтому на олимпиаде мы ее, естественно, не решили).
Итак, необходимо найти расстояние между тремя наиболее удаленными городами. Вполне логичным представляется, что все три города должны быть крайними (т.е. быть соединенными только с одним городом), кроме случая, когда все города расположены в цепочку, но его мы рассмотрим отдельно.
Выберем произвольный город (назначим его первым городом) и будем считать его корнем нашего дерева. Определим расстояния от корня до всех вершин этого дерева. Та вершина, расстояние до которой будет максимально, будет вторым городом. Теперь надо найти третий город, это делается хитрым образом: для каждой вершины, в которую ведет только одна дорога, кроме корня дерева, пойдем рекурсивно вверх, к корню дерева, записывая в каждой вершине, какое максимальное расстояние до листа и номер этого листа.
Теперь пойдем от нашего второго города к корню, выполняя на каждой вершине (обозначим эту вершину за D, а наши три города за A, B и C) следующие операции: из всех детей выберем того, у которого не совпадает конечный лист и расстояние до его конечного листа максимально.
Вершина C, такая, что расстояние CD будет максимальным и будет третьим городом. Действительно, сумма расстояний AD и BD не зависит от D. А расстояние CD входит в сумму расстояний между тремя городами дважды. Т.е. расстояние между тремя городами равно AB * 2 + max(CD) * 2.
Для того чтобы найти лучший вариант, необходимо перебрать все возможные города, выбирая их за город A. На самом деле это вовсе не обязательно, т.к. все три города должны быть крайними городами, то выбирать за город A город, который соединен более чем с одним городом, нет смысла.
Теперь о тонкостях технической реализации. Во-первых, необходимо посчитать расстояние от корня дерева до всех узлов дерева. Я делал это рекурсивной функцией, т.к. городов не так уж много, а рекурсия пишется очень быстро. Во-вторых, следует подсчитать для каждого узла расстояние до наиболее далекого листа. Я также делал это рекурсивной функцией, которая запускалась для каждого листа, кроме корня дерева. Она шла к отцу узла (массив отцов строился на этапе подсчета расстояний от корня дерева) и, если для него расстояние до самого дальнего листа меньше, чем наименьшее расстояние, то записываем туда новое расстояние и в другой массив записываем, что конечный элемент (когда-нибудь он станет Ci) изменился, затем увеличиваем расстояние на 1 и переходим к отцу этого элемента.
После того, как рекурсивная функция запустится для всех листьев дерева, начнем распутывать все от вершины B. Перейдем к отцу вершины B и для всех его детей (кроме отца узла, ведь он тоже записан как потомок дерева) выберем среди таких, последний лист которых не равен B, тот расстояние для которого наибольшее. Последний лист этого элемента обозначим за C и запомним его, если DC больше максимального DC на данный момент.
Перейдем к отцу этого узла и т.д., пока не достигнем корня дерева. Если сумма расстояний между тремя городами (она равна AB * 2 + max(CD) * 2) больше максимальной суммы на данный момент, то запоминаем A, B и C.
Испробовав все A, мы найдем-таки лучшую тройку A, B, C, или получим, что C = 0. В таком случае, надо выбрать произвольное C не равное A и B - значит, все города лежат в цепочке.
Надеюсь, что что-нибудь понятно.
Задача g6_1074: Простые гири (?)
Имеются гири с массами: 1 г, 2 г, ..., N г (N
Входные данные:
Входной файл input.txt содержит число N.
Выходные данные
В выходном файле output.txt выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.
input.txt
7
output.txt
1 6
7 4
5 2
Решение g6_1074:
Для решения этой задачи можно воспользоваться теоремой о том, что между натуральным n и 2 * n существует хотя бы одно простое число. Доказательства ее я не знаю, но оно нам не понадобится - информатика - великая наука :)
Итак, найдем наименьшее простое число M, лежащее между N и 2 * N. Естественно, его можно представить в виде суммы двух слагаемых из ряда чисел от 1 до N. Переберем и выведем все такие пары, следя за тем, чтобы числа в них не повторялись. Теперь мы можем найти оставшиеся пары, решив ту же самую задачу для числа N = M - N - 1, т.е. взяв за максимум первое неиспользованное число. Когда N станет равным нулю, то это будет означать, что все пары уже найдены.
Задача g6_1075: Folding (?)
Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом повторяющихся последовательностей в ней. Например, возможный способ представить последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел формальное понятие упакованной последовательности так:
Последовательность, содержащая один символ из диапазона 'A'..'Z' считается упакованной последовательностью. Ее распаковка возвращает тот же символ.
Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Причем, если результатом распаковки S является S', а Q - Q', то SQ распаковывается в S'Q'.
Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное целое число, большее 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.
Согласно этому определению легко распаковать любую запакованную последовательность. На Билл более заинтересован в обратной операции. Он хочет запаковать данную последовательность так, чтобы результирующая запакованная последовательность содержала как можно меньше символов (включая цифры и скобки).
Input
Входной файл содержит одну строку, состоящую не менее, чем из одного и не более чем из 100 символов в диапазоне 'A'..'Z'. Output
Запишите в выходной файл одно число - длину кратчайшего из вариантов запаковки исходной последовательности. Sample input and output
folding.in
AAAAAAAAAABABABCCD
folding.out
12
folding.in
NERRCYESYESYESNEERCYESYESYES
folding.out
13
Решение g6_1075:
Для решения задачи надо воспользоваться динамическим программированием. Т.е. нам необходимо придумать, что и как мы будем хранить и как этим пользоваться.
Здесь логично завести двумерный массив, первый индекс будет означать позицию, с которой начинается сжимаемая подстрока, второй - длину подстроки.
Легко заметить, что последовательность, состоящую менее чем из 5 символов, сжать невозможно. Т.е. первые четыре столбца нашей матрицы мы можем смело заполнять количеством символов, т.к. эти строки сжать невозможно.
Теперь рассмотрим, как определить наименьшее количество символов в строке C[I, K]: здесь существует два варианта. Пусть K делится на H, тогда попытаемся разделить нашу подстроку на части длины H и проверим, не равны ли все эти части между собой. Если они равны, то в таком случае подстрока будет сжиматься в C[I, H] + 2{два символа уходят на открывающую и закрывающую скобки} + f(H) символов, где f(H) - количество символов в десятичной записи числа H. Перебрав все H, выберем вариант, при котором длина упакованной подстроки наименьшая.
Второй вариант представить нашу подстроку - это разбить ее на две подстроки всеми возможными способами. Для этого надо пустить цикл J от I до I + K - 1 разбиваю нашу строку на две подстроки от I до J и от J + 1 до I + K. Перебрав все J, выберем наименьшую сумму длин подстрок, на которые мы разбиваем текущую подстроку.
Теперь из двух вариантов представления выберем наименьший - он и будет результатом C[I, K]. Ответом будет значение C[1, length(s)]. Осталось только правильно организовать два цикла, а это совсем несложно.
Задача g6_1076: Фишки (15 Всероссийская олимпиада по информатике)
Авторы: А.П. Овсяников, Т.В. Овсянникова
Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.
Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.
Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Формат входных данных
В первой строке входного файла записаны числа N и K (1
Формат выходных данных
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L - количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
fishes.in
9 3
1 0 0 1 1 0 1 1 0
fishes.out
2 1 6
1 1
0
fishes.in
3 1
1 1 0
fishes.out
0
Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.
Решение g6_1076:
Заметим, что количество фишек в одной группе не имеет никакого значения, т.к. за один обмен мы из 3 или 4 групп получаем 2. Получается, что нам нужно хранить количество фишек в группе только для того, чтобы правильно выводить позицию, с которой начинается группа, участвующая в обмене.
Необходимо завести массив A от одного до N (т.к. все группы могут состоять из одного символа) и хранить в нем позицию, с которой начинаются символы i-ой группы. Это сделать несложно - читаем последовательно символы последовательности и если символ не равен предыдущему, то сохраняем в A[i] позиция, на которой находиться данный символ (отсюда начинается новая группа) и увеличиваем i. Общее количество групп обозначим за M.
Теперь необходимо разработать алгоритм перестановки групп, чтобы добиться желаемого эффекта за наименьшее количество шагов. Будем выполнять действия до тех пор, пока количество групп не станет равным 2. Наша последовательность представляет собой последовательность групп вида 010101. Разобьем нашу последовательность на тройки и в каждой тройке произведем обмен первого элемента со вторым и в итоге, для данного примера, получим последовательность 101, а на следующем шаге 01.
Определим количество операций обмена, которые мы совершим на данном шаге: оно равно минимуму из K и количеством троек, на которые можно разбить нашу последовательность. Обозначим его за C. Теперь мы будем совершать операции обмена, меняя в каждой тройке первый и второй элементы. Эти обмены необходимо совершать только в последних C тройках нашей последовательности, оставляя первые Z = M - C * 3 элементов неизменными.
Займемся обменами элементов в последних C тройках. Пусть j - элемент, с которого начинается изменение последовательности, j = M - C * 3 + 1. Теперь, перебирая все i от C до 1, выводим все A[q], где q = M - i * 3 + 1 (начало первой группы в тройке), вывод такого число обозначает, что мы поменяли группу q с группой q + 1, это значит, что объединились группы q - 1 и q + 1, а также группы q и q + 2. Необходимо внести соответствующее изменение в массив: A[j] := (A[q + 2] - A[q + 1]) + A[q], где (A[q + 2] - A[q + 1]) - длина последовательности q + 1, которая теперь встала перед q. После этого необходимо увеличить j на 1. Отдельно рассматривается случай, когда q = 1: здесь вместо четырех участвуют три группы и поэтому менять следует не первую группу со второй, а вторую с третьей, т.е. предварительно увеличить j на 1.
Такой, казалось бы, сложный и запутанный способ решения задачи избавляет нас от использования списков или многократного присваивания массивов. Надеюсь, при внимательном прочтении и рисовании возможных вариантов и последовательности действий на бумаге все станет понятно.
|
Задача g6_1077: Квадраты 2
В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной а метров, покупатель платил а2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это, безусловно, можно было сделать, приобретя участки размером 1*1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. "Так мне будет легче общаться с Квадратной Налоговой Инспекцией", - сказал он. Сделка состоялась.
Задание:
Напишите программу SQUARE, которая находит количество свидетельств, полученных жителем.
Входные данные:
Единственная строка входного файла SQUARE.DAT содержит целое положительное число N
Выходные данные:
Единственная строка выходного файла SQUARE.SOL содержит число свидетельств, полученных в результате сделки.
SQUARE.DAT
344
SQUARE.SOL
3
Решение g6_1077:
Эта задача решается с помощью динамического программирования.
Сначала проверим, не является ли число полным квадратом. Если так, то сразу выводим "1" и заканчиваем. Если же не является, то придется потрудиться.
Заведем массив размером в 60000 элементов - в нем мы будем хранить количество участков для каждой площади. Пройдем его с 1 до N, если текущее число (i) - квадрат целого числа, то в соответствующий элемент массива записываем 1 и переходим к следующему. Если же это не так, то тут понадобиться еще один цикл (j) от 1, до тех пор, пока разность между i и j2 не станет меньше 1. Итак, мы можем узнать, сколько участков необходимо, чтобы скупить территорию i - j2; для того, чтобы скупить территорию площадью i, необходимо на один участок больше (этот участок со стороной j). Среди всех возможных j выберем минимальное количество участков для площади i и перейдем к следующему i. Этим мы полностью рассматриваем все варианты и выбираем наилучший (в этом несложно убедиться).
Задача g6_1078: Калькулятор (Командное соревнование школьников Свердловской области 2003)
автор: Денис Расковалов
Странные времена настали в Лощине Янтарной Росы. Все куда-то бегут, что-то покупают-продают, постоянно норовя обмануть друг друга. Нет былого спокойствия. Смутное время не обошло и Монастырь Светлой Луны: Никогда еще не было такого, чтобы обычный торговец пытался обмануть монахов, боязнь гнева Будды останавливала его. Но и этот страх померк перед страстью наживы.
Мудрый Настоятель подозревает, что один из поставщиков Монастыря нечист на руку. Известно, что при подсчете стоимости товара он использует Калькулятор. Этот Калькулятор умеет не так уж и много... Все что он умеет это:
1. ввести число 1
2. удвоить текущее число
3. поменять в текущем числе первую и последнюю цифры.
Калькулятор умеет работать лишь с целыми числами от 1 до 10000.
Обычно Торговец привозит в Монастырь товар, затем, пользуясь Калькулятором, подсчитывает стоимость товара, называет сумму Настоятелю, и Настоятель оплачивает товар. Настоятель хочет узнать, не обманывает ли его Торговец, называя сумму, которая не может быть получена с помощью Калькулятора. Помогите ему в этом.
Ввод. В файле находится единственное число k - сумма, названная Торговцем (1
Вывод. Выведите "YES", если сумма может быть получена с помощью Калькулятора, и "NO" в противном случае.
Пример input.txt #1
8042
Пример output.txt #1
YES
Пример input.txt #2
3
Пример output.txt #2
NO
Решение g6_1078:
На вход нам дается единственное число k, необходимо проверить, возможно ли получить его из числа 1 с помощью двух операций - умножения на 2 и обмена первой и последней цифр. Эта задача эквивалентна задаче о том, возможно ли из числа k получить число 1, с помощью операций - разделить на 2 и поменять местами первую и последнюю цифры числа.
Так мы и сделаем - напишем рекурсивную процедуру, которая состоит из трех условий:
Если текущее число 1, то выводим "YES" и прекращаем работу программы.
Если текущее число делится на 2, то запускаем рекурсивную процедуру, для числа, вдвое меньшего текущего.
Если после перестановки цифр число делится на 2, то запускаем рекурсивную процедуру для вдвое меньшего числа.
Здесь возникает вопрос: а не возникнет ли бесконечного цикла, т.е. мы переставляем цифры, получаем некоторое число, затем делим его на 2 и опять получаем первое число. Я не смог придумать, как проверить и отсечь это, кроме как создать массив от 1 до 10000 и проверять, не встречалось ли число ранее.
Для того чтобы переставить цифры, можно разбить число на части и собрать его заново, а можно перевести в строку и просто поменять местами первый и последний символы.
Задача g6_1079: Предсказание (Командное соревнование школьников Свердловской области 2003)
автор: Александр Сомов (подготовил Денис Расковалов)
Не секрет, что многие жители Лощины Янтарной Росы часто обращаются к монахам Монастыря с различными вопросами. Каждую весну жители окрестных деревень спрашивают Настоятеля, сколько мешков зерна они соберут осенью c одного посаженного весной мешка. Настоятелю надоело каждый раз изобретать ответ на этот вопрос, и он решил придумать алгоритм, который бы генерировал ответ (не подумайте, что он был просто шарлатаном, но нельзя же тревожить Будду по таким пустякам). Он решил, что будет отвечать по следующему правилу (такое уж хитрое правило никто не раскусит):
Факториалом числа n, n - натуральное, Настоятель называет число, определяемое по правилу: n! = 1, если n = 1
n! = n*(n - 1)!, еcли n > 1
Функция F(x), x >= 0 вычисляется по следующему правилу:
F(x) = x, если x
F(x) = F(S(x)), если x > 9
где S(x) - сумма цифр в десятичной записи числа x.
Правило это Настоятель применяет следующим образом: в год с номером n от рождения Будды мудрый Настоятель сообщает, что они соберут F(n!) мешков зерна с одного посаженного мешка весной. С каждым годом все трудней и трудней Настоятелю вычислять F(n!), ваша цель - помочь ему в этом.
Ввод. Единственное число n - номер года, 1
Вывод. F(n!) - ответ Наставника
Пример input.txt #1
3
Пример output.txt #1
6
Пример input.txt #2
4
Пример output.txt #2
6
Решение g6_1079:
Заметим, что любой факториал числа, большего 5 делится на 9. Это следует из того, что он состоит из множителей 3 и 6, которые при умножении на другие числа дают число, кратное 9. Воспользуемся свойством делимости на 9: если число делится на 9, то и сумма его цифр делится на 9. Мы знаем, что наш факториал кратен 9 (при n > 5), т.е. и сумма его цифр кратна 9. Если сумма цифр больше 9, то снова подсчитаем сумму цифр уже этого числа, она также будет кратна 9. Т.е. конечным результатом всегда будет 9.
А первые 5 значений несложно рассчитать вручную: 1, 2, 6, 6, 3.
Задача g6_1080: Чайнворд (15 Всероссийская олимпиада по информатике 2003)
Автор: Михаил Климов.
Журналисты газеты "The Run Times" к каждому номеру готовят чайнворд. Чайнворд - это последовательность клеток, в которые читатель вписывает угаданные слова. При этом каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова "set", "too" и "olymp" следующим образом: "setoolymp".
Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга "soly", который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.
Для экономии места в газете журналисты хотят составить чайнворд минимальной длины.
Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.
Входные данные
В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N - количество слов, которые можно использовать при составлении чайнворда (1
Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов.
Выходные данные
В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них.
Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ - знак вопроса.
Примеры
|