chain.in
soly
4
set
olymp
lye
too
chain.out
set
too
olymp
chain.in
solve
4
set
owe
evil
too
chain.out
?
chain.in
solve
7
olymp
set
too
pink
knot
parliament
tvs
chain.out
set
too
olymp
pink
knot
tvs
set
Решение g6_1080:
Это была вторая или третья по сложности задача на олимпиаде (сложнее только "Поезд Россия" и, может быть, "Песочница"), но я решил ее на полный балл во время олимпиады - случай довольно примечательный.
Здесь я опишу один из способов правильного решения, который я и реализовал на олимпиаде.
Сначала считаем все слова в массив. Теперь нам необходимо создать массив расстояний от буквы до буквы (двумерный t['a'..'z', 'a'..'z'], где каждый элемент содержит длину пути от буквы до буквы, какое слово используется, если в пути одно слово, и через какую букву идет, если в пути более одного слова). Сначала заполним его минимальными длинами слов. То есть, если в списке есть слова too и to, то t['t', 'o'].num = 2
Теперь необходимо найти переходы, в которых участвует несколько слов, для этого удобно воспользоваться алгоритмом Флойда. Примерно так должен выглядеть этот кусок кода:
for c1 := 'a' to 'z' do
for c2 := 'a' to 'z' do
for c3 := 'a' to 'z' do
if (t[c2, c3].num > t[c2, c1].num + t[c1, c3].num - 1) then begin
t[c2, c3].num := t[c2, c1].num + t[c1, c3].num - 1;
t[c2, c3].aft := c1;
t[c2, c3].add := 0;
end;
Здесь t.num - количество букв на пути, t.aft - через какую букву идет, в случае если идет по цепочке слов и t.add - через какое слово идет (в случае если идет по одному слову). Важно то, что при суммировании длин двух переходов (от c2 до c1 и от c1 до c3) сумма уменьшается на 1 - буква c1 накладывается.
Теперь у нас имеется список кратчайших расстояний и по нему мы можем восстановить кратчайшую последовательность слов.
Кроме этого нам понадобятся две функции, каждая из которых создает массив, в котором для каждого слова хранится количество букв, которые встречаются в образце начиная с позиции k. Т.е. допустим, что мы уже составили последовательность в которой есть k первых букв образца и нам надо определить, сколько последующих букв образца содержит каждое слово. Например, для образца "soly", для которого уже составлена последовательность для 2-х первых букв (k = 2), для слова "olymp" функция должна вернуть значение 2 - в этом слове встречаются буквы "l" и "y". Различие функций состоит в том, что одна из них должна считать количество букв, начиная с первой буквы слова, а другая - со второй. Оба этих массива нам пригодяться впоследствии.
Теперь, собственно, подготовка окончена и начинается решение.
Для решения нам необходим двумерный массив (go[1..250, 'a'..'z'] - каждый элемент хранит: go[i, c].now - сколько букв в строке, содержащей i первых букв образца и заканчивающейся на c; go[k, c].prev - сколько букв образца было в строке до добавления текцщего слова; go[k, c].cpr - какой символ был последний, до добавления текущего слова; go[k, c].pw - номер слова, которое мы добавили; go[k, c].beetw - флаг, использовали ли мы в пути от предыдущего состояния до добавления слова, содержащего буквы образца, другие слова - вместо него можно ставить особую метку в go.cpr - символ не из множества 'a'..'z'). Начнем заполнение этого массива.
Прогоним процедуру генерации массива, в котором содержится количество букв образца в слове, включая первую букву слова, с аргументом 0 - в последовательности еще нет ни одной буквы образца (пусть этот массив называется inw[j], где j - номер слова). Теперь организуем цикл (j) по всем словам и, внутри него, цикл (k) от 1 до inw[j]. Пусть c - последняя буква текущего слова. Если длина слова меньше go[k, c].now (сначала заполним все go.now бесконечностью), то запишем в go[k, c]: now - длина слова, prev = 0 - нет предыдущего слова, beetw или cpr - установим флаг цепочки в false - нет предшествующей цепочки, pw = j - номер слова.
Теперь - основной этап решения.
Заведем цикл (i) от 1 до количества букв в образце - 1. На каждом шаге формируем функциями два массива вхождений букв образца для каждого слова, считая, что i букв образца уже совпали. Пробегаем циклом (c) по всем буквам, на которые оканчивается текущая строка.
Следующие действия выполняем только если существует строка, содержащая i символов образца и оканчивающаяся на c. Организовываем еще один внутренний цикл по словам. Если первая буква текущего слова равна c, т.е. слово начинается на ту букву, на которую кончается текущая последовательность, то организовываем цикл (k) от 1 до количества букв образца, встречающихся в слове j, начиная со второй буквы.
В этом цикле проверяем - если последовательность, содержащая i + k букв образца и оканчивающаяся на последнюю букву слова, не существует или длиннее, чем текущая последовательность go[i, c].num + длина текущего слова (j) - 1, то заменяем ее данные на следующие: now = go[i, c].now + length(w[j]) - 1, prev = i, beetw или cpr = false, pw = j.
Заканчиваем цикл по k и условие что первая буква слова совпадает с последней буквой текущей последовательности (c). Теперь напишем кусок кода для случая, если первая буква текущего слова и последняя буква последовательности не совпадают.
Организуем цикл (k) от 1 до количества букв образца, содержащихся в слове j начиная с первой буквы. Если последовательность, содержащая k + i первых букв образца и заканчивающаяся на последнюю букву слова не определена, или ее длина больше чем, go[i, c] + (длина текущего слова - 1) + (расстояние от последней буквы текущей последовательности (с) до первой буквы слова - 1), то ставим ей в соответствие новые параметры: num = go[i, c] + t[c, w[j, h]] - 1 + h - 1, где h - длина слова, w - массив слов; prev = i; pw = j; cpr = c и beetw = true - содержит перед собой цепочку, которая начинается с буквы c и оканчивается первой буквой слова.
После работы этих циклов проверяем наличие ответа. Организовываем цикл по c от 'a' до 'z' и находим минимальное значение go[q, c].now (сохраним c для минимального значения как cbest, где q - длина заданной последовательности. Если минимум равен бесконечности, то значит не существует ни одного чайнворда из заданных слов, содержащего необходимую последовательность. Выводим "?" и выходим из программы.
Если же ответ существует, то его вывод также требует от нас определенных усилий. Мы знаем cbest и с помощью него восстановим лучшую последовательность. Для этого организуем цикл repeat until (сначала j равно длине данной последовательности, pc = cbest) и будем записывать в массив (por) номера слов go[pj, pc].pw и, в случае наличия флага beetw, также устанавливать флаг. После этого pc1 := go[pj, pc].cpr, pj := go[pj, pc].prev, pc := pc1 - переходим к предыдущему слову, содержащему буквы из данной последовательности.
Массив por необходимо перевернуть - он содержит слова в обратном порядке. Затем начинаем выводить слова. В случае, если установлен флаг, непосредственно перед словом необходимо вывести цепочку, соединяющую предыдущее слово с текущим. Для этого воспользуемся обратным рекурсивным обходом дерева, который восстановит всю цепочку в правильном порядке. Текст этой процедуры будет выглядеть примерно так:
procedure addlist(a, b : char);
begin
if t[a, b].add = 0 then begin
addlist(a, t[a, b].aft);
addlist(t[a, b].aft, b);
end else writeln(w[t[a, b].add]);
end;
Сначала в процедуру addlist в качестве a и b передаются последняя буква предыдущего слова и первая буква текущего соответственно.
Общая максимальная сложность алгоритма получается O(K*H*N*L), где K - количество букв в образце (250), H - мощность алфавита (26), N - количество слов (1000) и L - максимальная длина слова (10). Для самого худшего (практически нереализуемо) получаем порядка 65 000 000 операций, что вполне приемлемо для современных компьютеров.
Задача g6_1081: Таймер (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
Формат входных данных
В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.
Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
Формат выходных данных
В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись + days. Например, если сигнал прозвучит на следующий день - то +1 days.
Примеры
a.in
01:01:01
48:0:0
a.out
01:01:01+2 days
a.in
01:01:01
58:119
a.out
02:01:00
a.in
23:59:59
1
a.out
00:00:00+1 days
Решение g6_1081:
Сначала вырежем текущее время. Для этого надо считать строку, затем скопировать первые два символа в другую строку и перевести их в число. Затем удалить три символа (включая двоеточие). Повторив эту операцию 3 раза получим три числа - текущее время.
Затем считаем вторую строку и будем вырезать время из нее. Здесь все будет несколько сложнее, т.к. не определено, сколько символов отводиться на каждое из чисел и некоторые числа могут быть опущены. Пойдем по строке с конца, записывая каждый символ в другую строку. Как только мы встретили двоеточие или строка закончилась - переворачиваем строку, в которую мы записывали текущее число, переводим ее в число, записываем в соответствующую переменную - с секунд на часы, с часов на минуты.
Теперь все числа вырезаны и представлены нормальном виде. Просуммируем соответствующие числа текущего времени и интервала и начнем разносить их с конца, т.е. количество секунд делим нацело на 60, прибавляем это число к минутам, в секундах оставляем остаток от деления. Затем то же самое с минутами, и, в конце, делим часы нацело на 24, результат - количество дней. В часах оставляем остаток от деления.
Осталось только вывести ответ, не забывая при этом подставлять "0", если количество меньше 10 - так требует формат вывода.
Следует заметить, что здесь подходят переменные типа longint ( > 2*109) и поэтому никакие извращения с длинной арифметикой или с числами с плавающей точкой здесь не понадобится.
Задача g6_1082: Домой на электричках (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
Формат входных данных
Во входном файле записаны сначала числа N (2 i (2 i i пар чисел, первое число каждой пары задает номер станции, второе - время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении - либо от города, либо к городу.
Формат выходных данных
В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1.
Пример
b.in
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
b.out
20
Решение g6_1082:
Эту задачу можно решать многими способами (как и любую другую), но я буду использовать далеко не самый эффективный, но укладывающийся в ограничения для этой задачи.
Заведем одномерный массив для станций - для каждой станции будем хранить текущее минимальное время, за которое на нее можно добраться. Сначала заполним все бесконечностью. Также заведем массив, в котором будем хранить информацию о поездах - во сколько на какую станцию прибывает, а также, в каком направлении идет.
Для определения направления достаточно сравнить две любые станции на пути электрички - если номера возрастают, то поезд идет от города, иначе - к городу.
Теперь начинается медленное и неэффективное решение:
Запустим цикл (i) от 1 до количества станций. Затем идем по всем станциям (j), начиная с первой. Затем идем по всем поездам и, если время отправления поезда с этой станции больше либо равно текущему времени, за которое можно добраться до этой станции, считаем что на этот поезд можно сесть - прогоняем цикл по всем станциям, на которых останавливается этот поезд, и, если текущее время на станции больше, чем время прибытия на эту станцию данного поезда, то заменяем его.
Если за весь шаг цикла по i не произошло ни одного обновления, то прерываем работу программы. Несмотря на крайнюю неэффективность алгоритма программа успевает пройти все тесты.
Задача g6_1083: Клад (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Найти закопанный пиратами клад просто: всё, что для этого нужно - это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: "Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, ..., наконец десять шагов в сторону большого булыжника. Клад находится под ним". Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 - север, 2 - северо-восток, 3 - восток, 4 - юго-восток, 5 - юг, 6 - юго-запад, 7 - запад, 8 - северо-запад) (см. рис). Длина шага в любом направлении равна 1.
Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).
Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
Формат входных данных
Первая строка входного файла содержит число N - число указаний (1
Формат выходных данных
В выходной файл выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy - на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10-3.
Примеры
c.in
6
1 3
3 1
1 1
3 3
5 2
7 1
c.out
3.000 2.000
c.in
1
8 10
c.out
-7.071 7.071
Решение g6_1083:
Один из способов решения этой задачи - через номер направления вычислять синусы, косинусы, высчитывать углы... Но можно поступить гораздо проще. Заметим, что для всех побочных направлений, длина шага по каждой из координат составляет по модулю 2-1. Нам достаточно просто создать массив, в котором для каждого направления написать насколько изменяется каждая из координат.
Затем, считывая новую строку, просто умножаем количество шагов на соответствующее направлению изменение координаты и прибавляем к текущим координатам. Вот и вся задача.
Задача g6_1084: Забавная игра (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1*24+0*23+0*22+1*21+1*20 в двоичной системе запишется как 100112.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик - он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011
...
и результатом игры, следовательно, окажется число 1*24+1*23+1*22+0*21+0*20 = 28.
Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.
Формат входных данных
Входной файл содержит одно целое число N (0
Формат выходных данных
Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.
Пример
d.in
19
d.out
28
Решение g6_1084:
В решении этой задачи нам пригодиться знание о представлении числа в памяти компьютера. Как известно, оно представлено в виде последовательности нулей и единиц и полностью соответствует тем правилам перевода и записи, какими пользуется Юрий Петрович.
В переменную best, которая будет хранить максимальную перестановку, изначально инициализируем данным числом. Сначала определим некоторое число, которое назовем max. Посчитаем его таким образом: сначала приравняем его 1, а затем будем сдвигать бит с единичкой на 1 позицию влево (то же самое, что операция умножения на 2), до тех пор, пока число max не станет больше данного числа. Никакая перестановка цифр данного числа не может быть больше, чем max, т.к. содержит на 1 быть меньше. Запомним, какое количество операций сдвига мы произвели.
Теперь запустим цикл до количества операций сдвига для получения max. Булем осуществлять сдвиг двоичных цифр данного числа по следующему правилу: сдвигаем число на 1 бит влево, если оно больше max, то отнимаем от него max и прибавляем 1 - циклический перенос единицы. Если это число больше, чем best - заменяем best на это число.
Осталось только вывести ответ - best.
Задача g6_1085: Целые точки (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).
Формат входных данных
В первой строке содержится N (3 i, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi - целые числа, по модулю не превосходящие 1000000.
Формат выходных данных
В выходной файл вывести одно число - искомое число точек.
Примеры
e.in
4
-1 -1
-1 1
1 1
1 -1
e.out
1
e.in
3
0 0
0 2
2 0
e.out
0
Решение g6_1085:
Для решения этой задачи надо использовать формулу Пика, которая записывается так: x = s - n div 2 + 1, где s - площадь многоугольника, n - количество целочисленных точек на его сторонах.
Т.е. нам необходимо знать площадь многоугольника. Нам известна формула S = 1/2 * |Σi=1n[OPi, OPi+1]|, или преобразовывая ее и считая координаты точки O за (0; 0), получаем S = 1/2 * |(x1y2 - x2y1) + (x2y3 - x3y2) + ... + (xny1 - x1yn)|. Подробнее о выводе этой формулы можно прочитать в 4-ой части статьи "Вычислительная геометрия на плоскости". Пользуясь этой формулой и последовательно считывая координаты (следует не забывать о последнем члене этой суммы - сохранить координаты первой точки), легко получить площадь - сначала сложить все члены, затем взять по модулю и разделить на 2.
На этом же этапе следует считать количество целочисленных точек на сторонах многоугольника. Для этого надо посчитать длину проекций каждой стороны на координатные оси. Количество точек на этой стороне - НОД длин этих проекций. НОД по алгоритму Евклида считается так: на каждом шаге заменяем большое из двух чисел на остаток деления этого числа на меньшее, до тех пор, пока одно из чисел не станет равным нулю. Оставшееся число и есть наибольший общий делитель этих чисел. При подсчете количества точек следует также не забыть посчитать отрезок, соединяющий последнюю и первую точки многоугольника.
Теперь мы вычислили все необходимое и осталось только воспользоваться формулой, которая приведена в начале разбора: x = s - n div 2 + 1
|