Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3

Подождите немного. Документ загружается.

Выходной текстовый файл output.txt содержит порядковые

номера глав партий, вошедших в парламент.

Пример

Input.txt output.txt

N 4 2

1 2 3 4

2 3

3 1 4 2

4 2

Задачи по номинациям

Номинация «Физкультура и спорт»

В чемпионате региона по футболу участвует 10 команд. В

таблице чемпионата занесены результаты встреч команд друг с

другом . В случае выигрыша команда получает 2 очка, в случае

ничьей – 1 очко, в случае проигрыша – 0 очков. Требуется

разработать алгоритм (программу) для :

- построения таблицы чемпионата по данным, вводимым с

клавиатуры ;

- вывода этой таблицы (на экран или бумагу );

- определения названий команд, занявших последние три места

в чемпионате ;

- определения первой по списку из команд, не имевших ни

одной ничьей;

- определения команды-чемпиона.

Номинация «Искусство»

В конкурсе пианистов выступления участников оценивает

жюри , в состав которого входят шесть музыкантов.

Максимальная оценка, которую может выставить каждый член

жюри , 10 баллов, минимальная – ноль. Требуется разработать

алгоритм (программу) для

- построения линейной таблицы , содержащей фамилии и

инициалы участников, и прямоугольной таблицы , содержащей

оценки каждого члена жюри ;

- определения фамилии участника – победителя конкурса ;

- номер самого строгого члена жюри .

Номинация «Первокурсники»

На Компьютерной улице живут в собственных домах только

семьи Паскалёвых и Сиплюсплюсовых. Они решили

переселиться так , чтобы все Паскалёвы жили в начале улицы ,

а все Сиплюсплюсовы - в конце . Известно общее количество

домов на улице и кто живет в каждом доме.

Разработайте модель и составьте алгоритм (программу)

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

не более одного раза, а в каждом обмене должны участвовать

только две семьи .

Номинация «Информатика, как общеобразовательная

дисциплина»

На Южном полюсе расположены N пронумерованных

мете o рологических станций. Каждая станция соединена с

другими станциями линиями связи . В результате стихийного

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

Исправность линии связи между I-той и K-той станциями

определяется из целочисленной таблицы NET: элемент с

индексами (I,K) равен 1, если связь между I-той и K-той

станциями не нарушена, и 0 - в противном случае .

Требуется определить, между какими парами станций связь

невозможна даже через цепочки других станций. Создать

модель сети станций и разработать программу для определения

пар станций, между которым невозможно установить связь.

Технические требования

Входными данными являются число станций N и

целочисленная таблица NET размером NxN.

Входные данные берутся из текстового файла INPUT.TXT

(его предварительно нужно создать), в первой строке которого

указывается число станций, в каждой следующей строке -

очередная строка таблицы .

Результаты - пары номеров станций - выводятся построчно

на экран .

Номинация «Информатика как профилирующая

дисциплина»

Требуется смоделировать размещение Т файлов на дискетах

так , чтобы число дискет было минимальным, при условии, что

размер каждого файла не превышает емкости дискеты , и файлы

нельзя разбивать на части .

Технические требования.

Входными данными являются число файлов Т и

целочисленная таблица FILES, содержащая размеры файлов.

Емкость дискеты считается известной и равна 1,44 Мб.

Входные данные берутся из текстового файла INPUT.TXT

(его предварительно нужно создать), в первой строке которого

указывается число файлов, в следующей строке - строка

таблицы .

Результаты – число дискет и номера файлов на каждой из

дискет - выводятся построчно на экран .

Номинация «Студенты гуманитарных специальностей»

Требуется найти и вывести на экран все слова заданного

текста , корень которых вводится с клавиатуры . Текст

представляет собой последовательность слов, разделенных

любым числом пробелов. Требуется построить модель, алгоритм

и программу решения поставленной задачи .

З А Д А Н И Я 2 Т У Р А

Номинации:

- студенты, для которых информатика является

общеобразовательной дисциплиной;

- студенты гуманитарных специальностей;

- студенты, специализирующиеся в области искусства ,

культуры, спорта.

Задание 1. «Жюри»

Координатор Открытой региональной студенческой

олимпиады по программированию и компьютерному

моделированию О.Ф.Ускова поручила председателю жюри

олимпиады О.Д.Горбенко согласовать требования к

оформлению решений задач со всеми членами жюри , которые

живут в одном доме, но в разных подъездах. Накануне

олимпиады председатель жюри обошел всех членов жюри на их

квартирах и , выполнив поручение координатора, направился в

штаб-квартиру олимпиады.

Требуется определить количество ступенек, которые

прошел председатель жюри при обходе членов жюри , если

известны : количество членов жюри N, их номера квартир Y

, … , Y

, число этажей в доме К, количество подъездов в доме

М, количество квартир на каждом этаже Р и количество

ступенек между этажами R.

Технические требования

Входные данные берутся из текстового файла INP.TXT, в

первой строке которого содержатся целые числа N, K, M, P, R

через пробел. 0<=N<=100; 1<=K<=20; 1<=M<=20; 2<=P<=8;

1<=R<=20. Вторая строка содержит N целых чисел Y

, Y

, … ,

через пробел (1<=Y

<=K*M*P)

Выходное данное – целое число S – выводится на экран

Пример

Входные данные Выходные данные

2 5 4 4 6 6

2 25

Номинация "Первокурсники"

Задание 1. "Последовательность"

В текстовом файле хранится последовательность целых

чисел. Каждое число находится в диапазоне от -100000 до

100000. Необходимо найти длину наибольшей монотонно

убывающей или возрастающей подпоследовательности

чисел.

Формат входного файла :

