Теоретический тур, не требующий работы за компьютером

Теоретический тур, не требующий работы за компьютером.

Максимальное время выполнения: 60 минут

Максимальный балл за каждую задачу: 20 баллов

1.  Алгоритм.

На ленте напечатаны цифры. Над лентой находится некий исполнитель, который может выполнять три команды:

(<)- передвинуться на одну цифру влево;

(+) - изменить цифру, над которой он находится в данный момент, по правилу: 1 изменяется на 2, 2 на 3, 3 на 4, 4 на 5, 5 на 6, 6 на 7, 7 на 8, 8 на 9, 9 на 0, 0 на 1.

(-) - изменить цифру, над которой он находится в данный момент, по правилу: 1 изменяется на 0, 2 на 1, 3 на 2, 4 на 3, 5 на 4, 6 на 5, 7 на 6, 8 на 7, 9 на 8, 0 на 9.

На ленте напечатано число 2907, исполнитель находится над цифрой 7 (т. е. над последней цифрой). Как уменьшить число на 38 за минимальное количество ходов? Ответ приведите в виде строки из последовательности команд. Например, строка +<- для числа 52 приведет к результату 43.

Решение:

2907-38=2859

++<+++++<-

или

++<-----<-

2. Решите уравнение.

Дано уравнение 1000+х= где числа записаны в двоичной системе. Найденное число приведите в десятичной и троичной системе.

Решение:

х=02=1101012

х=1101012=1+4+16+32=5310

х=5310=27*1+9*2+3*2+2=12223

3. Размер файла.

В какой последовательности расположатся данные о размерах файла по убыванию объема информации: 0,5 Гбайт, 6 байт, 600 Мбайт, 1024 Кбайт, 0,75 Мбайт, 8 Гбайт.

В ответе каждый размер приведите в байтах.

Решение:

8 Гбайт = байт

600 Мбайт = байт

0,5 Гбайт = байт

1024 Кбайт = 1048576 байт

0,75 Мбайт = 786432 байт

6 байт.

4. Логическая задача.

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

