Заочная студенческая олимпиада по программированию

К участию к заочной студенческой олимпиаде по программированию приглашаются студенты любых вузов. Олимпиада проводится в телекоммуникационном режиме. Задания олимпиады будут опубликованы на сайте ШГПИ shgpi.edu.ru 19.02.2010 года в 14 ч. (12.00 Москвы). Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 ч. 20.02.2010 г. Рекомендуемыми языками программирования являются pascal (компилятор freepascal), С и С++ (копиляторы gcc и g++), php 5, javascript 1.5 (ввод-вывод через элемент textarea). Исполняемый файл не требуется при использовании интерпретируемых языков (php, javascript, perl, python и т.п.).

Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию: номер решаемой задачи, фамилию, имя и отчество автора решения, курс, наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон, почтовый адрес). Дополнительно рекомендуется включать информацию об используемом языке программирования, его версии, опциях компилятора или интерпретатора, требования к операционной системе и программным библиотекам.

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

Итоги олимпиады будут подведены до 23 февраля 2010 г и опубликованы на сайте shgpi.edu.ru. Дополнительно, при участии в очной олимпиаде в рамках студенческого форума победители заочной олимпиады получают 10% бонус по очкам.

Обсуждение правил и процесса проведения олимпиады, условий и решений задач доступно на форуме ШГПИ

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

Получить доступ к задачам текущей олимпиады в рамках системы эталонных решений Solver можно по адресу: http://shgpi.edu.ru/solver/olimp2010_zao/

Задача 1. «Причесывание» текста.

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: от 1 до 2

Мы часто встречаемся с той ситуацией, что текст отформатирован не совсем так, как нам хотелось бы: лишние пробелы или их нехватка, пустые строки и т.д. Требуется написать простую программу преобразования текста, назовем это «причесыванием». Для простоты примем следующие положения:

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

2. Обычные символы образуют слова, которые отделяются друг от друга пробелами, знаками препинания и символами перевода строки.

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

Задание.

Во входном файле (input.txt) содержится некоторый текст. На выходе программы (файл output.txt) получается текст обработанный, согласно следующим требованиям:

1. Удалены лишние пробелы. Другими словами, если между словами имеется n пробелов, то должен остаться только один. В случае, если пробелы стоят в начале строки, то должен остаться один пробел.

2. Если после слова идут несколько пробелов, а потом знак препинания, то пробелы должны быть удалены.

3. Если после знака препинания сразу начинается слово, то между знаком препинанием и словам должен быть вставлен пробел.

Замечание

Пример:

Papa    kurit  ,     trubku   ,
      mama     mila ramu .  Pora moi         drug  ,
pora    .
  

Papa kurit, trubku, 
 mama mila ramu. Pora moi drug, 
pora.  

Задача 2. Justify.

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 5

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

Задача.

Файл input.txt содержит в первой строке следующий набор данных (через пробел): ширина текста W, ширина символа по умолчанию DL, ширина пробельного символа SL, первый символ C1, ширина первого символа CL1, второй символ C2, ширина второго символа CL2 и т.д. Обязательными являются только W и DL, параметры SL и пары Ci-CLi могут быть опущены. При отсутствии информации о ширине символа, его ширина считается равной DL. Таким образом, при наличии в первой строке только значений W и DL шрифт текста будет считаться моноширным. Со второй строки начинается произвольный текст, предназначенный для выравнивания по ширине.

Файл output.txt содержит выровненный по ширине текст.

Правила выравнивания текста:

1. Для простоты будем учитывать только слова текста, без последовательностей пробельных символов. Будем считать, что кодировка используемых в словах символов - latin1.
2. Выравнивание текста реализуется равномерным добавлением (справа налево) пробелов между словами, пока ширина WS очередной строки не станет максимально возможной, т.е. либо WS=W, либо WS+SL>W.
3. Если из двух слов первое слово умещается в строке, а второе - нет, то первое слово должно остаться в начале строки, а второе должно быть перенесено на следующую строку.
4. Если ширина слова больше ширины текста, то слово целиком должно остаться в начале строки.
5. Последняя строка в выровненом по ширине тексте должна быть выровнена по левому краю.

Примеры:

500 10
To be or not to be - that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles
 And, by opposing, end them. To die, to sleep
 No more - and by a sleep to say we end
 The heartache and the thousand natural shocks
