© Данная статья была опубликована в № 16/2006 журнала "Информатика" издательского дома "Первое сентября". Все права принадлежат автору и издателю и охраняются.      Главная страница "Первого сентября"
     Главная страница журнала "Информатика"
     Содержание № 16/2006
 Московская личная олимпиада по программированию 2005,2006 уч. года для 7-9-х классов


ЖАРКОЕ ЛЕТО-2006
Олимпиады школьников по информатике

Московская личная олимпиада по программированию 2005,2006 уч. года для 7—9-х классов

Авторы задач — Е.В. Андреева, В.М. Гуровиц, В.А. Матюхин
Автор разбора — В.М. Гуровиц

От редакции. Мы уже рассказывали на страницах нашей газеты о формах проведения Московской городской олимпиады по информатике и способах отбора на эту олимпиаду. В этом учебном году количество различных соревнований было еще увеличено. В частности, была добавлена олимпиада для учащихся 7–9-х классов. Отбор участников этой олимпиады производился через тот же заочный отборочный интернет-тур, что и на основную олимпиаду. Только критерии отбора были существенно снижены. Несколько школьников приняли участие в олимпиаде по результатам окружных соревнований, которые также проводились в общем зачете, т.е. для школьников 7–11-х классов одновременно. Участие в отборочных соревнованиях было не напрасным: несмотря на свой юный возраст, все участники олимпиады уверенно работали с файлами, и только один ученик не смог набрать никаких баллов.

Правила олимпиады совпадали с правилами “настоящих” олимпиад по информатике, в частности, со Всероссийской олимпиадой. Однако задачи были существенно проще и на решение 5 задач отводилось 4 часа. Наверное, ученикам 10–11-х классов большинство задач показались бы не олимпиадными, а учебными. Кроме того, условия задач были сформулированы предельно кратко и понятно. Тем не менее никто из участников не решил полностью все 5 предложенных задач, хотя каждая задача была кем-то решена.
А первая — самая простая — задача была не полностью решена даже победителем олимпиады!

Подобные соревнования направлены на возрождение интереса к программированию, на стимулирование занятия программированием в основной школе. Организаторы считают первый опыт весьма успешным и стремятся его расширить: в июне 2006 г. была проведена и первая командная олимпиада для учеников 8-х и более младших классов, ведь именно им предстоит соревноваться в олимпиаде для 7–9-классников в следующем учебном году. Пожелаем им, а также их учителям и наставникам успехов!

Задача A. Строки в книге

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй — с (K + 1)-й по (2K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка и порядковый номер этой строки на странице.

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

Входной файл содержит число K — количество строк, которое печатается на странице, и число N — номер строки (1 K 200, 1 N 20000).

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

В выходной файл выведите два числа — номер страницы, на которой будет напечатана эта строка, и номер строки на странице.

Примеры

Решение

Подсчитаем сначала, сколько страниц будет заполнено целиком, если мы напечатаем только первые N строк. Для этого разделим N на K с остатком. Неполное частное как раз и будет равно искомому числу — количеству страниц, на которых напечатано по K строк. Если остаток от деления равен нулю, то строка с номером N окажется последней на странице с номером N div K. Если же остаток отличен от нуля, то эта строка окажется уже на следующей странице — на странице с номером (N div K) + 1 — и ее порядковый номер будет в точности равен этому остатку — N mod K. Осталось написать короткую программу:

read(K, N);

if N mod K = 0 then write(N div K, ' ', K)

else write (N div K + 1, ' ', N mod K);

Можно решить эту задачу и без использования условного оператора:

read(K, N);

write((n — 1) div k) + 1, ' ', (n — 1) mod k + 1);

Проверьте самостоятельно, что эти формулы дают верный результат.

Задача B. Палиндромная последовательность

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

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

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

Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. 1 LesQ.gif (292 bytes) N 100, элементы последовательности — натуральные числа от 1 до 9.

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

В выходной файл выведите сначала число M — минимальное количество элементов, которое надо добавить к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо добавить к последовательности.

Примеры

Решение

Заметим, что в худшем случае нам придется дописать N – 1 чисел. Например, если дана последовательность 1 2 3 … (N – 1) N, то кратчайшая симметричная последовательность будет выглядеть так: 1 2 3 … (N – 1) N (N – 1) … 3 2 1. В самом лучшем случае наша последовательность уже является симметричной, и дописывать ничего не нужно. Таким образом, ответом в задаче является число от 0 до N – 1.

Опишем один из алгоритмов, решающих нашу задачу. Для начала проверим, является ли данная нам последовательность симметричной, используя вызов функции, которая будет проверять, является ли симметричной последовательность a[1], a[2], …, a[k]. Для этого нужно сравнить числа a[1] и a[k], a[2] и a[k – 1], и т.д. до a[k div 2] и a[k div 2 + 1].

