Разбор задач заочного тура Московской олимпиады по информатике 2002/03 учебного года



жүктеу 225.75 Kb.
Дата04.05.2019
өлшемі225.75 Kb.

Разбор задач заочного тура Московской олимпиады по информатике 2002/03 учебного года

Опубликовано в газете "Информатика" издательского дома "1 сентября"
От редакции. В этом учебном году московской олимпиаде школьников по информатике, которая имеет статус региональной (областной) олимпиады, впервые предшествовал заочный тур. Целями проведения такого тура были, как поиск талантливых в области информатики и программирования школьников, который не так просто осуществить в таком мегаполисе, как Москва, так и попытка помочь учащимся подготовиться к очному туру. А именно, работая с проверяющей системой в режиме on-line, научиться соблюдать все технические требования, предъявляемые к проверке олимпиадной задачи, в частности, корректно работать с файлами входных и выходных данных. Кроме того, набор задач был таким, что решая их в течение двух месяцев, можно было познакомиться с широким спектром олимпиадных задач по информатике и освоить ряд полезных алгоритмов. Опыт проведения подобного тура оказался удачным. Более того, практически все призеры уже очной олимпиады, получившие дипломы I и II степени (9 из 11 человек), успешно справились с заданиями заочного тура, в результате чего и попали на очный. Традиционный же отбор участников через окружные олимпиады (аналог районных олимпиад) результатов практически не дал.

Проверка заданий была организована на сервере www.olympiads.ru/moscow с помощью специального сервиса, предоставленного факультетом ВМиК МГУ им. М.В. Ломоносова. Заочный тур московской олимпиады (в отличие от очных) был открытым, то есть помимо московских школьников в нем могли участвовать все желающие, чем не преминули воспользоваться практически все кандидаты в сборную России по информатике из различных регионов России, а также школьники из стран бывшего зарубежья. С результатами олимпиады, системой начисления баллов и тестами ко всем задачам можно ознакомиться на упомянутом выше сайте.

Как уже было сказано, задачи олимпиады были достаточно разнообразны, в том числе и по сложности. Наиболее простыми являлись задачи A, C и D. Наиболее сложная — задача I.


  1. Таймер

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

8 мегабайт

Таймер — это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.

Формат входных данных

В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ — от 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

a.out

01:01:01

48:0:0


01:01:01+2 days

01:01:01

58:119


02:01:00

23:59:59

1


00:00:00+1 days


Решение

Задачу можно решать, например, таким образом. Переведем заданное во входном файле время в секунды, считая началом отсчета начало суток. Например, время 12:30:00 соответствует 123600 + 3060 = 45000 секундам. Аналогично переведем требуемый интервал в секунды и прибавим его к начальному моменту времени — получим требуемое время, только заданное в секундах. Затем переведем это время в требуемый формат и выведем в выходной файл. При таком решении единственная возникающая проблема заключается в том, что полученный ответ может превысить максимально допустимое значение типа данных LongInt. Для хранения числа секунд можно было использовать тип данных Int64 языка FreePascal или тип данных long long int языка GCC.

Другой подход к решению состоит в том, что к начальному числу секунд прибавляется число секунд временного интервала, полученное число секунд переводится в минуты и секунды, минуты “запоминаются”, а секунды записываются как секунды ответа. Далее прибавим число минут интервала и “запомненные” минуты к начальным минутам, опять “запомним” лишние часы и т.д. При таком решении типа данных LongInt достаточно.


  1. Домой на электричках

Максимальное время работы на одном тесте:

3 секунды

Максимальный объем используемой памяти:

8 мегабайт

Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.

Формат входных данных

Во входном файле записаны сначала числа N (2  N  100) и E (2  E N). Затем записано число M (0   100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2  KiN) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.



Формат выходных данных

В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.



Пример

b.in

b.out

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


20


Решение

