Главная страница
Навигация по странице:

  • Избранные задачи по программированию

  • 6. Избранные задачи по программированию

  • Избранные олимпиадные задачи по программированию 293

  • 6. Избранные олимпиадиые задачи по программированию 295

  • Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница21 из 26
    1   ...   18   19   20   21   22   23   24   25   26
    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 100% очков

    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• для объекта с номером i выполняется l• для энергии объекта Y выполняется 1 и все энергии различны;

    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
    1   ...   18   19   20   21   22   23   24   25   26


    написать администратору сайта