Если в какой-то из пар числа окажутся неравными, то последовательность симметричной не является. Напишем соответствующий код:

function palindrom(k: integer): boolean;

var i: integer;

begin

  palindrome := true;

  for i := 1 to k div 2 do

    if a[i] <> a[k + 1 — i] then begin

      palindrom := false;

      break

    end

end;

Теперь вернемся к исходной задаче. Если исходная последовательность не симметрична, то проверим, достаточно ли добавить к ней одно число. Ясно, что для того, чтобы получилась искомая последовательность, необходимо в конец дописать число a[1]:

a[N + 1] := a[1];

После этого опять проверим, получилась ли у нас симметричная последовательность, вызывая функцию palindrom(N + 1). Если нас вновь постигла неудача, допишем в конец исходной последовательности уже два числа:

a[N + 2] := a[1]; a[N + 1] := a[2];

И т.д. до тех пор, пока функция palindrom на очередном шаге не вернет результат true.

Покажем, как организовать этот процесс, используя цикл for:

[1] for i := 0 to N — 1 do begin

[2]   for j := 1 to i do

      {Добавляем в конец i чисел}

[3]   a[N + j] := a[i + 1 - j];

[4]   if palindrom(N + i) then begin

       {Печатаем количество добавленных чисел}

[5]       writeln(i);

[6]       for j := 1 to i do

              {Печатаем добавленные числа}

[7]         write(a[N + j], ' ');

[8]      halt

[9]    end

[10] end;

Обратите внимание, что мы принудительно завершаем работу программы оператором halt, если при очередной итерации цикла получается симметричная последовательность. Можно было обойтись без этого, используя цикл while.

Теперь попробуем несколько модифицировать приведенный алгоритм. Дело в том, что мы выполняем лишние операции, дописывая в конец те же числа, что стоят в начале последовательности, и затем сравнивая эти числа в функции palindrom. Ясно, что достаточно проверять лишь числа, которые не дописывались в конец.

Для этого в цикле внутри функции palindrom нужно начинать проверять числа не с a[1], а с числа, которое сравнивается с числом a[N], то есть с числа a[k + 1 - N]:

for i := k + 1 — N to k div 2 do ...

Тогда и в основной программе нет нужды дополнять массив новыми числами: строки [2] и [3] можно удалить, а строку [7] заменить такой:

write(a[i + 1 - j],' ');

Отметим, что максимальная возможная длина палиндрома — 199. Это нужно учитывать при объявлении массива a.

Задача С. Кинотеатр

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

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

Во входном файле записаны два числа — X и Y (оба числа натуральные, не превосходящие 100).

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

В выходной файл выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно.

Если рассадить мальчиков и девочек согласно условию задачи невозможно, в выходной файл должна быть записана строка NO SOLUTION.

Примеры

Решение

Заметим, что задача не всегда имеет решение: например, если мальчиков слишком много, а девочек мало (или, и того хуже, нет вовсе!), то посадить каждого мальчика рядом с девочкой не удастся. Поскольку рядом с каждой девочкой могут сидеть не более двух мальчиков, то количество мальчиков не может превосходить количества девочек более чем вдвое. То есть, если X > 2Y, то задача решения не имеет. Также задача не имеет решения и в случае Y > 2X.

Покажем, что в остальных случаях школьников можно рассадить требуемым образом. Если мальчиков и девочек поровну, то одна из искомых рассадок очевидна: BGBG…BG.

Пусть мальчиков больше, чем девочек, на k человек: X = Y + k. Тогда можно рассадить школьников так: .

В тройках 2k мальчиков и k девочек, в парах — (Y – k) мальчиков и (Y – k) девочек. Итого:
2 k + (Y – k) = Y + k = X мальчиков, k + (Y – k) = Y девочек. Поскольку X 2Y, то k Y, то есть Y – k 0. Таким образом, предложенная рассадка всегда возможна. Случай, когда девочек больше, чем мальчиков, разбирается аналогично.

Остается написать программу.

read(X, Y);

if (X > 2 * Y) or (Y > 2 * X) then

    write('NO SOLUTION')

else if X >= Y then begin

         k := X — Y;

         for i := 1 to k do

             write('BGB');

         for i := 1 to Y — k do

             write('BG')

        end

        else begin

             k := Y — X;

             for i := 1 to k do

             write('GBG');

             for i := 1 to X — k do

             write('GB')

  end;

Обратим внимание на некоторые особенности работы этой программы. Если Y = X, то k = 0 и первый цикл for не выполняется ни разу: все школьники рассаживаются парами “мальчик — девочка”. Если же X = 2Y (или Y = 2X), не выполняется второй цикл, поскольку Y – k (X – k, соответственно) равно нулю. В этом случае все школьники рассаживаются тройками.

Задача D. Количество слов

