Задачи заочного тура по предмету Информатика фестиваля "Юные интеллектуалы среднего Урала"

Перед Вами задачи по информатике заочного тура фестиваля "Юные интеллектуалы Среднего Урала".

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

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

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

Дискеты могут быть возвращены на областной олимпиаде или при личном обращении в Институт математики и механики УрО РАН (обратиться к Сидоровой Е.В.).

Решения следует выслать до 15 декабря по адресу 620219, ГСП-384, Екатеринбург, ул. С. Ковалевской, 16, Институт математики и механики УрО РАН, с пометкой "олимпиада по информатике"

1. Заданы четыре группы чисел:

   1-ая группа	2-ая группа	3-ая группа	4-ая группа
   0 1 2 3 4 5 6 7	0 1 2 3 8 9 10 11	0 1 4 5 8 9 12 13	0 2 4 6 8 10 12 14

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

   Пример: Если задумано число 5, то в компьютер вводятся номера групп: 1, 3. Компьютер должен вывести сообщение: "Задуманное число - 5".

2. Написать программу расшифровки сообщения, закодированного по описанному ниже принципу. Пусть дан шифр (набор цифр 432513 и текст - "настоящий виновник кражи алмазов". Записываем текст без пробелов и под ним цифры шифра:

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

   Каждая буква алфавита заменяется на букву номер которой равен номеру исходной буквы в алфавите плюс цифра, стоящая под ней. При этом буква с номером 33+К есть буква с номером К.

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

   Шифр - строка из шести цифр;

   зашифрованное сообщение - строка не более чем из 64-х символов.

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

   расшифрованное сообщение.

    

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

   (1,1)
   		К
   						Л

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

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

   Комар за один ход может перелететь на одну из (максимум 8-ми) соседних клеток болота.

   Если лягушка прыгает на клетку, на которой находится комар, или пролетает над ней в прыжке, то она съедает комара.

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

   запрашивает начальные положения лягушки и комара;

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

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

4. Дано N целых чисел (1<N<100). Каждое из них можно изменить не более чем на величину L (целую), как в сторону увеличения, так и в сторону уменьшения, или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. Написать программу поиска такой операции, в результате которой остается наименьшее количество чисел.

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

   в первой строке значения L (1<=L<=32000) и N;

   во второй строке N чисел (-32000 <= N <=32000), записанных через пробел.

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

   количество оставшихся чисел.

   Пример.

   10 3

   11 21 27

   Результат - 1.

   Внимание! Здесь был неверный ответ в примере. Правильный ответ - 1.

5. На координатной плоскости XOY имеется замкнутая ломаная без самопересечений. Она задана целочисленными координатами точек излома (x₁,y₁), ... ,(x_n,y_n), перечисленных в порядке обхода вдоль ломаной против часовой стрелки.

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