Теоретический тур (6 задач)

Теоретический тур (6 задач)

Количество баллов за задачу определяется количеством участников, решивших ее – чем меньше решивших, тем больше баллов. Жюри оценивает решение в процентах, например, наполовину решенная задача оценивается в 50% от количества баллов задачи.

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

Если в задаче требуется предложить алгоритм, то записать его можно по-разному – лучше всего словесно или на псевдокоде, но можно и блок-схемой или на языке программирования, но это не желательно. Главное, чтобы были пояснения или комментарии. Если программа написана крайне неясно, она не засчитывается. Удачи!

Задача 1. “Сумма кодов”.

Выбрать слово, имеющее наименьшую сумму кодов символов в таблице кодировки ASCII (используются строчные буквы). Ответ обоснуйте.

beer

bear

type

deer

hair

Задача 2. “Два берега”.

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

Задача 3. “Приветствие племен”.

Алфавит одного племени состоит из Х символов, алфавит другого содержит в четыре раза больше символов. Племена обменялись приветствиями. Каждое по 100 символов. На сколько бит информации одно приветствие больше другого? Ответ обоснуйте.

Задача 4. “Количество команд”.

Программист написал программу на языке машинных команд, которая последовательно размещается в памяти начиная с нулевого адреса. Каждая команда занимает 4 байта памяти. Шестнадцатеричный адрес последней команды в программе равен 28. Сколько команд содержит эта программа? Ответ обоснуйте.

Задача 5. “Новобранцы”.

На первом построении вновь призванные в армию солдаты построились в шеренгу. По команде старшины «Напра-во!» некоторые солдаты повернулись направо, а некоторые — налево (на 90°). Каждый солдат, оказавшийся лицом к лицу со своим соседом считает, что совершил ошибку и разворачивается на 180°.

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

Задача 6. “ Лягушка”.

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

Практический тур (5 задач)

Поддерживаемые языки программирования: ПАСКАЛЬ (bp), СИ (bc) или БЕЙСИК (qb, gwbasic). При написании программ настоятельно рекомендуется следовать следующим правилам:

w  Файлы следует сохранять в указанном Вам каталоге, лучше войти туда и, находясь там, запускать программы bp, bc, qb.

w  Имена файлам программ с решениями задач давать как РЕГНОМ_НОМЗАД.РАСШ, например 23_2.pas, где 23 – номер участника, 2 – номер практического задания, .pas – расширение файла.

w  Советуем регулярно сохранять файлы, чтобы не потерять их в случае зависания компьютера.

w  Данные считываются из файла INPUT. TXT, где они следуют в порядке их упоминания в условии задачи, и находятся каждое на отдельной строке.

w  Если Вы не умеете работать с файлами, то разрешается ввод данных с клавиатуры при обязательном выводе подсказок о том, какие данные нужно ввести. Например, Введите длину конверта: А = _

w  Результат работы выводится на экран вместе с пояснениями: Письмо нужно сложить пополам 5 раз(а).

w  Если не будет подсказок и пояснений при вводе и выводе данных, то такие программы не будут засчитываться.

w  Вводимые числа помещаются в переменные без переполнения.

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

Задача 1. “Фишки”.

Рассмотрим шахматную доску размером NxN. Какое наименьшее число фишек нужно поставить на клетки шахматной доски для того, чтобы на каждой прямой, проходящей через центр произвольной клетки и параллельной каким-либо сторонам или диагоналям доски, стояла хотя бы одна фишка? (Фишки ставятся в центры клеток).

Пример входных данных:

4

Пример выходных данных:

8

Задача 2. “Слова”.

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

В первой строке входных данных записано выбранное для игры слово. Далее следует число K – количество слов в словаре. В последующих K строках задан "словарь" - множество слов, которые мы считаем осмысленными. Их количество не превышает 100. Слово - это последовательность не более чем 255 маленьких латинских букв. Каждое слово записано в отдельной строке. Слова в словаре, как это ни странно, не обязательно располагаются в алфавитном порядке, но не повторяются.

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

Пример входных данных: soundblaster 10 sound blaster soundblaster master last task sos test bonus done

