725 Задача 2

Имеется N групп учащихся и такое же количество учителей. Занятия

проводятся в следующие (условно) выбранные часы: 1,2,3,.. N. Как

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

одно занятие в каждой группе ровно один раз.

Пример.

При N=3 распределение может быть следующим:

В 1 час

1 учитель работает с 1 группой

2 учитель работает с 2 группой

3 учитель работает с 3 группой

Во 2 час

1 учитель работает с 2 группой

2 учитель работает с 3 группой

3 учитель работает с 1 группой

В 3 час

1 учитель работает с 3 группой

2 учитель работает с 1 группой

3 учитель работает с 2 группой

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

С клавиатуры вводится число, определяющее число групп учащихся и

учителей.

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

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

группам.

При N=3 таблица может иметь следующий вид:

1 учитель2 учитель3 учитель

1 час 1 23

2 час 2 31

3 час 3 12

726 Задача 1. "ПРОБИРКИ".

Имеются три пробирки. Вместимость каждой из них - 100 миллилитров.

На двух пробирках из трех нанесены одинаковые риски. Третья пробирка

- без рисок. Возле каждой риски надписано целое число миллилитров,

которое вмещается в пробирку от дна до этой риски.

Изначально одна из пробирок с рисками наполнена 100 миллилитрами

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

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

кваса, и если да, то находит минимально необходимое для этого число

переливаний. Квас можно переливать из одной пробирки в другую до тех

пор, пока либо первая из них не станет пустой, либо вторая из

пробирок (если она с рисками) не окажется заполненной до какой-либо

риски.

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

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

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

Ограничение времени: 20 секунд.

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

В первой строке входного файла содержится число рисок N (1<=N<=20)

на каждой из первых двух пробирок. Затем в порядке возрастания

следуют N целых чисел V1, ..., VN (1<=Vi<=100), приписанных рискам.

Последняя риска считается сделанной на верхнем крае пробирки

(VN=100). Все числа разделяются пробелами и/или символами перевода

строки.

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

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

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

"No" - в противном случае. В первом случае во вторую строку

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

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

INPUT.TXT OUTPUT.TXT

4

13 37 71 100 Yes

10

Максимальное количество баллов за задачу - 35.

727 Задача 2. "КУСКИ".

На плоскости задано N прямых. Напишите программу, которая

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

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

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

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

Ограничение времени: 20 секунд.

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

Исходные данные во входном файле записаны в следующем порядке: N,

a1, b1, c1, d1, ..., aN, bN, cN, dN, где 1<=N<=100, а пары чисел (ai,

bi) и (ci, di) - вещественные координаты двух различных точек, через

которые проходит прямая с номером i. Все данные разделяются пробелами

и/или символами перевода строки.

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

В выходной файл необходимо вывести одно целое число - искомое

количество кусков.

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

INPUT.TXT OUTPUT.TXT

3

0 0 0 2

0 2 2 0 2 0 0 0 7

728 Задача 1. Мешок фальшивых денег

Имеется N мешков монет, пронумерованных от 1 до N. На каждом мешке

написано число лежащих в нем монет. Один мешок наполнен только

фальшивыми монетами. В остальных мешках все монеты настоящие.

Настоящая монета весит 10 г., фальшивая 9 г.

Имеются весы с одной чашкой, которые показывают общий вес

положенных на них монет.

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

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

при абсолютном невезении.

Формат ввода:

Ввод производится из файла DENGI.DAT в следующем виде:

- первая строка - число N количество мешков;

- далее идут N строк, в каждой строке номер мешка и число монет в

мешке, разделенные пробелом:

1 m1

2 m2

...

N mN

Формат вывода:

Вывод необходимо производить в файл OUTPUT.DAT и дублировать на

экран. Должно выводиться одно число - число взвешиваний.

Ограничение на время тестирования 2 сек.

Максимальная оценка 30 баллов

729 Задача 2. Грамматическая