Решение: (http://www. *****/prob1294solve. html)

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

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

Если разделить каждую сторону на 4 четверти и двигаться по периметру по часовой стрелке, то каждой собаке надо встать на 1/4 в стороне от угла. Исходим из того, что в прямоугольном равностороннем треугольнике соотношение катета к гипотенузе не превышает 1,5, следовательно, собака всегда успеет добежать быстрее волка в любую точку края поля (читай - гипотенузы).

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

(http://www. smekalka. *****/funny/answer_funny_01.html)

Пусть v - максимальная скорость волка. Проведём через точку B, в которой находится волк, две прямые, параллельные диагоналям квадрата. Пусть эти прямые пересекают контур квадрата в точках C1, C2, C3 и C4. Поскольку скорость перемещения каждой из точек C1, C2, C3 и C4 не больше чем v√2<1,5v, то собаки смогут в каждый момент времени находиться в этих четырёх точках и, следовательно, не выпустят волка за пределы поля.

5. Найти машину.

Произошло столкновение двух автомобилей. В результате один автомобиль скрылся с места преступления. Некоторые свидетели происшествия запомнили несколько цифр и букв номера этой машины, но не запомнили их порядок, при этом цифры и буквы в номере не повторяются. Вот они: 4, 2, 7, И, Л. Для того чтобы найти владельца машины нужно знать его точный номер (это четыре цифры и 3 буквы русского алфавита). Сколько нужно перебрать номеров, чтобы найти его?

Решение:

Для каждой комбинации трех цифр (это числа - 427, 472, 247, 274, 742, 724; всего 3!=6) существует по 4 варианта размещения четвертой цифры, например, для 427 можно рассмотреть 427*, 42*7, 4*27, *427, где * - любая цифра от 0 до 9 (всего 10*4=40). Так как цифры не повторяются, то, например, для 427* числа 4277, 4272, 4274 не рассматриваются. Таких чисел для каждой четверки 3 (3*4=12). Получим (10*4-3*4)*3!=28 6=168.

Точно так же можно посчитать для букв: ИЛ, ЛИ (2!=2), далее ИЛ*, И*Л, *ИЛ (3*33=99), исключаем повторения, например, для ИЛ* это ИЛИ, ИЛЛ (2*3=6). Итак (33*3-2*3)*2!=93*2=186

Всего для каждой комбинации из цифр 168 может быть 186 комбинаций из букв. Итого 186*168=31248.

Практический тур на компьютере.

Максимальное время выполнения: 100 минут

Максимальный балл за каждую задачу: 20 баллов

1. Кофе с молоком.

В семье Ивановых все любят пить кофе с молоком, но в разных пропорциях. Так папа пьет в отношении 3 части кофе и 1 часть молока, т. е. в отношении 3:1. Мама любит разбавлять кофе молоком в отношении 2:1. А сын - поровну. Однажды они выехали на пикник в ближайший пригородный поселок. В местном кафе кофе с молоком не подают. Но есть автоматы, которые наливают сколь угодно кофе и отдельно молоко. У бармена есть только три емкости: по 300, 400 и 500 миллилитров.

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

Для решения задачи можно использовать исполнитель Водолей из комплекта программ КуМир. Ответ представьте в виде алгоритма (словесного, графического или в виде программы в среде КуМир).

Решение:

Обозначим емкости за буквы A=300, B=400, C=500. Будем обозначать действия следующим образом:

м=>А налить молоко в А до краев;

к=>С налить кофе в С до краев;

А=> вылить содержимое из А;

В=>А перелить содержимое из В в А до краев, если возможно, а остаток оставить в В;

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

для папы (1:3): к=>А, А=>В, м=>В, В=>С, к=>А, А=>В, м=>В; получится 800 мл по 400 мл в В и С.

для мамы (1:2): к=>С, С=>А, С=>В, А=>, В=>А, м=>А, к=>С, А=>В, С=>А, А=>, С=>А, м=>А, получится 600 мл по 300 мл в В и А

для сына (1:1): к=>С, С=>А, С=>В, м=>В, А=>, к=>С, С=>А, А=>, С=>А, В=>С, А=>В, м=>В, получится 800 мл по 400 мл в В и С.

2. Кино и реклама.

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

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

Все данные хранятся в электронной таблице films. xls.

Решение:

Для решения, нужно расписать время показа фильма на маленькие временные отрезки, например, на 5 минут. Выделить время на рекламу и рассмотреть разные варианты переключения. Вот несколько из вариантов:

1 фильм	2 фильм	3 фильм	итого
45	80	80	205
60	60	80	200
60	75	70	205

Из условия задачи выбираем последний вариант. Порядок переключений каналов будет такой: 3 (25 мин), 1 (25 мин), 3 (10 мин), 1 (15 мин), 2 (20мин), 1 (15 мин), 3 (20 мин), 2 (20 мин), 1(5 мин), 3 (15 мин), 2 (20 мин), 2 (15 мин).

3. Восстановить рисунок.

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

Все части рисунка Маша собрала и отсканировала в отдельные файлы с именами image01.bmp, image02.bmp и т. д. Помогите Маше восстановить рисунок и разукрасьте его.

Готовый файл сохраните с именем image. bmp (рисунок взят с сайта http://raskraska. *****/forum/12-18-1).

4. Разгадать шифр.

Профессор Знайка для передачи данных научного эксперимента своим коллегам использовал специальный ключ. В один прекрасный день Незнайка выкрал этот ключ и выбросил в реку. У Знайки сохранились предыдущие послания и их исходные тексты. Помогите ему восстановить ключ и зашифровать сообщение. Все исходные данные хранятся в файлах: TekstNN. doc - исходные тексты, ShifrNN. doc - зашифрованные тексты, где NN - номер послания. Например, текст в файле Tekst01.doc соответствует зашифрованному тексту в файле Shifr01.doc.

Файл Tekst05.doc нужно зашифровать и сохранить в файле Shifr05.doc. Напишите алгоритм получения зашифрованного текста (в словесном, графическом или в виде программы в среде КуМир).

Решение:

Tekst05.txt

деньги потерял - ничего не потерял, время потерял - многое потерял, здоровье потерял - все потерял.

Shifr05.txt

|27|03|19|05|12|14| |30|26|09|03|17|11|25| |-| |19|14|32|03|12|26| |19|03| |30|26|09|03|17|11|25|,| |28|17|03|10|11| |30|26|09|03|17|11|25| |-| |10|19|26|12|26|03| |30|26|09|03|17|11|25|,| |22|27|26|17|26|28|05|03| |30|26|09|03|17|11|25| |-| |28|01|03| |30|26|09|03|17|11|25|.|

Все буквы русского алфавита записаны в строчку:

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

Для перевода используем порядковый номер буквы, начиная с 01 до 33, которые записываются через |. Регистр букв не учитывается. Знаки препинания оставляем без изменения.

Программа на языке КуМир:

алг

нач

сим с

лит к, р,т, в

цел н, д, у

к:="съешьщёэтмягкихфранцузбулодвыпйчю"

ввод в

вывод "|"

нц для у от 1 до длин(в)

с:=в[у]

д:=0

нц для н от 1 до 9

если с=к[н]

то

р:="0"+цел_в_лит(н)+"|"

д:=1

выход

все

кц

нц для н от 10 до 33

если с=к[н]

то

р:=цел_в_лит(н)+"|"

д:=1

выход

все

кц

если д=0

то

р:=с+"|"

все

вывод р

кц

кон

5. Кодировка символов.

Выберите слово, которое имеет наименьшую и наибольшую сумму кодов в таблице ASCII: 12.12.12, 2012, Модель, House. В ответе напишите слово и значение суммы кодов в десятичной системе счисления.

Для ответа можно воспользоваться кодировочной таблицей в файле ASCII. xls (коды указаны в шестнадцатеричной системе счисления) или стандартной программой “Таблица символов”, выбрав шрифт “Терминал”.

Решение:

12.12.12 3116*3+3216*3+2Е16*2=49*3+50*3+46*2=389

2012 3016+3116+3216*2=48+49+50*2=197 (наименьшая)

Модель СС16+EE16+E416+E516+EB16+FC16=

=204+238+228+229+235+252=1386 (наибольшая)

House 4816+6F16+7516+7316+6516=72+111+117+115+101=516