2015-2016 учебный год

Районный тур олимпиады по информатике 6 класс (7 задач)

Задача А.  Забор  (2 балла)

Тому Сойеру нужно покрасить забор, состоящий из 5 досок:

У него есть 3 краски: белая, синяя и красная. Каждая доска должна быть покрашена в один цвет, причём две соседние доски нельзя красить в один и тот же цвет. Сколькими способами он может покрасить забор?

Ответ: 3·24 = 48.

Задача В. Робот-блинопёк (1 балл)

Робот «Блинопёк-1» напёк 10 блинов и сложил их на тарелку в одну стопку. Чуть позже выяснилось, что все блины, кроме трёх, были комом. Робот хочет переложить все хорошие блины наверх стопки, для этого он может перевернуть стопку из нескольких блинов, которые лежат сверху. Известно, что хорошие блины – третий, шестой и седьмой, если считать сверху. Помогите роботу справиться с задуманным, при этом затратив минимальное количество операций. В качестве ответа заполните таблицу, в которой записывайте количество блинов, которые надо перевернуть.

Ответ: 3 операции

Задача С.  Странные весы  (1 балл)

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

Есть 5 монет, среди которых 2 фальшивых. Одна фальшивая монета легче настоящей, а вторая – тяжелее. Определите настоящие монеты за минимальное число взвешиваний на странных весах.

В ответе запишите минимальное количество взвешиваний и заполните таблицу.

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

Задача D.  Лабиринт (1 балл)

В аттракционе «Лабиринт» заблудился новый сотрудник. К сожалению, у него нет с собой карты (схемы) лабиринта, но, совершенно случайно, есть компас. Сотрудник соседнего аттракциона — вышки для прыжков с парашютом составил для товарища последовательность выхода из лабиринта (сотрудник аттракциона не заботился о том, чтобы путь был короткий, но дважды через одну клетку он не отправлял проходить), записал каждый последовательный шаг на пронумерованную карточку, причем шаги использовал только самые простые — на одну клетку на запад, на восток, на север или на юг, связал карточки вместе и закинул в лабиринт. К сожалению, стопка карточек рассыпалась на лету и разлетелась по ветру. До заблудившегося сотрудника долетели лишь карточки №3 и №9, на обеих было написано — на восток.

Вам, как и сотруднику соседнего аттракциона, видна схема лабиринта (заблудившийся сотрудник на виде сверху виден как кружочек, непроходимые стенки видны как черные линии, выход в северо-восточном (правом верхнем) углу). Подскажите, что было написано на карточке №2?

Ответ: на север

Задача E.  Грымзики (2 балла)

Известно, что злобные мистические существа грымзики обладают следующими особенностями:

- грымзики живут в квадратного размера комнатах,

- каждая такая комната имеет один или два входа и один или два выхода,

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

- каждую минуту каждый грымзик перемещается из комнаты, где он находится, в соседнюю комнату, через выход. Это происходит одновременно со всеми грымзиками во всех комнатах,

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

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

Договоримся обозначать наличие грымзика в комнате крестиком (X), а отсутствие — ноликом (О).

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

Стрелками показаны переходы между комнатами. Каждая стрелка — переход между комнатами от выхода из одной комнаты к входу в другую комнату.

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

Укажите, через сколько минут (K) положение грымзиков на изображенной схеме станет точно таким же, как и при начальной расстановке. Приведите последовательность положений грымзиков в комнатах. При этом рисовать комнаты и стрелки не требуется. Достаточно выписать вертикально последовательность K положений грымзиков. В каждой строке — последовательность крестиков и ноликов (начальная последовательность ХООХО и начальную последовательность выписывать не нужно). В строке номер N должно быть указано положение грымзиков в минуту номер N.

Ответ:

6 минут

XXOOX

XOXXO

XXOXX

XOXXX

XOOOX

XOOXO

Задача F.  Шары  (2 балла)

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

Чтобы отсортировать шары, вдоль ленточного конвейера размещаются рабочие. Когда 2 шара, расположенные в неправильном порядке, проходят мимо рабочего, он меняет их местами. На картинке приведён пример, как изменяется порядок шаров, если на конвейере работает один рабочий. 

Сколько рабочих необходимо разместить вдоль конвейера, чтобы отсортировать данный набор шаров?

Ответ: 4 рабочих

Задача G.  Секретный код (1 балл)

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

Ответ: 132 (=12*11)

2015-2016 учебный год

Районный тур олимпиады по информатике 7 класс (7 задач)

Задача А.  Забор  (2 балла)

Тому Сойеру нужно покрасить забор, состоящий из 5 досок:

У него есть 4 краски: белая, синяя, красная и зелёная. Каждая доска должна быть покрашена в один цвет, причём две соседние доски нельзя красить в один и тот же цвет. Сколькими способами он может покрасить забор?

Ответ: 4·34 = 324.

Задача В.  Наводнение (1 балл)