Дан словарь, в котором N<=100 различных слов, состоящих из

строчных букв русского алфавита. (кроме ё ). Буквы а, о, и, е, у, э,

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

более 20 букв.

Каждое слово, встречающееся в словаре, может состоять из корня или

из корня и приставки. Приставка всегда пишется перед корнем.

Используются строчные буквы русского алфавита. Корень слова всегда

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

Любой корень встречается в словаре хотя бы в двух словах. Любая

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

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

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

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

возможно определить по данному словарю. Заданное слово может

отсутствовать в словаре, но обязательно имеет либо корень, либо

приставку, встречающиеся в словах словаря.

Формат ввода:

Входные данные вводятся из файла SLOVAR.DAT в следующем виде:

- первая строка заданное слово для разбора

- вторая строка число N количество слов в словаре;

- далее N строк, в каждой строке записано одно слово

Например:

убор

4

светло

засветло

забор

бор

Формат вывода:

Вывод должен производится в файл GRAMM.DAT в следующем формате:

- первая строка:

приставка - <приставка>, корень - <корень>

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

заданного слова по одному в строке.

Например, для слова убор, содержимое файла GRAMM.DAT будет

следующим:

приставка у, корень - бор

забор

Ограничение на время тестирования 20 сек.

Максимальная оценка 30 баллов

730 Задача 3. Игра Цзяньшицзы

Играют двое. Есть две кучки камней. Игроки ходят по очереди. Ход

заключается в том, что игрок берёт камни из этих кучек, соблюдая

следующие правила.

Из одной кучки можно брать любое количество камней (даже всю

кучку) или можно брать камни одновременно из двух кучек, но

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

тот, кто своим ходом сможет забрать все лежащие на земле камни.

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

ведущий к проигрышу) ход.

Формат ввода:

Входной файл GAME.TXT состоит из двух строк. В первой строке

количество камней в первой кучке, во второй количество камней во

второй кучке.

Количество камней в каждой из кучек не превышает 1 000 000 000.

Формат вывода:

Вывод необходимо производить в файл MOVE.DAT и дублировать его на

экран.

В первой строке указывается количество оставшихся камней в первой

кучке, во второй количество оставшихся камней во второй кучке после

хода программы. Если выигрывающая стратегия у первого игрока

отсутствует, то ваша программа должна вывести на экран текст

"Выигрыша нет".

Пример ввода и вывода:

Ниже приведён пример входного файла данных и три возможных

варианта ответа.

Содержимое файла GAME.TXT:

5

7

Выходной файл MOVE.DAT может содержать ответы:

4 или 3 или 5

7 5 3

Примечание

Может существовать несколько выигрывающих ходов, но достаточно

вывести только один ход.

Ограничение времени тестирования: 20 сек.

Максимальная оценка: 40 баллов.

731 ЗАДАЧА 2. Сокровища царя Макара.

Все сокровища царя Макара описаны и хранятся в пронумерованных

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

ценные предметы, так и ларцы меньшего размера.

В составленной писарем Чумичкой описи содержатся сведения о

содержимом каждого ларца в следующем виде:

ларец 1: ларец 4 ларец 5 алмаз диадема

ларец 2: картина корзина картонка ларец 3 собачонка

ларец 3: банан диван

и т.п.

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

полный список сокровищ, которые в нем хранятся, в том числе и во

вложенных ларцах.

Например:

ларец 2: картина корзина картонка банан диван собачонка

Примечание:

1. Все входные данные корректны.

2. Опись сокровищ вводится из файла с именем KAZNA.DAT.

Допускается ввод с клавиатуры (оценка снижается на 20%)

3. Форма ввода.

В первой строке содержится количество ларцов (не более 10). Далее

следует описи содержимого каждого ларца. Каждая опись ларца является

строкой текста (длина строки не более 255 символов).

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

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

предметов, которые содержатся в описываемом ларце. Обозначение ларца

представляет собой слово "ларец", за которым через пробел следует