That flesh is heir to - 'tis a consummation
Devoutly to be wished. To die, to sleep
To sleep, perchance to dream. Ay, there's the rub,
 For in that sleep of death what dreams may come,
When we have shuffled off this mortal coil,
 Must give us pause. There's the respect
That makes calamity of so long life.
  

To be or not to be - that is the question: Whether
'tis nobler in the mind to suffer The  slings  and
arrows of outrageous  fortune,  Or  to  take  arms
against a sea of troubles And,  by  opposing,  end
them. To die, to sleep No more - and by a sleep to
say we end The heartache and the thousand  natural
shocks That flesh is heir to - 'tis a consummation
Devoutly to be wished. To die, to sleep To  sleep,
perchance to dream. Ay, there's the  rub,  For  in
that sleep of death what dreams may come, When  we
have shuffled off this mortal coil, Must  give  us
pause. There's the respect That makes calamity  of
so long life.

50 10
To be or not to be - that is the question

To be
or
not
to be
-
that
is
the
question

50 5 2
To be or not to be - that is the question

To     be     or
not to  be  -
that is the
question

50 5 2 t 10 e 15
To be or not to be - that is the question

To  be   or
not       to
be            -
that     is
the
question

Задача 3. В поисках пиратского клада, пятый сезон.

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 8

Ты рылся в старых пыльных архивах, разгадывал головоломки, пробирался сквозь джунгли, искал путь в пещерном лабиринте, и все это оказалось не зря: вот оно, сокровище!!! Целый сундук со старинными золотыми монетами! Но не все так просто... С трех сторон приближаются три группы твоих конкурентов, ты один - их много... Что делать? Может сыграть на их алчности, заставить передраться за это золото? Итак, решено! Делим золото на три практически равные части и переносим каждую из них поближе к выходам, откуда должны появиться группы искателей сокровищ, пусть порадуются ... Недолго! В каждой части ровно столько золотых монет, что поделить их поровну между членами одной группы не удастся, как ни старайся. А пока они будут разбираться сначала друг с другом, а потом - с чужаками, ты постоишь в сторонке, вспоминая древнюю китайскую поговорку: "Когда дерутся тигры, добыча достается мудрой обезьяне, сидящей на дереве".

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

Задача

Дано: сундук с золотыми монетами в количестве N штук (100<=N<=10000000) и максимальное количество монет M (1<=M<=100), которое разрешается забрать себе с тем, чтобы оставшиеся монеты можно было разделить на три части с минимальной разностью монет между самой большой частью и самой маленькой, причем количество монет в каждой части должно выражаться простым числом, а количество взятых себе монет - быть минимально возможным и не уменьшающим количество монет в сундуке меньше 100 штук.

Входной файл input.txt содержит число N в первой строке и M во второй строке.

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

Время работы программы не должно превышать 1 секунду.

Примеры:

Задача 4. Теги.

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: от 5 до 10

Преамбула.

Документ на языке разметки HTML состоит из элементов, предназначенных для интерпретации и отображения их на экране. Каждый элемент выделяется открывающим и закрывающим тегом. Например, элемент <b>Статья</b> выделенный открывающим и закрывающим тегами <b> и </b>, будет отображаться на экране жирным текстом. В том случае, если тег не предназначен для выделения элемента текста (например, перевод строки <br>), закрывающий тег писать не нужно.

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

тег 1.

тег изменения порядка символов в тексте. Открывающий тег - <1>, закрывающий - </>. Таким образом, текст вида I <1>evol</> you – после обработки нашим интерпретатором будет выглядеть уже более осмысленно I love you. Другими словами, порядок символов в элементе, выделенном данным тегом, после обработки интерпретатором, будет изменен на противоположный.

Порядок записи открывающего и закрывающего тегов.

Правило записи открывающего тега. Между угловой скобкой < и символом 1 должны отсутствовать какие либо управляющие символы (код символа меньше 32) или пробелы (код пробела равен 32). Между символом 1 и угловой скобкой > может располагаться произвольное количество управляющих символов или пробелов.

Правило записи закрывающего тега. Между символами <, / должны отсутствовать какие либо управляющие символы (код символа меньше 32) или пробелы (код пробела равен 32). Между символом / и > может находиться произвольное количество управляющих символов и пробелов.