Весной в лесу случился паводок. Леснику необходимо перевезти на лодке на незатопленную опушку лесных обитателей: волка, лису и зайца. Одновременно в лодке могут находиться лесник, а с ним или только лиса, или только волк, или только заяц. В какой последовательности лесник должен перевозить зверей, учитывая, что волк и лиса охотятся на зайца (то есть зайца нельзя оставлять на одном берегу с волком или лисой). Сколько раз лесник должен переплывать реку? В ответе напишите минимальное число и запишите решение в таблице.

В – волк, Л – лиса, З – заяц, Лес - лесник

Решение:

В – волк, Л – лиса, З – заяц, Лес - лесник

Задача С.  Робот-блинопёк (1 балл)

Робот «Блинопёк-1» напёк 10 блинов и сложил их на тарелку в одну стопку. Чуть позже выяснилось, что все блины, кроме трёх, были комом. Робот хочет переложить все хорошие блины наверх стопки. Для этого он может перекладывать стопку из нескольких блинов, которые лежат сверху, на одну дополнительную тарелку и обратно (количество перекладываемых блинов может быть разное и блины перекладываются в том же порядке, как лежали на другой тарелке). Известно, что хорошие блины – третий, шестой и седьмой, если считать сверху. Помогите роботу справиться с задуманным, при этом затратив минимальное количество операций. В качестве ответа заполните таблицу, в которой записывайте количество блинов, которые надо переложить.

Ответ:

ИП: 10 0   (00X00XX000)  ()

1: 8 2  (X00XX000) (00)

2: 5 5 (XX000) (X0000)

3: 3 7 (000) (XXX0000)

4: 10 0 (XXX0000000) ()

И симметричное решение:

ИП: 10 0   (00X00XX000)  ()

1: 3 7  (000) (00X00XX)

2: 5 5 (00000) (X00XX)

3: 8 2 (X0000000) (XX)

4: 10 0 (XXX0000000) ()

Задача D.  Лабиринт (1 балл)

В аттракционе «Лабиринт» заблудился новый сотрудник. К сожалению, у него нет с собой карты (схемы) лабиринта, но, совершенно случайно, есть компас. Сотрудник соседнего аттракциона — вышки для прыжков с парашютом составил для товарища последовательность выхода из лабиринта, записал каждый последовательный шаг на пронумерованную карточку (сотрудник аттракциона не заботился о том, чтобы путь был короткий, но дважды через одну клетку он не отправлял проходить), причем шаги использовал только самые простые — на одну клетку на запад, на восток, на север или на юг, связал карточки вместе и закинул в лабиринт. К сожалению, стопка карточек рассыпалась на лету и разлетелась по ветру. До заблудившегося сотрудника долетела лишь карточка №6, на ней было написано — на восток.

Вам, как и сотруднику соседнего аттракциона, видна схема лабиринта (заблудившийся сотрудник на виде сверху виден как кружочек, непроходимые стенки видны как черные линии, выход в северо-восточном (правом верхнем) углу). Подскажите, что было написано на карточке №7? 

Ответ: на восток

Задача E.  Грымзики (2 балла)

Известно, что злобные мистические существа грымзики обладают следующими особенностями:

- грымзики живут в квадратного размера комнатах,

- каждая такая комната имеет один или два входа и один или два выхода,

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

- каждую минуту каждый грымзик перемещается из комнаты, где он находится, в соседнюю комнату, через выход. Это происходит одновременно со всеми грымзиками во всех комнатах,

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

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

Договоримся обозначать наличие грымзика в комнате крестиком (X), а отсутствие — ноликом (О).

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

Стрелками показаны переходы между комнатами. Каждая стрелка — переход между комнатами от выхода из одной комнаты к входу в другую комнату.

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

Укажите, через сколько минут (K) положение грымзиков на изображенной схеме станет точно таким же, как и при начальной расстановке. Приведите последовательность положений грымзиков в комнатах. При этом рисовать комнаты и стрелки не требуется. Достаточно выписать вертикально последовательность K положений грымзиков. В каждой строке — последовательность крестиков и ноликов (начальная последовательность ХООХО и начальную последовательность выписывать не нужно). В строке номер N должно быть указано положение грымзиков в минуту номер N.

Ответ:

8 минут

XXOOX

XOXOO

XXOXO

XXXOX

XOXXO

XXOXX

XOXOX

XOOXO

Задача F.  Шары  (2 балла)

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

Чтобы отсортировать шары, вдоль ленточного конвейера размещаются рабочие. Когда 2 шара, расположенные в неправильном порядке, проходят мимо рабочего, он меняет их местами. На картинке приведён пример, как изменяется порядок шаров, если на конвейере работает один рабочий и шаров 5 штук.

Сколько рабочих необходимо разместить вдоль конвейера, чтобы отсортировать данный набор шаров?

Ответ: 5 рабочих

Задача G.  Секретный код (1 балл)

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