номер. Обозначение предмета - любое слово, кроме слова "ларец".

Далее идет строка с номером ларец, содержимое которого следует

определить.

Пример входных данных:

3

ларец 1: ларец 4 ларец 5 алмаз диадема

ларец 2: картина корзина картонка ларец 3 собачонка

ларец 3: банан диван

2

ТЕСТЫ К ЗАДАЧЕ N 2.

Если ваш компьютер не имеет русского шрифта, возможно набрать

тексты латинскими буквами.

ТЕСТ 1:ТЕСТ 2:

7

ларец 1: сухарь кубарь

ларец 2: палка

ларец 3: селедка

ларец 4: ларец 2 ларец 3 галка

ларец 5: ларец 6 дискета

ларец 6: ларец 7

ларец 7: котлета винчестер

17

ларец 1: сухарь кубарь

ларец 2: палка

ларец 3: селедка

ларец 4: ларец 2 ларец 3 галка

732 Задача 1. ГВОЗДИ . В длинную деревянную рейку вбили несколько

гвоздей. Некоторые пары гвоздей связываются веревочками так, чтобы

выполнялись следующие условия: 1). К каждому гвоздю была привязана

хотя бы одна веревочка; 2). Суммарная длина веревочек была бы

минимально возможной.

Задание: написать программу, которая связывает пары гвоздей

веревочками, как описано выше.

Технические требования: входными данными являются число гвоздей и

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

соединяемых гвоздей. Максимальное число гвоздей - 20. Максимальная

координата гвоздя - 200.

Пример входных данных:

5

11 12 13 16 16

Пример выходных данных:

3

1 2 2 3 4 5

Максимальная оценка за задачу 20 баллов

Ориентировочное время решения 45 минут

733 Задача 2. ГОЛОВОЛОМКА . Квадрат размером 5? 5 вдоль линий сетки

разбили на несколько фигурок. Написать программу, которая определяет,

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

квадрат размером 5? 5. При перекладывании не разрешается поворачивать

и переворачивать фигурки.

Технические требования: входные данные - символьная матрица

размером 5? 5. Каждая буква в матрице означает идентификатор фигурки,

содержащей соответствующую клетку. Идентификаторами являются большие

буквы латинского алфавита. Программа должна выдать один или несколько

других способов составления квадрата размером 5? 5 (каждый из

способов отделяется одной пустой строкой) либо сообщение, что это

невозможно.

Пример входных данных:

ЕЕЕЕЕ

ЕВЕЕЕ

АВССЕ

АААDЕ

АААЕЕ

Пример выходных данных:

ЕЕЕЕЕ

ЕАЕЕЕ

ВАААЕ

ВАААЕ

DССЕЕ

Максимальная оценка за задачу 30 баллов

Ориентировочное время решения 1ч .45 минут

734 Задача 3 Острова . В океане расположен архипелаг из N островов,

каждый из которых имеет форму многоугольника. Острова не

соприкасаются и не пересекаются. Эти острова необходимо соединить

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

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

островов, при этом суммарная длина мостов должна быть минимальна.

Задание: написать программу, находящую описанное соединение.

Технические требования: входными данными задачи являются число

островов в архипелаге (N) и описаний островов. Каждый остров задается

числом вершин и их координатами в порядке обхода по часовой стрелке.

Программа должна вывести два числа - количество мостов и их суммарную

длину. Число островов в архипелаге 1< N ? 10. Максимальное число

вершин для каждого острова - 10.

Пример входных данных:

3

4 00 01 11 10

4 20 21 31 30

3 40 51 50

Пример выходных данных:

2

2.000

Максимальная оценка за задачу 40 баллов

Ориентировочное время решения 2 часа

735 Задача 4. СТРОЧКИ . Заданы две символьные строки А и В. Требуется

вычислить, сколькими способами можно получить строку В из строки А,

вычеркивая некоторые символы. Например, если строки А и В имеют