Таким образом, согласно этому правилу, текст

ababaababa diii<1

>dfdfdfdfdfdfdf</ >asdaq

Будет содержать правильные теги. Результатом выполнения обработки будет текст

ababaababa diiifdfdfdfdfdfdfdasdaq

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

Тег 2.

тег для поиска и замены подстроки в строке. Открывающий тег <2 пар1 пар2>, закрывающий тег - </>. Пар1, пар2 – строки (последовательности символов, заключенные в кавычки). Строки могут содержать пробелы и другие управляющие символы (например, символы перевода строки). Здесь пар1 – подстрока для замены, пар2 – строка для поиска. Длины строк пар1 и пар2 произвольным образом соотносятся друг с другом. Поиск осуществляется в элементе, который выделен данным тегом. Если пар1 пуст, то в результате обработки будут просто удалены элементы, соответствующие пар2.

Правило записи открывающего тега. Между угловой скобкой < и символом 2 должны отсутствовать какие либо управляющие символы (код символа меньше 32) или пробелы (код пробела равен 32). Между символом 2 и пар1 может находиться произвольное количество пробелов и управляющих символов. Между пар1 и пар2 может находиться произвольное количество пробелов и управляющих символов. Между пар2 и символом > может находиться произвольное количество пробелов и управляющих символов. Заметим, т.о. что параметры пар1 и пар2 могут идти друг за другом, например так "pop""push".

Правило записи закрывающего тега. Как вы заметили, закрывающие теги одинаковы для обоих открывающих тегов. Так что правило написания для закрывающих тегов одни и те же.

Пример записи тега.

I like to solve <2 "problems" "??">??!</>

В результате обработки интерпретатором получим строку

I like to solve problems!

Важно! Поиск подстроки осуществляется с первого символа элемента и продолжается с символа, который идет за найденным элементом. Замена осуществляется столько раз, сколько раз будет найдена подстрока пар2 в выделенном элементе.

Положения, общие для обоих тегов.

Элементы, выделенные тегами, могут находиться один внутри другого, т.е. быть вложенными. Количество вложений не ограничено. Например, выражение

aaa <1>012<1>3<2 "ab" "45">45</>6</>789</>

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

aaa 9873ab6210

Допускаются пустые элементы, когда открывающий и закрывающий теги идут друг за другом: <1></> или <2 "1""2"></>. В результате обработки теги, обрамляющие пустые элементы, будут просто удалены.

Сообщения об ошибках.

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

1. Порядок следования тегов: отсутствие закрывающего тега, отсутствие открывающего тега.

2. Ошибка в структуре тега: наличие пробелов между символами < и 1 и между символами < и 2, отсутствие хотя бы одного параметра для тега 2.

3. Ошибка в записи параметров. Отсутствие символов в пар2. Отсутствие символов в пар1 ошибкой не является.

О полноте языка

Описанный здесь язык, разумеется, не полон. Действительно, не ясно как в параметрах тега 2 описать символ '"'. Во-вторых, не прописан механизм описания тегов как обычной последовательности символов. Наконец, не совсем правильным было введение одного закрывающего тега для двух открывающих. Однако добавив такие механизмы, мы слишком усложнили бы задачу, а это в наши намерения не входило.

О переводах строк

В разных системах по-разному обозначается конец строк. В Windows это последовательность символов с кодами 13 и 10. В Linux это символ с кодом 10. Поскольку по условию эти символы также должны обрабатываться программой, то результаты в разных системах могут отличаться друг от друга. В нашем решателе предполагается, что конец строки обозначается двумя символами.

Задание

Написать программу—обработчик (интерпретатор) описанных выше тегов. В исходном файле (input.txt) находится текст, который может содержать произвольное количество тегов. Объем исходного текста ограничен 60 кб. Выходной файл (output.txt) должен содержать обработанный текст.

За полное решение задачи присуждается 10 баллов. Реализация программы-рбработчика только для тега 1 - 7 баллов. Реализация интерпретатора без обработки ошибочных тегов, некорректных символов и т.п. (или с ошибками в такой обработке) - минус 2 балла. Таким образом, за решенную задачу можно получить от 5 до 10 баллов