Задания

Решения задач загружаются в Виртуальном кабинете. Загрузка решений задач будет доступна с 12:00 (мск) 13 ноября 2018 года.

Виртуальный кабинет

Каждая команда или индивидуальный участник получает после регистрации доступ к Виртуальному кабинету.
С помощью Виртуального кабинета команда/индивидуальный участник:

• узнает новости проекта, уточняет ключевые даты
• подает ответы на задания Интернет-олимпиады
• отправляет письма координатору
• оставить свои отзывы и пожелания организаторам проекта

Ключевые даты

Этапы выполнения заданий	Дата получения (начала выполнения) задания	Дата окончания выполнения задания
Выполнение заданий проекта, загрузка работ через Виртуальный кабинет	11-00 (мск) 12 ноября 2018 г.	17-00 (мск) 23 ноября 2018 г.
Публикация итогов проекта		17-00 (мск) 4 декабря 2018 г.
Команды и участники отправляют отзыв о проекте из Виртуального кабинета.	23 ноября 2018 г.	4 декабря 2018 г.

Задачи теоретической части

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

 

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

1. четкость описания решения.
2. корректность решения.

Любой из способов требуется обосновать. Без обоснования оценка за задачу снижается.

Решения задач теоретической части оформляются в виде документа Microsoft Word в соответствии с техническими требованиями и загружаются для проверки в Виртуальном кабинете.

 

1. Рассчитайте, какую территорию захватит конь.

Шахматного коня поставили на клетку бесконечной клетчатой доски. Ему разрешили сделать ровно N ходов. На скольких разных клетках он может оказаться?

Например, при N=1 количество таких клеток равно 8. Опишите алгоритм, отвечающий на этот вопрос.

Комментарий. Задача кажется искусственной, однако, при различных правилах «передвижения коня» похожие модели используются при моделировании распространения лесных пожаров, инфекционных заболеваний и т.п.

 

2. Помогите строевому генералу.

100 новобранцев выстроили перед генералом в каре – квадрат 10×10. Все новобранцы разного роста. Генерал может отдавать команды двух видов:

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

 

3. Помогите юному программисту.

Учитель задал начинающим программистам такое задание: написать программу, которая вводит два числа, что-то делает, а в конце – выводит два числа. Программа обязательно должна иметь следующую структуру:

ВВОД (X, Y)

ЦИКЛ ПОКА УСЛОВИЕ

КАКИЕ-ТО ДЕЙСТВИЯ

КОНЕЦ ЦИКЛА

ВЫВОД (X, Y)

УСЛОВИЕ и КАКИЕ-ТО ДЕЙСТВИЯ школьники должны написать сами. Главное требование – на выводе числа должны появиться в порядке, противоположном тому, в каком он поступили на входе.

Сможете ли вы выполнить задание учителя?

 

4. Помогите криминалисту.

В ряд лежат 8 алмазов. Криминалист знает, что весить они должны 5, 6, 7, 8, 9, 10, 11 и 12 карат, но не знает, какой – сколько. Также он знает, что один из алмазов подменили на более лёгкий. Как криминалист, имея чашечные весы без гирь сможет за наименьшее число взвешиваний определить фальшивый алмаз?

5. Исправьте ошибку строителей

При настилке паркета в квадратной комнате строители допустили ошибку – вместо чёрных и белых квадратов размера 1 дм × 1 дм они постелили квадраты 2 дм × 2 дм. В результате, пол в комнате стал выглядеть так (левый рисунок), вместо того, чтобы выглядеть так (правый рисунок).

            

 

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

 

6. Помогите кому-нибудь из мальчиков выиграть.

Пётр и Вова по очереди переставляют две рядом стоящие цифры в написанном на доске числе. Сначала на доске написано число 12345. Начинает Пётр. Запрещено получать число, которое на доске уже было. Кто не сможет сделать ход – проиграл. Кто из мальчиков может обеспечить себе победу, и как он для этого должен играть?

 

7. Восстановите содержимое памяти.

В компьютере «Five5» каждая ячейка состоит ровно из пяти бит, каждый из которых может быть в состоянии 0 или 1. Вам дано задание восстановить состояние одной из ячеек. Для этого можно воспользоваться следующим действием: предъявить какое-нибудь пятизначное двоичное число от 00000 до 11111, и вам будет дан ответ – в скольких разрядах предъявленное число совпадает с состоянием интересующей вас ячейки. Как можно выполнить задание за возможно меньшее число действий?