Задачи по информатике

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

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

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

С клавиатуры вводится исходная строка длиной менее 80 символов.

Пример

To be or not to be - that is the question. Cool!

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

На экран следует вывести результирующую строку.

Пример

To be or not to be - taht is the qetsioun. Cool!

Задача 2. «Сейф» – 40 баллов

Зуев П.В.

Сейф заперт при помощи электронного кодового замка. Для ввода отпирающей сейф комбинации служит квадратная 16-клавишная клавиатура (4 ряда по 4 клавиши в каждом). Клавиши пронумерованы числами от 1 до 16 как показано на рисунке:

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

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

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

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

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

Ваша программа должна запросить с клавиатуры число N - количество светящихся клавиш (0 ≤ N ≤ 15). Затем программа должна считать с клавиатуры N чисел, являющихся номерами этих клавиш. Ввод каждого числа завершается нажатием Enter.

Пример

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

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

Пример

Задача 3. «День» – 15 баллов

Шараев Д.Я., Устюжанин А.М.

Поделим весь 2004-й год на 1000 равных частей. Если первая часть начинается в 0 часов 1 января, то 1000-ная заканчивается в 24 часа 31 декабря. Вам необходимо написать программу, которая будет по введенному номеру части N (1 < N < 1000) определять в какой день какого месяца заканчивается эта часть.

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

С клавиатуры вводится целое число N (1 < N < 1000).

Пример

900

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

На экран следует вывести искомую дату в виде двух целых чисел через пробел – день и месяц.

Пример

25 11

8-9 класс - 2-й тур

Задача 1. «Последовательность» – 40 баллов

Зуев П.В., Устюжанин А.М.

Последовательность натуральных чисел x(0), x(1), ..., x(n), ... задана правилом:

a) x(0) - заданное натуральное число, не превосходящее 30000;

b) если уже известно число x(n), то следующее x(n+1) вычисляется как квадрат суммы цифр числа x(n).

Например, для x(0) = 4 получим x(1) = 4² = 16, x(2) =(1+6)² = 49, x(3) =(4+9)² = 169, x(4) =(1+6+9)² = 256, x(5) =(2+5+6)² = 169, ...

Вам необходимо написать программу, которая с клавиатуры вводит число x(0) и отвечает на два вопроса:

1) какова (наименьшая) длина цикла в последовательности;

2) каково максимальное k такое, что в последовательности x(0), x(1), ..., x(k) нет повторяющихся элементов.

В рассмотренном примере цикл 169 – 256, длина цикла равна 2. Первый повторяющийся элемент x(5) = x(3) = 16, следовательно, k = 4.

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

С клавиатуры вводится исходное натуральное число x(0).

Пример

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

Программа должна в отдельных строках вывести на экран длину цикла и k.

Пример

длина цикла: 2

k=4

Задача 2. «Призы» – 20 баллов

Устюжанин А.М.

В соревнованиях на дальность стрельбы косточками от вишни участвовало K (0<K<10) человек. Для награждения участников имеется N (0<N<1000) вишен. Ни у одной пары участников не оказалось равных результатов. Судьи приняли следующее решение:

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

Какое максимальное количество вишен может получить победитель.

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

С клавиатуры следует ввести 2 натуральных числа – K и N, завершая ввод каждого нажатием клавиши Enter.

Пример

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

На экран следует вывести количество вишен в призе победителю, если вишен у судей достаточно, и 0 в противном случае.

Пример

Задача 3. «ЯПИ» - 40 баллов

Устюжанин А.М.

Введение в ЯПИ.

Рассмотрим некий язык программирования инструкций ЯПИ.

Алфавит языка состоит из 26 строчных латинских букв, 10 арабских цифр, знаков + - ( ) : , > и знака пробела. Никакие другие символы в программах ЯПИ недопустимы.

Константы ЯПИ – целые без знака, состоящие не более чем из 4 цифр.

Идентификаторы переменных состоят из буквы и цифры (именно в таком порядке).

Переменные только целого типа.

