Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
2 3 другим. При печати буклета на одном лис- те печатаются четыре страницы: две — на л и ц е в о й стороне, и две — на обратной. Ког- да ВЫ СЛОЖИТе все ЛИСТЫ ПО ПОРЯДКУ И СО- гнете их пополам, страницы будут идти в правильном порядке, как у обычной кни- ги. Например, четырехстраничный буклет должен быть напеча- тан на одном листе бумаги: лицевая сторона должна содержать сначала страницу 4, потом — 1, обратная — 2 и 3. 6. Избранные задачи по программированию 269 Если в буклете число страниц не кратно четырем, то в конце можно добавить несколько пустых страниц, но так, чтобы ко- личество листов бумаги при этом было минимально возмож- ным. Ваша задача — написать программу, которая считывает из входного файла количество страниц в буклете и генерирует по- рядок его печати. Входные данные. Входной файл (a.in) содержит количество страниц в буклете — натуральное число, не превы- шающее 500. Выходные данные. В выходной файл (a.out) не- обходимо выдать порядок печати данного букле- та — последовательность команд, каждая из кото- рых располагается на отдельной строке и состоит из четырех чисел. Числа разделяются пробелом и обозначают следующее: • Номер листа, на котором происходит печать. • Сторону: 1 — если печать происходит на ли- цевой стороне, и 2 — если на обратной сторо- не. Два оставшихся числа — номера страниц букле- та, которые должны быть напечатаны. Пустая страница задается числом 0. Если целая сторона должна быть оставлена пустой, команду для ее пе- чати выводить не обязательно. Указание. Необходимо дополнить число стра- ниц до значения, кратного четырем, а затем акку- ратно выводить информацию по лицевым и обрат- ным сторонам листа буклета. На лицевых сторонах листов буклета правая страница должна быть нечет- ной, а на обратных — четной. Фрагмент решения. Var Function Out -.Integer ; Begin If q<=n Then Else End; Procedure Solve; Var Begin If n=l Then ('1 1 0 1 ') ; Else Begin nn:=nn+(4-nn mod 4) количество страниц до кратного 4. *} Пример. а 1 in a.out 1 1 a.in 4 а 1 1 а 0 1 1 2 in 14 а 1 1 2 2 3 3 4 4 4 1 2 3 1 2 1 2 1 2 1 2 0 1 2 0 14 3 4 13 12 5 6 11 10 7 8 9 270 Избранные задачи по программированию For i:=l Div 2 Do Begin If i Mod Then ( Div 2,' 1 ', Out ' ', Out (i)) лицевые стороны. *} Else WriteLn (i Div ' 2 (nn+l-i) ); обратные стороны. *} End; End; End; 5. В стране Гексландии каждое графство имеет форму пра- вильного шестиугольника, а сама страна имеет форму большого шестиугольника, каждая сторона которого состоит из N мале- ньких шестиугольников (на рисунке Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя — одного из 200 жрецов. Этот ритуал называется Великими перевы- борами жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет жрецов о том, кого они хотели бы видеть своим покровителем (если заяв- ление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). После этого все заявки удовлетворя- ются. Если несколько конфедераций выбирают одного и того же жреца, то они навсегда объединяются в одну. Таким обра- зом, каждый жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволя- ющую Совету жрецов выяснить состав каждой конфедерации после Великих перевыборов. В Совете все графства занумерова- ны (начиная с 1) с центрального графства по спирали (см. рису- нок). Все жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями). Входные данные. Во входном файле (b.in) записано число N — размер страны — и далее для каждого графства записан номер жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций в виде пар чисел: первое чис- ло — номер очередного жреца-покровителя, второе — номер желаемого жреца-покровите- ля. Все числа во входном файле разделяются 1 3 пробелами и (или) символами перевода стро- Пример. b.in 2 3 1 5 1 3 3 3 6. Избранные задачи по программированию 271 Выходные данные. В выходной файл (b.out) вывести для каждого графства одно число — номер его жреца-покровителя после Великих перевыборов. Сначала — для первого графства, затем — для второго и т. д. Указание. Задача на принцип косвенной адресации. Использо- вать два массива (начальный и конечный) для хранения номеров жрецов для графств нельзя — оперативной памяти явно не хва- тит. Обозначим через f(N) количество графств в стране со сторо- ной из N шестиугольников. Тогда Заметим, что при уве- личении размера страны добавляется «внешний пояс» графств, их количество — 6*(N-1). Итак, или При N, равном 128, получаем 48769 графств. Var .200] Of Word; b : Of Byte; i,n,k,t : Word; f : Text; Begin Assign ') ;Reset (f) ; Read(f,n) ;n:=l+3* *n; For i := 1 To 200 Do a[i]:=i; For i := 1 To n Do While Not SeekEof (f) Do Begin End; Close (f) ; Assign (f, '); For i := 1 To n Write(f,a[b[i]]) ;{*Косвенная *} End. А что, если N больше 128, например, равно 1000? Количест- во графств приближается к 3 миллионам. Есть ли решение? Оказывается, есть. Массив для хранения номеров жрецов для графств вообще не требуется. 6. «Игра в слова». Надеемся, что вам знакома следующая игра. Выбирается слово, и из его букв составляются другие ос- мысленные слова, при этом каждая из букв исходного слова может быть использована не более такого количества раз, кото- рое она встречается в исходном слове. Напишите программу, помогающую играть в эту игру. Входные данные. В первой строке входного файла (c.in) за- писано выбранное для игры слово. В последующих строках за- дан «словарь» — множество слов, которые мы считаем осмыс- 272 Избранные задачи по Пример. c.in soundblaster sound sound blaster soundblaster master last task sos test bonus done sound sound blaster soundblaster last bonus done ленными. Их количество не превышает Слово — это последовательность не более чем 255 маленьких латинских букв. Каждое слово записано в отдельной строке. Заканчивается словарь словом "ZZZZZZ" (состоящим из за- главных букв), которое мы не будем считать осмысленным. Слова в словаре, как это ни странно, не обязательно располагаются в алфа- витном порядке. Выходные данные. В выходной файл {c.out) необходимо выдать список слов, которые мож- но получить из исходного слова. Слова должны быть выданы в том же порядке, в котором они встречаются в словаре. Каждое слово должно быть записано в отдельной строке. Список слов должен заканчиваться все тем же неосмыслен- ным словом «ZZZZZZ». Указание. Требуется проверить: можно ли из букв одного слова получить другое слово. «Запутанные» решения основаны на анализе соответствия букв исходных слов. При простом решении следует сформировать маски — коли- чество букв (а, Ъ, с,.., z) в каждом из слов. Если такие маски есть, то задача сводится к проверке вхождения ма- ски слова из словаря в маску первого слова. 7. «Делители». Даны два положительных целых числа А и В. Определить возможность их разложения на N положитель- ных делителей таких, что произведения этих делителей совпадают. Т. е. требуется выполнение следую- щих условий: и где — делители a .... — делители числа Число 1 в этой задаче считается делителем. Входные данные. В единственной строке входного файла (d.in) через пробел записаны числа А, В N. Произведение чисел В не превышает значения 2147483647, а значение N — 31. Выходные данные. В первую строку выход- ного файла (d.out) через пробел записываются числа ..., а во вторую — ..., (достаточно вывести одно из решений). Если решение отсутствует, то в выходной файл запи- сывается сообщение Указание. Произведение делителей чисел А и В совпадает и равно, обозначим его как h. Нахождение h сводится к вычисле- Пример. d.in: 4 16 2 d.out: 2 2 4 4 6. Избранные задачи по программированию 273 нию )). Пусть мы нашли число j такое, что h и А делятся нацело на/, В нацело делится на h Div j. В этом случае А следует разделить на а В — на Div j. После этого процесс поиска делителей следует продолжить. Если мы найдем N таких чисел то задача решена. Пример. Если А равно 320, В — 2278125 и N — 6, то после вычислений получим h, равное 30, а в результирующих массивах будет за- писано соответственно (2, 2, 2, 2, 2, 10) и (15, 15, 15, 15, 15, 3). 8. «Мотоциклисты». Среди мотоциклистов г. Кирова попу- лярно следующее соревнование: на одной из улиц города выби- рается прямой участок, на котором установлено несколько светофоров, имеющих только красный и зеленый цвета. Мотоциклист проезжает выбранный участок на постоян- ной скорости, причем нарушать правила дорожного движения, т. е. проезжать перекресток на красный свет, категорически за- прещается, кроме случаев, когда мотоциклист пересекает пере- кресток в момент переключения светофоров. Мотоциклист, из- менивший скорость движения, либо проехавший на красный свет, либо выбравший скорость, меньшую 5 м/с, дисквалифи- цируется. Побеждает мотоциклист, проехавший трассу за ми- нимальное время. Требуется найти оптимальную скорость дви- жения по трассе. Входные данные. В первой строке входного файла (m.in) за- писано N — число светофоров. В следующей строке N+1 чисел: первое — расстояние от точки старта до первого светофора, вто- рое — расстояние между первым и вторым светофорами, ... последнее число — расстоя- ние от последнего светофора до точки фини- ша (расстояния — числа из интервала от 1 до 100000). В третьей строке записаны N чисел — времена работы в красном и зеле- ном режимах (оно одинаково) для каждого светофора (числа из интервала от 1 до 300). Выходные данные. В выходной файл (m.out) записывается одно число (с точностью до четырех знаков) — искомая ско- рость или сообщение «по», если решения нет. Указание. На рисунке по горизонтальной оси откладываем расстояния, а по вертикальной — время. Времена работы каждого светофора в крас- ном режиме выделены на соответствующих расстояниях «черным отрезком». Каждой скорости движения мотоциклиста соответ- ствует наклонная прямая. Для решения за- m.in 3 200 100 200 200 2 m.out 55.5556 274 Избранные задачи по программированию дачи необходимо провести прямую из начала координат с наи- меньшим угловым коэффициентом, проходящую через «свет- лые» участки рисунка. Обратим внимание на то, что «лучшая» прямая касается хотя бы одного отрезка в верхней точке. Дей- ствительно, если она не касается ни одного отрезка в верхней точке, то ее можно сдвинуть («повернуть») вниз, уменьшая при этом угол, т. е. увеличивая скорость, до соприкосновения с пер- вой возможной точкой. Из вышесказанного следует решение: необходимо проверить все возможные «верхние» точки «тем- ных отрезков» на предмет их принадлежности искомым пря- мым и выбрать наилучшую. 9. Троллейбусы одного маршрута проходят через остановку каждые k минут. Известны времена прихода N (l k — целые числа). Если человек приходит на остановку в мо- мент прихода троллейбуса, то он успевает войти в этот троллей- бус. Необходимо написать программу определения времени прибытия первого троллейбуса на остановку (это число от 0 до k-1), такого, чтобы: • суммарное время ожидания троллейбуса для всех граждан было минимально; • максимальное из времен ожидания троллейбуса было ми- нимально. Входные данные. В первой строке входного файла (t.in) за- писано число k, во второй — N, а затем N строк со временем прихода жителей на остановку (числа от 0 до 100000). Выходные данные. В выходном файле (t.out) записываются два числа, каждое в своей строке, являющиеся от- ветами на первый и второй вопросы задачи соот- ветственно. Если вариантов решения задачи не- сколько, то выдать один из них. При решении только одного пункта задачи строка, соответству- ющая другому пункту, остается пустой. Указание. Достаточно подсчитать время прихо- да жителей по модулю k. После этого в каждый момент времени от 0 до имеем количество пришедших жителей. Для решения задачи доста- точно проверить время прихода первого трол- лейбуса 0 k-1 и выбрать из них наилучшее для пер- вого и для второго пунктов. 0 3 .... k-1 Пример. t.in 100 5 0 210 99 551 99 10 51 6. Избранные задачи по программированию 275 Так, например, логика решения первого пункта задачи вы- глядит следующим образом. Procedure SolvePA; Var i , j : Min: Begin For i:-0 To k-1 Do прихода первого *} =0 ; { Находим сумму времени ожидания троллейбусов для всех *} For j:=0 k-1 Do + ((к - j + i) Mod к) * A[j] ; If sc *} End; End; 10. «Посылки». Весь воскресный день родители решили по- святить отправке посылок голодному в г. Москве сыну-студен- ту. Для этого родители привозят посылки на вокзал и отправ- ляют их на любом идущем в г. Москву поезде. А сын в г. Москве приезжает к приходу этого поезда на вокзал, получа- ет посылку и отвозит ее в общежитие. При этом родители не могут сразу принести на вокзал более одной посылки (так как очень тяжело!). Студент также не может носить по несколько посылок сразу (он голодный!). Время, необходимое родителям, чтобы добраться от дома до вокзала, равно Т (оно равно време- ни переезда от вокзала до дома). В г. Москве, как известно, по- езда приходят на разные вокзалы. Для каждого вокзала извест- но время, необходимое студенту на дорогу от общежития до этого вокзала (оно равно времени на дорогу от этого вокзала до общежития). Дано расписание движения поездов из г. Кирова в г. Москву. Договоримся, что поезда в пути не обгоняют друг друга (т. е. поезд, который раньше другого отправляется из г. Кирова, прибывает в г. Москву также раньше). Написать программу определения максимального количества посылок, которые родители смогут послать за воскресный день голодно- му студенту (он все их должен встретить и отвезти в общежи- тие). Входные данные. Во входном файле заданы в следую- щем порядке целые числа: • Т — время на дорогу родителей от дома до вокзала в г. Кирове; • М — количество вокзалов в г. Москве 276 Избранные задачи по программированию Пример. p.in 70 2 40 50 4 60 1200 2 200 1120 1 1200 1440 2 2 • М строк, в каждой из которых записано одно число — время переезда от соответствующего вокзала до общежи- тия; • N — количество поездов (0 • N строк, каждая из которых содержит 3 числа: время от- правления поезда из г. Кирова, время в пути, номер во- кзала в г. Москве, на который прибывает данный поезд. Примечание Список поездов дан в отсортированном по време- ни отправления порядке. Время в задаче — абст- рактное число из интервала от 0 до 5000. В одну единицу времени отправляется не более одного поезда. Все данные — целые числа. Выходные данные. В выходном файле (p.out) необходимо вывести одно число — максималь- ное количество посылок, которые родители смо- гут отправить за воскресенье. Указание. Предположим, что родители от- правили посылку с первым поездом. При- нимаем решение по второму поезду. Воз- можны два варианта. Если они успевают съездить за второй посылкой, то они ее от- правляют с поездом, и количество отправ- ленных посылок к этому моменту времени будет равно двум, а если нет, то первую посылку они могут от- править не с первым, а со вторым поездом. Продолжим после- довательно этот процесс. Пусть для всех поездов с номерами i от 1 до 1 найдено максимальное количество посылок, кото- рые успеют отправить родители к моменту отправления поезда i. Решаем задачу для поезда с номером к (рисунок), предпола- гая, что с ним также отправляется посылка. Для нахождения этого числа (посылок) достаточно рассмотреть все предыдущие поезда, с которыми можно было отправить предпоследнюю по- сылку и успеть отправить посылку на поезде с номером к. Есте- ственно, что из этих чисел выбирается максимальное. Схема динамического программирования в действии. Рассмотрим основную процедуру — она проста, если не вда- ваться в детали, что и не требуется делать на данном этапе ре- шения. Procedure Solve; Var i, j: Integer; Begin *} Избранные олимпиадные задачи по программированию 277 For i:=l N Do Begin задачу для поезда с номером i . *} всегда можем отправить первую посылку с этим поездом, "проспав" все *} For j:=l Do{ *Согласуем отправку посылки с поездом i с отправками посылок на предыдущих поездах. *} If Then {*Если между поездами с номерами i и j родители успевают съездить домой, студент - в общежитие, то сравниваем Res +1 и Res[i]. *} ResP);{*Может быть полученный для поезда с номером i, Res[i] являться ответом задачи, например, в том случае, когда все следующие поезда отправляются через каждую секунду. *} End End; Итак, все технические сложности задачи сконцентрированы в функции IfPossib проверки совместимости отправки посылок поездами с номерами i и у. 11. «Закраска прямой». Интервал прямой с целочисленны- ми координатами содержит левую границу — точку а, и не содержит правую границу — точку Ь. Итак, интервал от 0 до 1.000.000.000 выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой опе- рации цвета в интервале, границы которого задаются, меняют- ся на противоположный (белый на черный, черный на белый). Написать программу поиска самого длинного интервала белого цвета после заданной последовательности операций перекра- шивания. Входные данные. Входной файл (z.in) содержит в первой строке число и затем строк с границами интервалов (числа в диапазоне Выходные данные. В выходной файл выводится одно число — длина само- го большого белого интервала. Указание. Решение с отслеживанием всех перекрашиваний достаточно трудоем- ко. Порисуем чуть-чуть. На рисунке изобра- жен один интервал. Вверху указан номер границы, внизу — цвет интервала. Значе- Пример. z.in 4 |