Подсчитаем, когда мы можем попасть на каждую из станций. Для этого в начале запишем, что на станцию 1 мы можем попасть в начальный момент времени, а для остальных станций запишем значение “неизвестно” (например, выразив его числовой константой –1). Далее на очередном шаге найдем ту вершину A из “неизвестных”, до которой мы можем добраться из одной из “известных”, как можно раньше. Затем запишем в эту вершину то время, за которое до нее можно добраться вместо пометки “неизвестно”. Как только станция E перестанет быть помечена как “неизвестная”, мы и узнаем самый быстрый способ добраться до нее. Если же на очередном шаге мы не нашли ни одной “неизвестной” станции, до которой можно добраться из “известных”, то прекращаем работу алгоритма — до нужной станции добраться невозможно. Ясно, что таким образом мы можем найти минимальное время поездки до любой станции, до которой можно доехать на заданных электричках.




  1. Клад

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

Найти закопанный пиратами клад просто: все, что для этого нужно — это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: “Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним”. Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 — север, 2 — северо-восток, 3 — восток, 4 — юго-восток, 5 — юг, 6 — юго-запад, 7 — запад, 8 — северо-запад) (см. рис). Длина шага в любом направлении равна 1.

Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис. 1).





Рис. 1

Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.



Формат входных данных

Первая строка входного файла содержит число N — число указаний (1 ≤ N ≤ 40). Последующие N строк содержат сами указания — номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.



Формат выходных данных

В выходной файл выведите координаты X и Y точки (два вещественных числа, разделенные пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy — на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10–3.



Примеры

c.in

c.out

6

1 3


3 1

1 1


3 3

5 2


7 1

3.000 2.000

1

8 10


–7.071 7.071


Решение

Для решения этой задачи достаточно было завести две переменные для хранения текущих координат кладоискателя и изменять их в соответствии с входными данными. Например, можно было для каждого указания разбирать 8 случаев — в зависимости от направления — и в каждом из них соответствующим образом передвигать кладоискателя. Однако при таком решении довольно легко ошибиться. Более рациональным было бы использование того факта, что 8 направлений пронумерованы подряд по часовой стрелке. Это могло привести, например, вот к такому короткому решению:

Var I,N,Dir,Len:LongInt;

X,Y:Real;

Begin

Assign(Input,'c.in');



Reset(Input);

Read(N); X := 0; Y := 0;

For I := 1 To N Do Begin

Read(Dir,Len);

X := X + Sin(Pi/4*(Dir–1))*Len;

Y := Y + Cos(Pi/4*(Dir–1))*Len

End;

Assign(Output,'c.out');



Rewrite(Output);

WriteLn(X:0:3,' ',Y:0:3);

Close(Output)

End.



  1. Забавная игра

Максимальное время работы на одном тесте:

3 секунды

Максимальный объем используемой памяти:

8 мегабайт

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 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 N  32767).



Формат выходных данных

Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.



Пример

d.in

d.out

19

28


Решение

Задачу можно решать непосредственно путем перевода исходного числа в двоичную систему счисления, получения всех его циклических сдвигов, перевода их в десятичную систему и выбора максимального из них:

Var I,J,Max,Num,NumDigits,Digit: Integer;

Digits: Array[1..20] Of Integer;

Begin

<ввод исходного числа в переменную Num>

Max := Num;

NumDigits := 0;

{перевод в двоичную систему}

While Num > 0 Do Begin

Inc(NumDigits);

Digits[NumDigits] := Num Mod 2;

Num := Num Div 2

End;

For I:=1 To NumDigits – 1 Do Begin



{сдвиг}

Digit := Digits[1];

For J := 2 To NumDigits Do

Digits[J–1] := Digits[J];

Digits[NumDigits] := Digit;

{перевод в десятичную систему}

Num := 0;

For J := NumDigits DownTo 1 Do

Num := Num*2 + Digits[J];

If Num > Max Then

Max := Num

End;


<вывод значения переменной Max в качестве ответа>

End;


Естественно, можно было решать эту задачу с использованием операции побитового сдвига SHR, не переводя числа явно в двоичную систему.


  1. Целые точки

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).

Формат входных данных