соответственно вид Самарина Ира и Сара, то искомое число равно 7, для

строк aaabbbccc и abc это число равно 36.

Задание: напишите программу, находящую требуемое число способов.

Технические требования: входные данные - строки А и В. Длина

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

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

латинского алфавитов. Строчные и прописные буквы различаются.

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

А в соответствии с заданием.

Пример входных данных:

aaabbbccc

abc

Пример выходных данных:

36

Максимальная оценка за задачу 40 баллов

Ориентировочное время решения 1ч.30 минут

736 Задача 5. МНОГОУГОЛЬНИК . Многоугольник на плоскости задан

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

количество точек с целостными координатами, лежащих: 1) на границе

многоугольника; 2) строго внутри него. Задание: напишите программу,

вычисляющую требуемое количество точек для двух заданных случаев.

Технические требования: входными данными являются число вершин

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

Координаты вершин - целые числа и по модулю не превосходят 1000000.

Пример входных данных:

4

-10 -10 -10 10 10 10 10 -10

Пример выходных данных:

80

361

Максимальная оценка за задачу 40 баллов

Ориентировочное время решения 2 часа

737 Задача 6. РАСПИСАНИЕ СУДОВ . Расписание судоходной компании

включает в себя набор данных следующей структуры:

Пункт отправления

Пункт назначения

Дата и время отправления

Дата и время прибытия в пункт назначения

Название судна

Требуется организовать: 1) заполнение расписания; 2) нахождение по

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

минимальной длительностью путешествия (длительностью путешествия

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

временем прибытия в конечный).

Задание: напишите программу, реализующую указанные функции.

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

наименование пункта отправления (строка длиной не более 20

символов); наименование пункта назначения (строка длиной не более 20

символов); дата и время отправления (дата представляется в формате

дд/мм/гг, время - в 24-часовом формате); дата и время прибытия в

пункт назначения (дата представляется в формате дд/мм/гг, время - в

24-часовом формате);

ПРИЛОЖЕНИЕ К ЗАДАЧЕ 6

Пример входных данных для пункта 1:

Введите пункт отправления:

Архангельск

Введите пункт назначения:

Мурманск

Введите дату и время отправления:

30/03/97 14:15

Введите дату и время прибытия:

31/03/97 16:00

Введите название судна:

Максим Горький

Продолжать? (Д/Н) Д

Введите пункт отправления:

Мурманск

Введите пункт назначения:

Петербург

Введите дату и время отправления:

01/04/97 11:00

Введите дату и время прибытия:

04/04/97 18:00

Введите название судна:

Анна Ахматова

Продолжать? (Д/Н) Н

Пример входных данных для пункта 2:

Введите пункт отправления для маршрута:

Архангельск

Введите пункт прибытия для маршрута:

Петербург

Пример выходных данных:

30/03/97 14:15

04/04/97 18:00

Максим Горький

Анна Ахматова

Примечание:

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

клавиатуры.

738 Задача 7 (вне конкурса). ПОЛИМИНО . Полимино - это связная фигура

из N клеток. Под связной здесь понимается фигура, все клетки которой

можно обойти ходом шахматной ладьи. Для заданного N в общем случае

можно составить несколько различных полимино. Фигуры, совпадающие при

переносах и (или) поворотах, различными не считаются.

Задание: напишите программу, которая находит все различные

полимино из N клеток для двух случаев: а) 1? N? 5; б) 6? N? 11.

Технические требования: число N вводится с клавиатуры. Программа

должна вывести в первом случае список всех найденных полимино и общее