Арифметические и логические выражения записываются из констант и переменных, соединенных знаками арифметических и логических операций, по правилам подобно таким языкам программирования как Паскаль, Си или Бэйсик.

Операция присваивания состоит из арифметического выражения, знака : и идентификатора переменной, которой присваивается значение выражения.

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

Операция ввода данных с клавиатуры состоит из зарезервированного слова rd и записанного в скобках идентификатора переменной. Операция вывода - из зарезервированного слова wd и записанного в скобках идентификатора переменной.

Каждая операция записывается в отдельной строке без переноса на следующую.

Программа имеет следующую структуру:

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

· во второй строке - операция ввода данных;

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

· в последней строке (и только в ней) – операция вывода данных.

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

Задача

Вам необходимо на языке ЯПИ написать программу умножения введенного числа на 5. Программу следует записать в текстовый файл с именем yapi без расширения.

Для проверки правильности и трансляции программы можно воспользоваться предлагаемым Вам препроцессором PREPRO.EXE, который переводит ЯПИ в ПАСКАЛЬ и далее в EXE-программу.

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

Отсутствуют.

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

Программа должна быть записана в текстовый файл с именем yapi без расширения.

Пример программы на языке ЯПИ, которая добавляет к введенному положительному числу 1, а к нулю – 2, и выводит его.

rd(n1)

ifn1>0,n1+1,2:n1

wd(n1)

10-11 класс - 1-й тур

Задача 1. «Роботы» – 45 баллов

Устюжанин А.М.

Роботы уже умеют играть в футбол, и вы можете помочь им в этом нелегком деле. В каждый момент каждый игрок команды знает, сколько у него шансов в попытке забить гол противнику и сколько шансов в попытке передать мяч каждому из партнеров. Рассмотрим упрощенную ситуацию, когда в течение некоторого времени шансы остаются постоянными, несмотря на некоторое изменение положения игроков. Пусть в начале нашей ситуации мяч находится у вратаря, имеющего номер 11. Имея всю информацию от всех игроков, нужно так рассчитать передачи, чтобы шансы забить гол были максимальными. Если есть несколько вариантов передач для получения необходимого результата, то следует выбрать такой, при котором количество передач минимально. Если и таких вариантов несколько, то выбирается любой из них. При передачах шансы, что мяч не перехватят противники, перемножаются. Очевидно, что шансы передать мяч и забить гол не могут быть больше 1.

Например, у вратаря (И11) есть 0.1 шансов передать мяч игроку с номером 1 (И1), 0.02 шанса – любому другому игроку (Иi , i=2, …, 10) и 0.01 шанса – забить гол. У И1 0.5 шансов передать мяч И2, 0.01 шанса – любому другому игроку и 0.02 шанса забить гол. У И2 по 0.02 шанса передать мяч любому другому игроку и 0.9 шансов – забить гол. У остальных игроков нет шансов передать мяч и забить гол. Очевидно, что вратарь должен передать мяч И1, тот И2, а И2 пытаться забить гол. Это дает 0.1*0.5*0.9 = 0.045 шанса забить гол. Если же вратарь сразу передаст мяч И2 и тот пробьет по воротам, то шансы забить гол будут 0.02*0.9 = 0.018. Аналогично можно просчитать другие варианты. Заметим, что для такой постановки задачи несущественно, какие шансы у игрока «передать мяч себе».

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

Программа должна ввести с клавиатуры имя файла. Затем программа должна прочитать исходные данные из текстового файла с этим именем. Файл содержит 11 строк. В каждой строке 11 вещественных чисел, записанных через пробел, - информация для игрока, номер которого совпадает с порядковым номером строки. Пусть номер строки i, а номер числа в строке j. Тогда при i=j число означает шансы игрока забить гол, а при i≠ j – шансы i-того игрока передать мяч j-тому. Все числа заданы не более чем с двумя знаками после десятичной точки.

Пример

0.02 0.5 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01

0.02 0.9 0.02 0.02 0.02 0.02 0.02 0.02 0.02 0.02 0.02

0 0 0 0 0 0 0 0 0 0 0

0.1 0.02 0.02 0.02 0.02 0.02 0.02 0.02 0.02 0.02 0.01

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

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