В первой строке содержится N (3 ≤ N ≤ 1000) — число вершин многоугольника. В последующих N строках идут координаты (XiYi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi — целые числа, по модулю не превосходящие 1000000.



Формат выходных данных

В выходной файл вывести одно число — искомое число точек.



Примеры

e.in

e.out

4

–1 –1


–1 1

1 1


1 –1

1

3

0 0


0 2

2 0


0

Решение

Эта задача проще всего решалась с использованием так называемой “формулы Пика”: если вершины многоугольника расположены в точках с целочисленными координатами (в дальнейшем такие точки будут называться “целыми точками”), то выполнено следующее равенство: S = K + M/2 – 1, где S — площадь многоугольника, K — число целых точек, лежащих внутри многоугольника, M — число целых точек, лежащих на границе многоугольника. Зная координаты вершин многоугольника, мы можем подсчитать S и M, а значит можем найти K, то есть ответ к задаче, по формуле Пика. О том, как найти площадь S многоугольника, зная координаты его вершин, можно прочитать, например, в [1]. Что касается нахождения числа M, то эта задача сводится к такой: зная координаты концов отрезка (целые числа), найти, сколько на нем целых точек. Можно заметить, что ответом на последний вопрос будет НОД(Δx, Δy) + 1, где НОД(A,B) — наибольший общий делитель чисел A и B, а Δx и Δy — разности абсцисс и ординат концов отрезка соответственно. А тогда число M — просто сумма НОД(Δx, Δy) для всех сторон многоугольника.




  1. Степень

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.

Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.



Формат входных данных

Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).



Формат выходных данных

В выходной файл выведите единственное число N.



Примеры

f.in

f.out

8

4

13

13


Решение

Решение задачи основано в основном на математических рассуждениях. Несложно понять, что искомое число N должно было содержать в своем разложении на простые множители все простые множители заданного числа A. Более того, в большинстве случаев ответом является именно число M — произведение всех простых множителей числа A, взятых по одному разу. Такой ответ не является верным, если только полученное число M настолько мало, что меньше даже степени, с которой одно из простых чисел входит в разложение числа A. С другой стороны, как уже было сказано выше, правильный ответ всегда делится на M. Поэтому достаточно перебрать числа M, 2M, 3M, …, пока не найдем подходящее. Легко понять, что правильный ответ не превосходит 40M, поэтому мы найдем его менее чем за 40 шагов. Единственная сложность, возникающая при таком решении — возведение в большие степени и возникающие при этом большие числа. Для решения этой проблемы можно было в программе вместо чисел как таковых использовать их разложения на простые множители. А именно, завести специальный тип “разложение на простые множители” (назовем его, скажем, TDecomposition):

Type

Tdecomposition = Record

NumPrimes: LongInt; {Число различных простых множителей}

Prime: Array[1..50] Of LongInt; {Множители}

Degree: Array[1..50] Of LongInt;

{Степени, с которыми они входят в разложение}

End;


Остается реализовать операции “разложение числа на простые множители”, “умножение двух разложений”, “возведение разложения в степень”, “проверка делимости одного разложения на другое”.


  1. Игра с фишками

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).

Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:



  1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.

  2. Путь не должен пересекать других фишек.

При этом часть пути может оказаться вне доски. Например:

Фишки с координатами (1, 3) и (4, 4) могут быть соединены. Фишки с координатами (2, 3) и (5, 3) тоже могут быть соединены. А вот фишки с координатами (2, 3) и (3, 4) соединить нельзя — любой соединяющий их путь пересекает другие фишки.

Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или “мнимых клеток”, расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Формат входных данных