их количество (соседние фигуры должны быть разделены ровно одной

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

количество различных полимино, содержащих N клеток.

Пример входных данных 1:

3

Пример выходных данных 1:

* * *

* *

*

2

Пример входных данных 2:

10

Пример выходных данных 2:

4466

Основная идея решения задачи: Основная проблема в этой задаче -

правильно организовать перебор. Можно хранить все полученные варианты

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

ранее найденными, но это требует слишком много ресурсов. Существует

более эффективное решение, не требующее запоминания всех вариантов.

739 Задача 1. Новые гвозди (30 баллов)

На прямоугольный стол разложили N одинаковых листков бумаги со

сторонами, параллельными краям стола. Необходимо прибить листки к

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

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

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

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

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

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

Ограничение времени: 20 секунд

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

В файле исходных данных записано количество листков N (1? N? 100),

длина листка L и его ширина W (1? L, W? 1000). Далее следуют описания

N листков, заданных координатами левого нижнего угла. Оси координат

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

углу стола. координаты точек - пары неотрицательных чисел, не

превосходящих 1000. Все числа разделяются пробелами и/или символами

перевода строки.

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

Если вбить гвозди требуемым в условии способом невозможно, то

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

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

выходной файл координаты гвоздей в произвольном порядке. Координаты

гвоздей - вещественные числа. Числа в выходном файле должны

разделяться пробелами и/или символами перевода строки. Пример файлов

входных и выходных данных:

INPUT.TXT

3

10 10

0 0 5 5 12 3OUTPUT.TXT

6 6

13 7.5

740 Задача 5. АБРАКАДАБРА (40 баллов)

Последовательность из латинских букв строится следующим образом.

На первом шаге она пуста. На каждом последующем шаге

последовательность удваивается, после чего к ней дописывается

очередная буква латинского алфавита (а, b, c, ...). Ниже приведены

первые шаги построения последовательности:

Шаг 1. пустая последовательность

Шаг 2. а

Шаг 3. baa

Шаг 4. cbaabaa

Шаг 5. dcbaabaacbaabaa

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

символ, который стоит на N-ом месте в последовательности,

получившейся после 24-го шага.

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

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

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

Ограничение времени: 20 секунд

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

Во входном файле записано одно натуральное число N (1? N< 226).

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

Запишите в выходной файл символ, стоящий в позиции N получившейся

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

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

INPUT.TXT

4OUTPUT.TXT

T

741 Задача 6. ДВА КОНВЕЙЕРА (35 баллов)

В цехе по производству напитков работают два конвейера. На первом

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

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

бутылки она сразу же поступает на второй. Поскольку тара используется

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

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

последовательности бутылок:

А) Определяет время, через которое последняя бутылка в этой

последовательности будет закупорена (закупоривать можно лишь

наполненые бутылки).

Б) Находит такую перестановку заданных бутылок, при которой

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

определяет это время.

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

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

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

Ограничение времени: 20 секунд

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

В первой строке входного файла содержится целое число N (1? N?

1000) - количество бутылок. Далее идут N пар чисел X1 Y1 X2 Y2...Xn

Yn. Здесь Xi означает время разлива, а Yi - время закупорки бутылки с

номером i. Xi и Yiнеотрицательные целые числа, не превосходящие

1000000. Все числа разделяются пробелами и/или символами перевода

строки.

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

Первая строка выходного файла должна содержать время, требуемое

для исходной последовательности бутылок, вторая - минимально

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

перестановку номеров бутылок от 1 до N, для которой достигается

минимальное время.

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

INPUT.TXT

3

200 40

100 100

30 90OUTPUT.TXT

490

370

3 2 1

742 Задача 7 (40 баллов)

Даны координаты вершин невыпуклого самонепересекающегося

многоугольника и координаты некоторой точки. Определить принадлежит

ли данная точка заданному многоугольнику.

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

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

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

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

В файле исходных данных записывается количество вершин

многоугольника N, далее записываются координаты вершин X1, Y1, X2,

Y2,...Xn, Yn, а затем координаты точки X,Y.

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

INPUT.TXT

4

1 1 3 3 2 1 3 0

4 2OUTPUT.TXT

не принадлежит

743 Задача 1. Стопами Дирихле .

У главного животновода кроликоведческого хозяйства Стопами Дирихле

неожиданно возникла проблема. После долгих переговоров с западными