Пример выходных данных: 7 sound blaster soundblaster last sos bonus done

Задача 3. “Змейка”.

На шахматной доске размером NxN расставлено k пронумерованных фишек. Ежик, который собирает эти фишки, выходит из клетки с координатами (1,1) и должен собрать все фишки в порядке возрастания их номеров. Из клетки с координатами (x, y) ежик может переместиться только в одну из четырех соседних, т. е. в одну из клеток с координатами (x+1,y), (x-1,y), (x, y+1) или (x, y-1), конечно с соблюдением условия, что он не должен выходить за границы доски. Требуется определить, какое минимальное количество ходов нужно сделать, чтобы собрать все фишки. Если ежик проходит через клетку, где содержится фишка с большим номером, чем он сейчас должен взять, то ничего не происходит (он просто проходит, а фишка остается стоять).

Вводятся два числа N и k. Затем вводятся k пар координат (x, y) соответствующих фишек, т. е. сначала для первой фишки, затем для второй фишки и т. д.

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

Пример входных данных:

4 3

3 3

1 4

2 1

Пример выходных данных:

11

Задача 4. “Густой лес”.

На плоскости во всех точках с целочисленными координатами от 1 до N стоят деревья - всего N2 деревьев. Путник находится в точке с координатами (x1,y1), где x1,y1>0 и хоть одна из этих координат больше N (чтобы не оказаться в самом лесу). Требуется определить, видно ли путника из точки с координатами (0,0). Путника не видно, если на прямой, проходящей через точку (0,0) и точку (x1,y1), есть хоть одно дерево.

На вход подается три целых числа – N, x1, y1.

Требуется вывести YES, если путника видно и NO иначе.

Пример входных данных1 5 6 2 Пример выходных данных1 NO

Пример входных данных2 5 7 6 Пример выходных данных2 YES

Задача 5. “Боулинг”.

При игре в боулинг дается десять подходов, каждый из них состоит из двух бросков. Перед каждым подходом на дорожке выставляется 10 кегель. Цель – сбить как можно больше за два броска. Если с первого броска все сбить не удалось, то у вас есть второй бросок, чтобы попасть по оставшимся кеглям. Если будут сбиты все десять кегель с первого броска в подходе, то это называется «strike». Если десять кегель сбиты за два броска, то это «spare». Количество кегель, сбитое в подходе, прибавляется к общей сумме игрока. Но если в предыдущем броске у вас был «strike» или «spare», то еще будут получены дополнительные очки.

Если предыдущий бросок был «strike», то количество сбитых кегель в текущем подходе умножается на два. Если же два предыдущих броска были «strike», то количество сбитых кегель в текущем подходе умножается на три. Если предыдущий бросок был «spare», то на два умножается только количество кегель сбитых первым броском в текущем подходе (например, пусть предыдущий был «spare» и в этот подход игрок двумя бросками сбил всего 8 кегель, 5 и 3 соответственно, тогда к общей сумме будет прибавлено 5*2+3=13 очков).

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

Вводится 10 пар чисел, по одной на подход. Каждое из чисел – количество кегель, сбитое в соответствующем броске (естественно, что каждое число может быть от 0 до 10). Если был «strike», то строка будет такая: 10 0 (потому что второй бросок уже не нужен, т. к. сбиты все кегли, но для таблицы формально будем считать, что вторым броском было сбито 0 кегель).

Требуется вывести одно число – итоговая сумма

Пример входных данных: 6 4 8 2 9 0 0 10 10 0 10 0 6 0 7 3 10 0 9 1

Пример выходных данных: 164 Пояснение: у игрока было 5 «spare» - 1-й, 2-й, 4-й, 8-й и 10-й подходы и три «strike» - 5-й, 6-й и 9-й подходы. Промежуточные итоговые суммы были следующие: 10 (+ 6+4) 28 (+ 2*8+2) 46 (+ 2*9+0) 56 (+ 10) 76 (+ 2*10+0) 96 (+ 2*10+2*0) 114 (+ 3*6+3*0) 124 (+ 7+3) 144 (+ 2*10+0) 164 (+ 2*9+2*1)