Первая строка входного файла содержит два натуральных числа: W — ширина доски, H — высота доски (1 ≤ W, H ≤ 75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ “X” (заглавная английская буква “экс”) обозначает фишку, символ “.” (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырех натуральных чисел, разделенных пробелами — X1, Y1, X2, Y2, причем 1 ≤ X1, X2W, 1 ≤ Y1, Y2H. Здесь (X1, Y1) и (X2, Y2) — координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1, 1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса). Последняя строка содержит запрос, состоящий из четырех чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.



Формат выходных данных

Для каждого запроса необходимо вывести одно целое число на отдельной строке — длину кратчайшего пути, или 0, если такого пути не существует.



Примеры

g.in

g.out

5 4

XXXXX


X...X

XXX.X


.XXX.

2 3 5 3


1 3 4 4

2 3 3 4


0 0 0 0

5

6

0



4 4

XXXX


.X..

..X.


X...

1 1 3 1


0 0 0 0

4

Решение

Задача решается стандартным волновым алгоритмом (его также называют “поиском в ширину”). А именно, в начале необходимо поставить в начальную клетку пометку “0”, а остальные клетки оставить без пометок. Затем на шаге номер n мы ищем все клетки с пометкой “n – 1”, и если рядом с ними есть непомеченные пустые клетки, то помечаем эти пустые клетки пометкой “n”. Как только окажется помеченной (скажем, меткой “m”) клетка, находящаяся рядом с конечной клеткой, мы нашли длину кратчайшего пути от начальной клетки до конечной — она равна m+1. Если же мы никогда не пометим клетки, находящейся рядом с конечной клеткой, то пути от начальной до конечной не существует (наш алгоритм заканчивает работу, как только на очередном шаге не будет помечено ни одной клетки). Единственная проблема, возникающая при таком решении, состоит в том, что по условию путь может проходить вне доски. Для того чтобы решить эту проблему, достаточно добавить к доске по одному ряду пустых клеток с каждой из четырех сторон.




  1. Раскопки

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований ученые пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать…

Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык — язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции — сложение, умножение и вычитание (марсиане никогда не использовали “унарный минус”: вместо “–5” они писали “0–5”). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3 + 3*5 у них равнялось 30, а не 18.

К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью “18=7 (5 3) 2”, то возможна такая расстановка знаков: “18=7+(5–3)*2” (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью “5=3 3”, то марсиане явно не имели в виду числового равенства, когда писали это…

Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.



Формат входных данных

Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 230, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 230. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).



Формат выходных данных

В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа “–1”. Выходная строка не должна содержать пробелов.



Примеры

h.in

h.out

18=7 (5 3) 2

18=7+(5–3)*2

5= 3 3

–1


Решение

Решение задачи состоит из нескольких этапов. В начале необходимо привести входные данные к удобному для работы виду. Например, можно удалить все лишние пробелы и поставить в те места, где необходимо вставить знак арифметического действия, какой нибудь специальный символ, например, “^”. Ниже приведен фрагмент программы, выполняющий такое преобразование:

While Pos(' ',Expr) > 0 Do Begin

A:=Pos(' ',Expr);

If (A = 1) Or (A = Length(Expr)) Then

Delete(Expr,A,1)

Else If (Expr[A–1] In ['0'..'9',')']) And

(Expr[A+1] In ['0'..'9','(']) Then

Expr[A] := '^'

Else Delete(Expr,A,1)

End;

A := 1;


While A < Length(Expr) Do Begin

If ((Expr[A] = ')') And (Expr[A+1] In ['0'..'9','('])) Or

((Expr[A] In ['0'..'9',')']) And (Expr[A+1] = '(')) Then

Insert('^',Expr,A+1)

Else Inc(A)

End;


(здесь переменная Expr типа String — это обрабатываемое выражение, а переменная A имеет тип Integer). В первой части этого фрагмента удаляются все пробелы и расставляются те знаки “^”, на месте которых стоят пробелы. Во второй части фрагмента вставляются знаки “^” между числом и скобкой даже в тех местах, где пробелов не было.

Затем необходимо написать функцию, вычисляющую значение выражения, в котором знаки арифметических действий уже расставлены. Эта задача называется “синтаксическим разбором”, ее решение описано, например, в [2].

И, наконец, надо объединить уже написанные части функцией, перебирающей все возможные расстановки знаков и вызывающую для каждой расстановки функцию подсчета значения. Если значение хотя бы один раз совпадет с тем, что написано в левой части, значит, мы нашли решение задачи. Если же такого совпадения не случится, то требуемой расстановки знаков не существует. Пример функции, перебирающей все расстановки знаков, приведен ниже:

Function Rec(Start:LongInt):Boolean;

Begin

Rec:=True;



Repeat

Inc(Start);

If Start>Length(Expr) Then Begin

If <значение выражения, полученного в переменной Expr, нужное> Then

Exit;

Rec:=False;



Exit

End


Until Expr[Start]='^';

Expr[Start]:='*';

If Rec(Start) Then Exit;

Expr[Start]:='+';

If Rec(Start) Then Exit;

Expr[Start]:='–';

If Rec(Start) Then Exit;

Expr[Start]:='^';

Rec:=False

End;


Вызывается эта функция как Rec(0), она возвращает значение True в том случае, если искомая расстановка знаков существует, и False — в противном случае. Если расстановка знаков существует, в переменной Expr оказывается одна из возможных расстановок.


  1. Деревни

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

32 мегабайта

В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.

Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).