Во входном файле записана строка текста, в которой могут встречаться:

· прописные и строчные (т.е. большие и маленькие) латинские буквы,

· пробелы,

· знаки препинания: точка, запятая, восклицательный и вопросительный знаки,

· символ “–”, обозначающий в некоторых случаях тире, а в некоторых — дефис.

Слово — это последовательность подряд идущих латинских букв и знаков “дефис”, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака “дефис” пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.

Напишите программу, определяющую, сколько слов в данной строке текста.

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

Во входном файле записана строка длиной не более 200 символов.

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

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

Примеры

Решение

В каждом слове есть первая буква. Поэтому вместо того, чтобы считать слова, можно считать первые буквы слов. Какая буква является первой буквой слова? Любая, слева от которой стоит не буква. Исключение составляет буква, слева от которой стоит символ “–”, а перед ним — буква. Осталось написать программу, которая перебирает все символы строки и считает, сколько среди них первых букв.

read(s);

for i := 1 to length(s) do

{s[i] — буква}

    if (s[i] in ['a'..'z','A'..'Z'])

    {s[i - 1] — не буква}

    and not(s[i - 1] in ['a'..'z','A'..'Z'])

    {s[i - 1] — не дефис}

       and not ((s[i - 1] = '-') and

       (s[i - 2] in ['a'..'z','A'..'Z']))

     then n := n + 1;

write(n);

У этой программы есть небольшой дефект. Когда мы проверяем, например, символ s[1], нам приходится обращаться к несуществующим символам s[0] и s[–1]. Чтобы избежать этого, можно изначально добавить в начало строки два символа, которые не повлияют на количество слов в строке, например, s:='!!' + s, и начинать искать первые буквы слов, начиная с третьего символа строки:

for i := 3 to length(s) do ...

Задача E. Метро

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

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

Во входном файле записано сначала число N — количество станций метро в городе (2 N 100). Далее записано число M — количество линий метро (1 M 20). Далее идет описание M линий. Описание каждой линии состоит из числа Pi — количества станций на этой линии (2 Pi 50) и Pi чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

В конце файла записаны два различных числа: A — номер начальной станции и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

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

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

Примеры

Решение

Идею решения этой задачи можно кратко описать так. Рассмотрим все линии, на которых расположена станция A. До любой станции на любой из этих линий можно добраться со станции A без пересадок. Пометим все эти линии числом 0. Теперь рассмотрим все непомеченные линии, у которых есть общие станции с линиями, помеченными числом 0. До любой станции на любой из этих линий можно добраться со станции A, используя одну пересадку, но нельзя добраться без пересадок. Пометим эти линии числом 1. Далее аналогично рассмотрим все непомеченные линии, у которых есть общие станции с линиями, помеченными числом 1. На любую станцию этих линий можно попасть, используя две пересадки, поэтому пометим их числом 2, и т.д. до тех пор, пока мы впервые не пометим одну из линий, на которых есть станция B. Число, которым помечена эта линия, и будет являться ответом в нашей задаче. (Такой алгоритм называют волновым.)

Теперь займемся реализацией этого алгоритма. Проще всего написать программу, используя структуру данных множество (set). Пусть L[i] — множество станций метро, лежащих на i-й линии (то есть L — массив множеств), current — множество станций, на которых можно оказаться, используя не более step пересадок. Построим множество next станций, на которых можно оказаться, используя не более (step + 1) пересадок. Во-первых, все станции из множества current входят во множество next. Во-вторых, если на какую-то станцию можно попасть за не более чем step пересадок, и эта станция принадлежит в том числе и линии i, то тогда на любую станцию линии i можно попасть за не более чем (step + 1) пересадок. То есть, если множество current * L[i] не пусто (звездочкой обозначено пересечение множеств, то есть их общая часть), все элементы множества L[i] нужно включить во множество next:

next := next + L[i]; {объединение множеств}

Осталось заметить, что если метро состоит из M линий, то либо со станции A на станцию B можно попасть не более чем с (M – 1)-й пересадкой, либо нельзя попасть вовсе (A и B лежат в разных компонентах связности соответствующего графа).

Теперь напишем тело программы.

begin

{Чтение данных из входного файла}

  read(N, M);

  for i := 1 to M do begin

  read(k);

    for j := 1 to k do begin

    read(t);

  {Добавляем станцию t во множество L[i]}

    Include(L[i], t)

  end

end;

read(A, B);

{Инициализация}

emptyset := []; {Пустое множество}

step := 0;

current := [A];

{Основной цикл}

  for step := 0 to M — 1 do begin

    next := current;

    for i := 1 to M do

      if current * L[i] <> emptyset then

        next := next + L[i];

    if B in next then begin

      write(step); halt

    end;

    current := next

end;

{Пути от станции A до станции B нет}

write(-1);

end.