Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
6. Избранные олимпиадные задачи по программированию 287 строки до первого слова в и от последнего слова в строке до конца строки. Требуется преобразовать текст так, чтобы сумма кубов пус- тот по всем строкам была минимальна. Для достижения этой цели разрешается заменять произво- льную пробельную последовательность (непустую последовате- льность подряд идущих пробелов и/или символов перевода строки) любой другой последовательностью. Входные данные. Первая строка входного файла содержит целое число S В последующих строках записан текст, содержащий не более 500 слов. Длина каждого слова не превос- ходит S. Выходные данные. В первую строку выходного файла запи- сывается минимально возможная сумма кубов пустот по всем строкам. В последующих строках выводится преобразованный текст. 10 10 aa-bb---bb 10 13 ааааа-аааа-ааа-аа-а 13 аааааа-ааааа-аааа-ааа-аа-а 13 ааааааа-аааааа-ааааа-аааа-а аа-аа-а 15 -aaa--bbb-bbb с- 8 с-сс- 6 b-aaaa-cccc-cc 35 5 аааааа-ааааа- аааа-ааа-аа-а 59 ааа-ааа-аа-а- Для осознания сути задачи приведем примеры входных и со- ответствующих выходных файлов (в таблице символом обо- значен пробел — удобнее Указание. Решение основано на факте — сумма кубов мини- мальна в том случае, когда количество пробелов между слова- ми совпадает, и если этого достичь нельзя, эти значения (ко- личество пробелов) наиболее близки другу. Пусть мы 288 Избранные олимпиадные задачи по программированию размещаем в строке q слов, количество символов в словах равно w. Длина строки известна — позиций. Обязательное количе- ство пробелов на каждом месте (d), а их подсчитываем, находя целую часть частного от деления количества пробелов на количество мест q+1. Оставшееся число пробелов Mod (q+1)) необходимо распределить по одному к пробелам на т местах. 18. Парковка около Великой Стены состоит из длинного ряда парковочных мест, полностью заполненного ма- шинами. Один из краёв считается левым, а другой — правым. Каждая из машин имеет свой тип. Типы перенумерованы нату- ральными числами, и несколько машин могут иметь один и тот же тип. Рабочие решили упорядочить машины в парковочном ряду так, чтобы их типы возрастали слева направо. Упорядоче- ние состоит из нескольких этапов. В начале каждого этапа ра- бочие одновременно выводят машины с их мест и затем ставят машины на свободные места, образовавшиеся в результате вы- езда машин на данном этапе, т. е. меняют их местами. Каждый рабочий перемещает только одну машину за этап, и некоторые рабочие могут не участвовать в перемещении машин на этапе. Эффективность процесса упорядочивания машин определяется количеством этапов. Предположим, что на парковке находится N машин и W ра- бочих. Требуется написать программу, которая находит такое упорядочивание, при котором количество этапов не превосхо- дит значения N/(W-1), округлённого в большую сторону, т. е. Известно, что минимальное число этапов не пре- в о с х о д и т Рассмотрим следующий пример. На парковке находятся 10 машин типов 1, 2, 3, 4 и четверо рабочих. Начальное положение машин слева направо, заданное их типами — 2 3 3 4 4 2 1 1 3 1 . Минимальное количество этапов — 3, и они могут быть вы- полнены так, что расположение машин по типам после каждо- го из этапов следующее: • 2 1 1 4 4 2 3 3 3 1 — после первого этапа, • 2 1 1 2 4 3 3 3 4 1 — после второго этапа, • 1 1 1 2 2 3 3 3 4 4 — после третьего этапа. Входной файл имеет имя Первая строка входного файла состоит их трёх чисел. Первое — количество машин N, Второе — количество типов машин М, причём тип машины является натуральным числом от 1 до Задача с Международной олимпиады школьников 2000 года. Избранные задачи по программированию На парковке есть хотя бы одна машина каждого типа. Тре- тье — количество рабочих W, 2 N целых чисел, где i-e число является типом i-й машины в пар- ковочном ряду, считая слева направо. Выходной файл имеет имя car.out. Первая строка выходного файла содержит число R — количество этапов. Далее следует R строк, где строка выходного файла описывает i-й этап. Фор- мат строки, описывающей этап, следующий. Первое число — количество машин С, перемещаемых на данном этапе. Далее следует С пар чисел, определяющих перемещения машин на данном этапе. Первое число пары — позиция, с которой маши- на перемещается, второе число пары — позиция, на которую машина перемещается. Позиция машины является целым чис- лом от 1 до iV и отсчитывается с левого конца ряда. В случае, если существует несколько оп- тимальных решений, выдайте только одно Оценка решения. Предположим, что ко- личество этапов, выданных вашей програм- мой, — R, a = Если какой-то из R этапов выдан некорректно или после выполнения всех этапов типы машин не выстраиваются в возрастающем порядке, 3 1 5 5 10 10 1 Пример. car.in 10 4 4 2 3 3 4 4 2 1 1 3 1 car.out 3 4 2 7 3 8 7 2 8 3 3 4 9 9 6 6 4 вы набираете 0 очков за тест. В противном случае ваши очки будут начислены в соответствии со следую- щими правилами: • R • 50% очков • 20% очков 0% очков Указание. Прагматика и еще раз прагматика торжествует в решении данной задачи. Поиск минимального количества эта- пов в задаче не требуется. Необходимо осуществить перестанов- ку машин на стоянке за этапов — это дает 100%-ный балл. Если за один этап на свои места ставится W-1 машина, то этот результат достигается. Так как на стоянке работают W рабо- чих, W-1 машина всегда ставится на свои места на одном этапе, с помощью простого эвристического алгоритма. • Взять машину, стоящую не на своем месте, и переставить ее на место в том промежутке, где она должна стоять, за- нятое машиной, также стоящей не на своем месте; • продолжить этот процесс (с последней машиной) до тех пор, пока не окажутся задействованными в перестановке 290 6. Избранные олимпиадные задачи по программированию все рабочие или не получится цикл. При этом машина, вытесненная последней, ставится на первоначальное мес- то, с которого начинался процесс перестановки. Послед- няя машина не обязательно попадает в свой промежуток. В случае цикла и оставшегося количества рабочих более одного, алгоритм повторяет свою работу с этими рабочими над машинами, стоящими, естественно, не на своих мес- тах. Для примера из формулировки задачи этот алгоритм дает следующие этапы работы. № этапа 1 2 3 Место 1 2 2 1 1 2 3 3 3 1 3 3 3 3 1 4 4 2 2 2 5 4 4 2 2 6 2 3 3 3 7 1 1 1 3 8 1 1 1 3 9 3 4 4 4 10 1 1 4 4 Ответ (файл 4 4 1 4 4 9 9 6 6 1 4 1 5 5 10 10 1 2 2 4 2 7 7 2 3 8 8 3 Решение состоит не из минимального числа этапов, но оно отвечает требованию задачи. 19. «Медианная энергия»*. В новом космическом экспери- менте участвуют N объектов, пронумерованных от 1 до N. Из- вестно, что N — нечетно. Каждый объект имеет уникальную, но неизвестную энергию У, выражающуюся натуральным чис- лом, Назовем объектом с медианной энергией такой объект X, для которого количество объектов с энергией, мень- шей, чем у X, равно количеству объектов с энергией, большей, чем у X. Требуется написать программу, которая определяет объект с медианной энергией. К сожалению, сравнивать энер- гии можно только с помощью устройства, способного для трех различных заданных объектов определить, какой из них имеет медианную энергию. Библиотека. Вам предоставляется библиотека device с тремя операциями: • GetN, вызывается только один раз в начале программы; не имеет аргументов; возвращает значение Задача с Международной олимпиады школьников 2000 года. 6. Избранные задачи по программированию • Med3, вызывается с тремя различными номерами объек- тов в качестве аргументов; возвращает номер объекта, имеющего медианную (среднюю) энергию; • Answer, вызывается только один раз в конце программы; единственный аргумент — номер объекта X, имеющего медианную энергию. Эта функция корректно завершает выполнение вашей программы. Библиотека device генерирует два текстовых файла an.out и median.log. Первая строка файла median.out содержит одно целое число: номер объекта, переданного библиотеке при вызове Answer. Вторая строка содержит одно целое число: ко- личество вызовов Med3, которое было сделано вашей програм- мой. Диалог между вашей программой и библиотекой записы- вается в файл median.log. Инструкция для программирующих на языке Pascal: вклю- чите строку uses device; в текст вашей программы. Экспериментирование. Вы можете поэкспериментировать с библиотекой, создав текстовый файл device.in. Файл обязан со- держать две строки. Первая строка — одно целое число: коли- чество объектов N. Вторая строка — целые числа от 1 до N в некотором порядке: i-e число является энергией объекта с но- мером i. Пример device.in 5 2 5 4 3 1 Файл device.in, указанный выше, описывает 5 объектов с их энергиями: Номер объекта Энергия 1 2 2 5 3 4 4 3 5 1 Ниже приведена корректная последовательность с пятью об- ращениями к библиотеке: 1. GetN возвращает 5. 2. Med3(l,2,3) возвращает 3. 3. возвращает 4. 4. Med3(4,2,5) возвращает 4. 5. Answer(4) Ограничения: • количество объектов N нечетно, и 5 292 6. Избранные задачи по программированию • библиотека для Pascal содержится в файле: device.tpu • объявление функций и процедуры на Pascal: Function Function Med3(x,y,z:Integer):Integer; Procedure • в ходе исполнения программы разрешается использовать не более 7777 вызовов функции • ваша программа не должна читать или писать какие-либо файлы. Указание. Пусть есть следующий массив с энергиями объек- тов. Номер Энергия 1 8 2 1 3 3 4 7 5 5 6 4 7 13 8 10 9 2 10 11 11 12 12 9 13 6 Все, что мы можем сделать с помощью операции Med3, это разбить массив на три части, выбрав случайным образом два несовпадающих номера (а и Ъ) элементов. Не деление пополам, как в бинарном поиске, а деление на три части — «тринарный» поиск. Пусть и Просматриваем все номера объектов, помеченные признаком True. В начальный момент времени для всех объектов этот признак равен True. Если операция Med3(a,b,i) даёт в качестве результата: • значение а, то помечаем объект с номером i как элемент, принадлежащий левой части (признак • значение г, то помечаем объект с номером i как элемент, принадлежащий средней части (признак • значение Ъ, то помечаем объект с номером i как элемент, принадлежащий правой части (признак _Right). В таблице буквами L, M, R обозначены признаки _Left, _Midlle, _Right. Буквой N обозначен признак _None, элемент не рассматривается на данном шаге анализа. Номер Признак 1 М 2 L 3 L 4 М 5 N 6 L 7 R 8 R 9 L 10 Я 11 Я 12 N 13 М Итак, разбили, а что дальше? Напрашивается единственно разумный ход — выбрать одну из трех частей и продолжить по- иск (другого не дано). Вся сложность задачи — в выборе пара- метров поиска и в аккуратном переходе от одного этапа поиска к другому. Какую часть выбрать для следующего этапа поиска? Мы имеем в левой части результата поиска 4 элемента, в пра- вой — 4 и в средней (без учета а и Ъ) — 3. Первоначально осу- ществлялся поиск элемента с медианной энергией 7 в массиве Избранные олимпиадные задачи по программированию 293 из 13 элементов. После этого этапа необходимо искать элемент со вторым значением энергии среди элементов, помеченных признаком _Middle. Часть параметров поиска определена: ко- личество и признак элементов, среди которых ищется иско- мый; номер значения энергии объекта. Еще один параметр — одно из предыдущих значений а или Ъ — требует пояснений (это самый сложный момент). Поясним рисунком. Если Med3(an,bn,ac)obn Оказалось, что поиск следует продолжать в левой (по отно- шению к а) части. Генерируем новые значения а Ъ (обозначены как Ъп). Если после этого средний элемент находится не на месте Ъп, то структура последующего поиска нарушается. Необходимо поменять значения у Ъп. Так, если после первого этапа поиска мы выяснили, что его следует продолжать в левой части, то и следующее деление на три час- ти должно осуществляться с учетом этого результата. Примечания. 1. Прервите чтение и проделайте ручной просчет поиска по данным из условия задачи без смены значений. Результат уже на этом про- стом примере окажется отрицательным. 2. Сделайте еще два рисунка и выясните особенности использова- ния функции Med3 при продолжении поиска в средней и правой частях. Позволим себе привести полный текст решения этой краси- вой задачи*. Program Median; Uses device; Const MaxN = 1500; Type TDir = (_None, ; Var n: Integer; Mas : Array Of TDir; Это одна из версий программы решения задачи. Разработана Дмитрием Сер- геевичем 294 Избранные олимпиадные задачи по программированию Rt : Integer; (*Количество элементов в подмножествах *) Procedure элементы, среди которых осуществляется поиск. *} Var i: Integer; Begin For i := 1 To N Do If Mas[i] = Dir Then Mas : = _Middle Else Mas [i]:= End; Procedure Swap (Var a,b: Integer); Var c: Integer; Begin с := a; a := b; b := c: End; Procedure a,b: Integer; Integer); {*Генерируем номера а и b. *} Var Integer; Begin t := 0; ca := Random (len)+1; cb := While ca=cb Do cb ;= Random For i : = 1 To N Do в том, что номера оставшихся элементов для поиска идут не подряд. *} If Mas [i] = _Middle Then Begin inc(t) ; If ca = t Then a := i; If cb = t Then b i; End; End; Procedure TDir; res, len, 1b: Integer); {*Основная процедура, параметры поиска описаны ранее. *} Var a, b, i, t: Integer; Begin ; {*Выделяем элементы, среди которых осуществляется поиск. *} If len = 1 Then Begin a := 1; While [a] <> Do inc(a); End Else Begin 6. Избранные олимпиадиые задачи по программированию 295 If Then Begin If Med3 (lb,a,b) <> a Then Swap End Else If Med3 (a,b,lb) <> b Then ; значения а и b с учетом предыдущего поиска. Пояснение приведено на рисунке в тексте. *} If = 2 Then Begin If res = 1 Then Answer (a) Else Answer (b) End Else Begin 0; rt := 0; := _None; := For i := 1 To n Do If Mas [i] = Then Begin t := ; If t = b Then Begin inc(rt) ; Mas[i] : _Right End{*Пишем в правую часть. *} Else If t = a Then Begin inc(lt) ; Mas[i] := End; End; If Res = Then Answer (a) Else элемент попал на границу интервала, поиск *} If Res = Then Answer (b) Else If res < lt+1 Then Doit ,a) с новыми *} Else If res < len-rt Then Doit Else End; End; End; Procedure Begin n GetN; Randomize; SizeOf(Mas) , ; Doit shr n, n shr 1+1 - среднее значение энергии, 1- условно считаем, что ранее был первый номер (обеспечивает правильный поиск). *} Begin Solve End. 296 Избранные задачи по программированию 20. В компьютерной графике* для обработки черно-белых изображений используется их преобразование в строку из деся- тичных чисел. Изображение или его часть (квадрат меньшего размера) последовательно делится на 4 равных квадрата. Если все точки в квадрате одного цвета (черного или белого), то про- цесс деления этой части изображения заканчивается. Квадра- ты, содержащие как черные, так и белые точки, опять делятся на 4 равных квадрата. Процесс продолжается до тех пор, пока каждый из квадратов не будет содержать точки только одного цвета. Например, если использовать 0 для белого и 1 для черного, то изображение слева будет записано матрицей из нулей и еди- ниц. ' .'.J 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 |