Вы должны написать программу, помогающую ему в этом.

Формат входных данных

Первая строка входного файла содержит два числа: N и P (1 ≤ PN ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.



Формат выходных данных

В выходной файл выведите единственное число — искомое количество дорог.



Примеры

i.in

i.out

3 2

1 2


3 2

1

11 6

1 2


1 3

1 4


1 5

2 6


2 7

2 8


4 9

4 10


4 11

2

Комментарий. Во втором примере группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.
Решение

Эта задача была, наверное, самой сложной задачей олимпиады. Во-первых, необходимо было понять, что деревни образуют дерево (связанный граф без циклов). Затем нужно “подвесить” это дерево за какую-нибудь из вершин, и таким образом получить дерево с выделенным корнем, при этом у каждой вершины, кроме корня, будет известен ее родитель. Затем необходимо применить метод динамического программирования: для каждой вершины V и для каждого числа T от 1 до P подсчитаем, какое минимальное число дорог должно быть разрушено, чтобы в поддереве с корнем в V компонента связности (максимальная связная часть), содержащая вершину V, состояла из T вершин — назовем это число Best[V,T]. Будем подсчитывать значения Best, идя по вершинам от листьев к корню. Если для всех детей какой-то вершины V эти значения уже подсчитаны, мы можем подсчитать их и для этой вершины. Для этого рассмотрим, как устроена какая-нибудь компонента связности из T вершин, содержащая вершину V. Она состоит из вершины V, а также из компонент, начинающихся в детях этой вершины, и имеющих суммарный размер T – 1. Тогда перебрав все разбиения числа T–1 на неотрицательные целые слагаемые T – 1 = a1 + a2 + … + am (их число m должно быть равно числу детей вершины V), мы берем в качестве очередного кандидата сумму Best[V1,a1] + Best[V2,a2] + … + Best[Vm,am] (где V1, V2, …, Vm — дети вершины V), причем если какое-то ai равно 0, то мы считаем Best[Vi,ai] = 1. Далее из всех вышеупомянутых кандидатов мы выбираем наименьший и записываем в Best[V,T]. При таком решении довольно долгое время может занимать перебор всех разложений числа T – 1 на несколько слагаемых, однако этого частично можно избежать — оставим данный момент читателю для размышлений. После того, как значения Best подсчитаны, остается получить из них ответ к задаче. А именно, для того чтобы отрезать от остальных деревень группу из P вершин с корнем в вершине V требуется разрушить Best[V,P] дорог, плюс еще одну дорогу в случае, если вершина V не является корнем дерева (а именно, дорогу, соединяющую поддерево с корнем в V с остальным деревом). Естественно, теперь необходимо выбрать из всех таких способов тот, который требует разрушения минимального количества дорог.



Литература


1. Андреева Е.В., Егоров Ю.Е. Вычислительная геометрия на плоскости. Информатика №44/2002.

2. Андреева Е.В. Конечные автоматы. Разбор выражений. Информатика №12/2002.

Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет