Теоретический тур

1. Найти несколько следующих членов последовательности натуральных чисел 7, 11, 13, 14, 19, 21, 22, 25, ... и привести описание алгоритма их нахождения.

2. В данной таблице 12*12 клеток, содержащей натуральные случайные числа от 1 до 9, найти и нарисовать маршрут от центра клетки (1;1) до центра клетки (12;12) так, чтобы:

а) маршрут состоял из отрезков, соединяющих центры соседних клеток, имеющих общую сторону;

б) маршрут, удовлетворяющий предыдущему условию, имел наименьшую длину;

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

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

Объяснить ход нахождения маршрута.

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

Доказать, что директор может достичь свою цель за

а) 3 дня, если N=4;

б) 6 дней, если N=8;

в) 15 дней, если N=32.

(Считать, что за это время массы слонов не меняются.)

4. а). Имеется механизм, состоящий из N расположенных "в одной плоскости" свободно надетых на зафиксированные оси одинаковых пронумерованных шестеренок.

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

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

Практический тур

5. Рассмотрим следующие числовые последовательности:

(ai) - последовательность всех простых чисел: 2, 3, 5, 7, ...;

(bj) - последовательность индексов i тех ai, которые содержат цифру k;

(cm) - последовательность индексов j тех bj, которые содержат цифру k;

(dn) - последовательность индексов m тех cm, которые содержат цифру k.

Для введенных k (0k9) и N (1N5) определить dN.

Примечание 1. Члены последовательностей индексируются числами 1, 2, 3, ...

Примечание 2. В задаче говорится о цифрах в десятичной записи.

6. Имеется цепочка символов ограниченной длины, состоящая из букв латинского алфавита.

Можно выполнять свертку повторяющихся подстрок этой строки по следующим правилам:

а) несколько последовательных повторений одной и той же подстроки заменяются так:

aaa 3(a),

abcbcd a2(bc)d,

б) правило а) можно применять многократно и к частично свернутой строке, например:

2(a)b2(a)b 2(2(a)b).

Требуется выдать для введенной строки свертку по возможности наименьшей длины (считая символы свертки n(.) одним символом).

6-8 классы, теоретический тур

7. Во время поездки на поезде девочка заменила в названии поезда каждую букву ее номером в русском алфавите и получила запись из единиц и двоек "211221-21221". Определить откуда и куда идет поезд?

8. Как перевезти в лодке с одного берега на другой козла, капусту, двух волков и собаку, если известно, что волка нельзя оставлять без присмотра с козлом и с собакой, собака "в ссоре" с козлом, а козел "неравнодушен" к капусте? В лодке только три места, поэтому можно брать с собой одновременно не более двух животных или одно животное и капусту.

9. Известно, что "медные" монеты в 1, 2, 3 и 5 копеек весят 1, 2, 3 и 5 грамм, соответственно. Есть по одной монете в 1, 2, 3 и 5 копеек, одна из которых фальшивая (отличается по весу от настоящей). Как на рычажных весах без гирь за два взвешивания определить эту фальшивую монету?

10. В бочке 18 литров бензина. Имеется два ведра по 7 литров, в которые надо налить по 6 литров. Кроме того, есть черпак объемом 4 литра. Как осуществить разлив?

11. Если единицу 1000 раз умножить на 2, то получим число "2 в степени 1000". Найти две последние цифры этого числа. Указать алгоритм определения двух последних цифр числа "2 в степени n" для произвольного натурального n.

12. Какое минимальное количество памяти достаточно для хранения слова из 8 букв, если оно содержит только русские заглавные буквы и не содержит букву Ё. Описать способ хранения таких слов.

6-8 классы, практический тур

13. Дано время (часы, минуты, секунды) - три натуральных числа. Составить программу определения времени через 10 секунд.

14. Слово шифруется следующим образом: после первых двух букв вставляется слог "БУ", после следующих двух букв вставляется слог "КА", это повторяется до тех пор пока в слове есть еще хотя бы две буквы.

а). Написать программу такой шифровки слова. Например, слово "КОЛОБОК" шифруется как "КОБУЛОКАБОБУК".

б). Написать программу расшифровки слова, зашифрованного по этому правилу. Например, из шифровки "КАБУРАКАНДБУАШКА" получается слово "КАРАНДАШ".