Пример

11 1 2

0.045

Задача 2. «Суммы» – 15 баллов

Устюжанин А.М.

Пусть задано натуральное число K. Ваша программа должна просуммировать следующие числа: 1; 1, 2; 1, 2, 3; 1, 2, 3, 4; ..., K. Например, для K=5 это будут числа 1; 1, 2; 1, 2, 3; 1, 2, 3, 4; 1, 2, 3, 4, 5, а сумма будет равна 1+3+6+10+15=35.

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

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

Пример

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

На экран следует вывести искомую сумму.

Пример

Задача 3. «Дизайнер» – 40 баллов

Зуев П.В., Лукин А.С.

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

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

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

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

Координаты вершин листа и прямоугольников являются действительными числами и даны в прямоугольной системе координат, в начале которой находится один из углов листа. Стороны листа параллельны соответствующим осям координат. Цвета обозначены целыми числами и могут иметь номера от 1 до 100 включительно (Вася не обязан использовать все эти цвета). Все прямоугольники невырождены (т.е. имеют ненулевую площадь).

Программа должна ввести с клавиатуры имя файла. Затем программа должна прочитать исходные данные из текстового файла с этим именем. Содержимое файла представляет собой несколько чисел в порядке, приведённом ниже.

Первая строка файла содержит три числа, разделенные пробелами. Первые два из них – x₀ и y₀ – задают координаты второго угла листа (0 < x₀≤ 1000, 0 < y₀≤ 1000). Третье число – c₀ – задает номер цвета чистого листа.

Вторая строка содержит только одно число N – количество прямоугольников, нарисованных Васей (0 ≤ N ≤ 200).

Далее следуют N строк, содержащих по пять чисел, разделенных пробелами – x_n₁, y_n₁, x_n₂, y_n₂, c_n, где x_n₁, y_n₁, x_n₂, y_n₂– координаты двух противоположных вершин n-го прямоугольника, c_n – номер цвета n-го треугольника. Прямоугольники во входном файле перечислены в том порядке, в котором Вася их рисовал.

Пример

10 10 1

1 9 9 1 3

4.5 4.5 5.5 5.5 2

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

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

Пример

1 36.00

2 1.00

3 63.00

10-11 класс - 2-й тур

Задача 1. «Автомобили» – 35 баллов

Устюжанин А.М.

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

Дорога моделируется полосой, разбитой на пронумерованные от 0 до N ячейки.
Каждый автомобиль занимает ровно одну ячейку, два автомобиля могут находиться в соседних ячейках.
В ячейке N находится препятствие (красный светофор). Автомобиль может находиться только в ячейках с номерами, меньшими N .
В ячейке 0 находится зеленый светофор. Автомобиль может находиться в этой ячейке.
Движение автомобилей пошаговое. На каждом шаге кроме информации о положении автомобиля (номер занимаемой ячейки) известна скорость, т.е. количество ячеек, на которое автомобиль сместится по направлению к красному светофору при переходе к следующему шагу.
На нулевом шаге дорога пуста. На очередных шагах в ячейке 0 может появиться автомобиль с известной положительной скоростью.
При переходе от одного шага к другому кроме положения автомобиля может измениться его скорость. При этом изменение скорости по модулю не более 1.
Обгон на однополосной дороге невозможен.

Ваша программа должна моделировать движение (положение автомобилей и их скорости) на шагах от 1 до заданного шага K. На каждом шаге автомобили, с одной стороны, должны оказаться максимально близко к красному светофору, а с другой, должны иметь скорости, которые позволили бы им на следующих шагах остановиться перед светофором и не столкнуться с впередиидущими.

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

Ваша программа должна ввести с клавиатуры имя файла. Заметим, что имена входных файлов не будут иметь расширения. Затем программа должна прочитать исходные данные из текстового файла с этим именем. Каждая строка файла содержит два целых числа, разделенных пробелами. Первое число первой строки – N (10<N<100), второе число – K (0<K<100). В следующих строках первое число – номер шага, на котором очередной автомобиль появился в ячейке 0, а второе – его скорость. Признаком окончания ввода является конец файла. Предполагается, что входные данные позволяют провести правильное моделирование.