партнерами наконец-то поступила партия из 2n кроликов k пород.

Кроликов нужно рассадить в n имеющихся в наличии двухместных клеток,

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

больше однопородных брачных пар (разнополых кроликов, сидящих в одной

клетке), а разнопородных брачных пар не было вовсе.

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

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

ответа, количество образованных брачных пар.

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

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

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

Ограничение времени: 10 секунд

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

Во входном файле INPUT.TXT содержится последовательность строк

вида:

f r

или

m r

Символы f и m определяют пол кролика (f самка, m - самец), r целое

число от 1 до 10, обозначающее номер породы, к которой принадлежит

кролик. Количество кроликов не превышает 100000.

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

Написанная вами программа должна поместить в выходной файл

OUTPUT.TXT либо строку вида:

b

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

заданными требованиями (b количество образованных брачных пар), либо

строку вида:

No

в противном случае.

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

f2

m3

m2

f3

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

файла):

2

744 Задача 2. Умножение дроби

Задана некоторая правильная периодическая дробь Q и натуральное

число N, Q и N таковы, что количество цифр, используемых для их

описания, не превосходит 100. При изображении дроби Q периодическая

часть заключается в круглые скобки.

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

умножения Q на N, то есть непериодическую часть и минимальный период

числа Q? N. В случае получения результата умножения в виде конечной

дроби скобки опускаются.

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

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

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

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

Входной файл INPUT.TXT содержит две строки. В первой строке

задается дробь Q, а во второй число N.

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

В единственной строке выходного файла OUTPUT.TXT должен

содержаться результат умножения Q на N.

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

0.1 (6)

3

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

файла):

0.5

745 Задача 3. Арифметическая прогрессия

Задана последовательность натуральных чисел из диапазона [1,

2147483647). Количество чисел в этой последовательности не превышает

100000. Необходимо определить, можно ли выстроить эти числа в отрезок

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

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

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

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

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

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

Ограничение времени: 15 секунд

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

Входной файл INPUT.TXT содержит заданную последовательность

натуральных чисел. Числа в файле разделены пробелами или символами

перехода на новую строку.

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

Выходной файл OUTPUT. TXT должен содержать либо строку

Yes

в случае положительного ответа, либо строку

Nо

в противоположном случае.

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

80 50 10 30 70 40 20 60 90

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

файла):

Yes

746 Задача 4. ХАМЕЛЕОН

Игра Хамелеон заключается в следующем. Задан квадрат размером 3х3,

в клетках которого находятся 8 фишек с буквами этого слова, а одна из

клеток пустая. За один ход разрешается одну из фишек переместить на

соседнюю пустую клетку. Цель игры достигнуть расположения фишек,

указанного на рис.1.

ХАМ

ЕЛЕ

ОН

Рис. 1

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

цели за минимально возможное число ходов, либо сообщает, что цель

достичь нельзя.

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

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

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

Ограничение времени: 30 секунд

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

Во входном файле находится матрица 3х3, составленная из больших

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

располагается в соответствующей строке в файле.

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

Ваша программа должна вывести в первую строку выходного файла

искомое число ходов, а в последующие их список. Каждый ход задается

координатами той фишки, которая перемещается. Если искомого плана не

существует, выведите в выходной файл сообщение Нет решения в виде

единственной строки.

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

ХАМ

Е Е

ОЛН

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

2

32

33

747 Задача 5. Максимальный результат

Задано алгебраическое выражение, составленное из неотрицательных

вещественных чисел и знаков операций +, и *. Необходимо расставить в

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

возможным.

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

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

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

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

Ограничение времени: 10 секунд

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

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

выражение длиной не более 250 символов. Внутри чисел пробелы не

допускаются. Выражение содержит не более 50 чисел, каждое из которых

лежит в диапазоне от 0 до 106.

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

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

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

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

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

любой из них.

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

1+2 - 3.0*4

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

0

((1+2)-3)*4