В каждой строке входного файла хранится очередное число

последовательности . Всего в файле не может быть более 100000

чисел.

Формат выходного файла :

В первой строке выходного файла должна быть

записана длина наибольшей монотонной

подпоследовательности .

Технические требования:

Входной файл: INPUT.TXT

Выходной файл: OUTPUT.TXT

Время тестирования: 5 секунд

Пример N1

INPUT.TXT

OUTPUT.TXT

1 4

- 4

- 1

Задание 2. "Разложение "

Имеется некоторое натуральное число N из интервала от 1 до

100. Необходимо напечатать все способы его представления в

виде суммы произведений некоторых чисел. Перестановка

слагаемых или множителей, а также умножение на 1 нового

способа не даёт.

Формат входного файла :

В первой строке входного файла записано число N.

Формат выходного файла :

В каждой строке выходного файла должен быть написан

некоторый вариант разложения числа N. При этом , способы

разложения не должны повторяться .

Технические требования:

Входной файл: INPUT.TXT

Выходной файл: OUTPUT.TXT

Пример

INPUT.TXT OUTPUT.TXT

6 6

3*2

5+1

4+2

2*2+2

4+1+1

2*2+1+1

3+3

3+2+1

3+1+1+1

2+2+2

Номинация "Информатика - профилирующая дисциплина"

Задание 1. Символьный компьютер

Молодой хакер Extel приобрел новейший компьютер

для символьной обработки информации под кодовым

именем X9091. Основным применением этого компьютера

cтало использование для криптографии. Этот компьютер

принимал на вход строки текста и формировал выходные

строки , в зависимости от программы заложенной в него в

это время. Чип для этого компьютера создавался

исключительно по RISC технологии и поэтому набор

команд был представлен всего тремя инструкциями:

- Удалить символ в указанной позиции.

- Вставить символ в указанную позицию.

- Изменить символ в указанной позиции на другой.

Программа для этого компьютера должна была бытьь

написана в форме машинного кода, каждая инструкция которого

имеет формат «ZXdd», где Z представляет собой код

инструкции ( соответственно D, I, C ), X – это символ и dd

представляет собой двухзначное число - позицию. Программа

заканчивается специальной инструкцией для останова в виде

литеры ‘E’.

Для примера рассмотрим преобразование строки “abcde” в

строку “bcgfe”. Это может быть выполнено серией команд C(

change ), но программа будет не самая оптимальная. Следующая

программа будет лучше:

Abcde

Da01 Bcde

Cg03 Bcge

If04 bcgfe

E bcgfe

Напишите программу, которая будет читать две строки и

находить минимальную по количеству инструкций программу,

необходимую для преобразования первой строки во вторую. Так

как решение может быть неоднозначно, достаточно найти одно

решение.

Входные данные и результаты

Входной файл INPUT.TXT состоит из нескольких строк,

на каждой из них находятся 2 строки , разделенных точно одним

пробелом . Строки состоят не более чем из 20 символов

английского алфавита . На последней строке файла расположен

символ “#”.

Результат в виде нескольких строк с программами ( одна

программа для X9091 на каждую пару строк) должен быть

помещен в файл OUTPUT.TXT.

Пример входного файла

abcde bcgfe

Пример выходного файла

Da01Cg03If04E

Задачи, общие для всех номинаций

Задание 1. Спонсоры

Организаторы Первой региональной студенческой

школы - олимпиады пожелали первоначально воспользоваться

набором псевдографических символов для набора списка

спонсоров олимпиады в виде таблицы . Однако проблемы

возникли при редактировании: каждый раз приходилось

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

Вам предлагается реализовать функцию автоматического

выравнивания таблицы спонсоров.

Таблица представляет собой прямоугольник,

разделенный на ячейки горизонтальными и вертикальными

линиями.

Текст в ячейках таблицы может распологатьтся на

нескольких строчках. Текст не может содержать управляющие

символы и символы псевдографики .

Во время редактирования таблицы , текст в ячейках

может изменится и символы ‘| ’ (ASCII 179) могут сдвинуться

влево или вправо. Количество строк и столбцов в таблице ,

также как и количество строк в каждой ячейки , не меняется .

Текст в каждой строке каждой ячейки должен быть отделен

от вертикального символа - разделителя точно одним пробелом

слева и не меньше, чем одним пробелом справа в выравненной

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

могут. Разрешаются только:

- изменять количество ведущих или завершающих пробелов

в строках ячейки ;

- добавлять и удалять символы “ - ” (ASCII 196) в строчках с

горизонтальными символами-разделителями.

Таблица не может содержать пустые колонки , т.е . каждая

колонка имеет по крайней мере одну ячейку, заполненную

текстом .

Необходимо выровнять заданную таблицу , сделав ширину

таблицы минимальной.

Входные данные

Файл с входными данными INPUT.TXT содержит

редактируемую таблицу . Таблица состоит не более, чем из 100

строк и длина строки не превышает 255 символов. Строки файла

не содержат сами по себе ведущих или завершающих пробелов.

Результат

Таблицу , полученную после редактирования, необходимо

записать в файл OUTPUT.TXT. Строки файла не дожны содержать

ведущих и завершающих пробелов. Входные данные подобраны так ,

что ширина полученной таблицы не превышает 255 символов.

Олимпиадные задачи по программированию. Лучшие решения. В

трех частях. Часть 3.: Учебное издание/ О .Ф .Ускова, О .Д .Горбенко – Воронеж:

ООО ПФ «Джуди», 2002 – 80 с.

Редактор Андрейчикова Л .А.

Заказ . Отпечатано в ООО ПФ "Джуди". Тираж 200 экз.