Пример файла AUTO

12 3

1 2

2 4

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

Результаты моделирования следует записать в текстовый файл с именем входного и расширением OUT. В каждой его строке через пробел должны быть записаны скорости автомобилей на очередном шаге, начиная с первого и до K-го шага. Таким образом, файл должен состоять из K строк. Значения скорости автомобилей должны быть в порядке расположения автомобилей от красного светофора (ячейки N). Если на некотором шаге автомобили на дороге отсутствуют, то должна быть записана пустая строка.

Пример файла AUTO.OUT

3 4

3 3

Задача 2. «Простые слагаемые» – 35 баллов

Устюжанин А.М.

Известно, что каждое натуральное число K, кроме 1, можно однозначно представить в виде произведения простых сомножителей. Ваша задача – представить такое число в виде суммы простых чисел таким образом, чтобы количество слагаемых было минимально возможным. Если таких представлений несколько, то достаточно найти любое. Время работы программы на компьютере, сравнимом с PII/500MGz, не должно превышать log₁₀₀ K минут.

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

С клавиатуры вводится число не превосходящее 50000.

Пример

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

На экран следует вывести искомые слагаемые по одному в строке.

Пример

Задача 3. «Фибоначчи» – 30 баллов

Устюжанин А.М.

Введение в ЯППИ.

Рассмотрим некий язык процедурного программирования инструкций ЯППИ.

Алфавит языка состоит из 26 строчных латинских букв, 10 арабских цифр, знаков + - ( ) : , > и знака пробела. Никакие другие символы в программах ЯППИ недопустимы.

Константы ЯППИ – целые без знака, состоящие не более чем из 4 цифр.

Идентификаторы состоят из буквы и цифры (именно в таком порядке).

Переменные только целого типа.

Арифметические и логические выражения записываются из констант, переменных, вызовов функций, соединенных знаками арифметических и логических операций, по правилам подобно таким языкам программирования как Паскаль, Си или Бэйсик. Вызов функции состоит из идентификатора функции и фактического параметра в скобках. В качестве фактического параметра может выступать арифметическое выражение.

Каждая операция записывается в отдельной строке без переноса на следующую.

Описание функции в ЯППИ имеет следующую структуру:

· в первой строке – заголовок, состоящий из зарезервированного слова fn, идентификатора функции и идентификатора формального параметра в скобках;

· во второй строке перечислены локальные переменные данной функции;

· в следующих строках - операции присваивания и выбора в соответствии с алгоритмом решения задачи (такие строки могут отсутствовать);

· в последней строке (и только в ней) – операция присваивания, где в качестве переменной, которой присваивается значение выражения, выступает идентификатор функции; именно это значение возвращается в вызывающую программу.

Главная программа имеет следующую структуру:

· в первой строке перечислены глобальные переменные;

· в следующих строках находятся описания функций (такие строки могут отсутствовать);

· в следующей строке - операция ввода данных;

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

· в последней строке (и только в ней) – операция вывода данных.

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

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

Задача

Вам необходимо на языке ЯППИ написать программу вычисления чисел Фибоначчи, т.е. последовательности чисел, подчиняющихся рекуррентному соотношению a_n₊₁ = a_n + a_n_-1 с заданными двумя первыми членами, равными единице (a₀=1, a₁=1). Программа должна вводить номер числа Фибоначчи, а выводить значение этого числа. Программу следует записать в текстовый файл с именем yappi без расширения.

Для проверки правильности программы можно воспользоваться предлагаемым Вам препроцессором PREPRO.EXE, который переводит ЯППИ в ПАСКАЛЬ и далее в EXE-программу.

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

Отсутствуют.

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

Программа должна быть записана в текстовый файл с именем yappi без расширения.

Пример программы на языке ЯППИ, которая умножает введенное число на 11:

fnq2(m0)

m0+m0:m1

m1:q2

rd(n1)

ifn1>0,q2(q2(q2(n1))+n1)+n1,0:n1

wd(n1)