Ответ:  108 (=12*9)

2015-2016 учебный год

Районный тур олимпиады по информатике 8 класс (7 задач)

Задача А.  Забор  (2 балла)

Тому Сойеру нужно покрасить забор, состоящий из 8 досок:

У него есть 4 краски: белая, синяя, красная и зелёная. Каждая доска должна быть покрашена в один цвет, причём две соседние доски нельзя красить в один и тот же цвет. Сколькими способами он может покрасить забор?

Ответ: 4·37 = 8748.

Задача В.  Увеличитель (2 балла)

Иван на уроке информатики узнал об исполнителе «Увеличитель». Такой исполнитель может выполнять только три команды:

1. Умножь на 2,

2. Прибавь 1,

3. Возведи в квадрат.

Первая из команд умножает число, данное исполнителю, на 2, вторая – прибавляет 1, а третья – возводит это число в квадрат. Программа для такого исполнителя – последовательность цифр. (Например: 1223 – означает, что исходное число сначала умножили на 2, затем 2 раза прибавили по единице и, на последнем шаге, возвели число в квадрат).

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

Ответ: 13 программ

Задача С.  Цветочный магазин (1 балл)

Светлана Николаевна работает в цветочном магазине. В этом магазине продаются цветы всего 3 видов: розы, лилии и ирисы. В магазин часто приходят клиенты и просят составить для них букет. Светлана Николаевна всегда записывает - какие цветы она использует в проданных букетах.

По её данным, за последний месяц, букетов, состоящих только из роз и ирисов, было продано 120, букетов из роз и лилий – 57, а букетов, в состав которых входили розы, лилии и ирисы – 28.

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

Ответ: 149 букетов.

Задача D.  Лабиринт  (1 балл)

В аттракционе «Лабиринт» заблудился новый сотрудник. К сожалению, у него нет с собой карты (схемы) лабиринта, но, совершенно случайно, есть компас. Сотрудник соседнего аттракциона — вышки для прыжков с парашютом составил для товарища последовательность выхода из лабиринта, записал каждый последовательный шаг на пронумерованную карточку (сотрудник аттракциона не заботился о том, чтобы путь был короткий, но дважды через одну клетку он не отправлял проходить), причем шаги использовал только самые простые — на одну клетку на запад, на восток, на север или на юг, связал карточки вместе и закинул в лабиринт. К сожалению, стопка карточек рассыпалась на лету и разлетелась по ветру. До заблудившегося сотрудника долетела лишь карточка №9, на ней было написано — на запад.

Вам, как и сотруднику соседнего аттракциона, видна схема лабиринта (заблудившийся сотрудник на виде сверху виден как кружочек, непроходимые стенки видны как черные линии, выход в северо-восточном (правом верхнем) углу). Подскажите, что было написано на карточке №6? 

Ответ: на север

Задача E.  Грымзики (2 балла)

Известно, что злобные мистические существа грымзики обладают следующими особенностями:

- грымзики живут в квадратного размера комнатах,

- каждая такая комната имеет один или два входа и один или два выхода,

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

- каждую минуту каждый грымзик перемещается из комнаты, где он находится, в соседнюю комнату, через выход. Это происходит одновременно со всеми грымзиками во всех комнатах,

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

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

Договоримся обозначать наличие грымзика в комнате крестиком (X), а отсутствие — ноликом (О).

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

Стрелками показаны переходы между комнатами. Каждая стрелка — переход между комнатами от выхода из одной комнаты к входу в другую комнату.

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

Укажите, через сколько минут (K) положение грымзиков на изображенной схеме станет точно таким же, как и при начальной расстановке. Приведите последовательность положений грымзиков в комнатах. При этом рисовать комнаты и стрелки не требуется. Достаточно выписать вертикально последовательность K положений грымзиков. В каждой строке — последовательность крестиков и ноликов (начальная последовательность ХОХОО и начальную последовательность выписывать не нужно). В строке номер N должно быть указано положение грымзиков в минуту номер N.

Ответ:

15 минут

1. XXOXO
2. XXXOX
3. XOOXO
4. XXOOX
5. XOOOO
6. XXOOO
7. XXXOO
8. XXXXO
9. XXXXX
10. XOOXX
11. XOXOX
12. XOXXO
13. XXOXX
14. XOOOX
15. XOXOO

Задача F.  Шары  (2 балла)

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

Чтобы отсортировать шары, вдоль ленточного конвейера размещаются рабочие. Когда 2 шара, расположенные в неправильном порядке, проходят мимо рабочего, он меняет их местами. На картинке приведён пример, как изменяется порядок шаров, если на конвейере работает один рабочий и шаров 5 штук. 

Сколько рабочих необходимо разместить вдоль конвейера, чтобы отсортировать данный набор шаров?

Ответ: 5 рабочих

Задача G.  Секретный код (2 балла)

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

Ответ: 1320 (=12*11*10)