Задания олимпиады «Бельчонок» по информатике для 9 класса. В работе 10 заданий по логике, системам счисления, обработке изображений и строк. К двум заданиям приложены текстовые файлы.
Ответы к олимпиаде «Бельчонок» по информатике
Задания по информатике — 9 класс
Задание 1.
Бельчонок исследует методы выделения границ объектов в компьютерном зрении. Для анализа изображений размером 5 на 5 он предложил следующую модифицированную формулу-условие для детекции границы:
(в случае выхода за границу изображения считать I(x + 1, y) = I(x, y) и I(x, y + 1) = I(x, y));
I(x, y) = R + G + B3.
R, G, B – числа от 0 до 255, определяющие цвет точки как интенсивность красного, зеленого и голубого цветов соответственно.
Оказалось, что на его изображении было 13 точек, которые он идентифицировал как граничные, но после оказалось, что при обработке исходного изображения часть пикселей повредилось и теперь они обозначены как (?).
Посчитайте, сколько всего возможных троек (R1, G1, B1), (R2, G2, B2) придется передать Бельчонку в худшем случае, чтобы найти исходное изображение.
Вам дано такое изображение (дополнительно файл 9_7.txt):
| 211,169,212 | 163,73,164 | 163,73,164 | 183,112,183 | 163,73,164 |
| 224,193,224 | 211,168,211 | 168,168,168 | 133,133,133 | 122,129,100 |
| 173,130,173 | 163,73,164 | (?) | 0,0,0 | 186,232,43 |
| 24,24,24 | 0,0,0 | 0,0,0 | 188,232,50 | 181,230,29 |
| 0,0,0 | 0,0,0 | 0,0,0 | 181,230,29 | 181,230,29 |
Задание 2.
Укажите все формулы, которые эквивалентны приведенной системе логических уравнений:
- (¬X ∧ (¬Y ∨ (Y ∧ ¬Z))) ∨ X
- (X ∧ ¬(¬Y ∨ (Y ∧ ¬Z))) ∨ X
- X → (Y → Z)
- Таких формул в приведенном списке нет
- ¬X ∧ Y ∧ Z
Задание 3.
Найдите, сколько существует уникальных троек X,Y,Z, таких, что выполнены оба следующих условия:
А. X10+Y10+Z10≤1610
Б. X54Y+2+YZX+Y+AYAZX+Y+Z=ZYACX·Y
Подстрочным индексом обозначены основания систем счисления.
Примечание: если таких троек нет, то запишите в ответ 0.
Задание 4.
Никита забыл пароль от своей базы данных, в которой он хранил важную информацию. Он помнит, что пароль состоит из N неповторяющихся символов (N — натуральное число). Первые два символа — это латинские буквы из набора n, a, k, w, t, x; следующие N-3 символа — это цифры от 0 до 9, а последний символ — одна из букв: d, o, r.
Известно, что на ввод одного пароля Никита тратит 1 секунду независимо от его длины. Также дополнительно известно, что в худшем случае на подбор пароля у Никиты уйдёт не более 1 часа, а N<8.
Чему равно максимально возможное значение N и сколько именно секунд потребуется Никите в худшем случае при таком N?
В ответ запишите сначала N, а потом без пробелов время. Например, если N=7, а время 2500, то ответ надо записать 72500.
Задание 5.
В текстовом файле 9_9.txt находится строка, состоящая из символов A,B,C.
Определите наибольшую длину подстроки, составленной из последовательности 5-символьных блоков структуры 2-1-2, получаемых циклическим сдвигом. То есть возможные варианты исчерпываются такими (AABCC, CCABB, BBCAA), которые при склейке образуют цепочку вида AABCCCCABBBBCAAAAB… . Искомая подстрока может начинаться и заканчиваться с любой позиции внутри этой структуры.
Примеры:
Строка CCCC – подходит, так как является подстрокой AABCC+CCABB;
Строка CAB – подходит, так как является подстрокой CCABB;
Строка CCCABBB – подходит, так как это подстрока AABCC+CCABB+BBCAA;
Строка AABCCCCABBBBCAA – подходит так как является полным циклом из 15 символов;
Строки AC, AAAAA, BAC – не подходят.
Задание 6.
Минимальный информационный объем, с которым может манипулировать компьютер Бельчонка, равен 16 битам. Бельчонок хочет понять, какой информационный объём будет у сообщения: “Привет, я бельчонок”, если алфавит состоит из 33 букв русского алфавита в верхнем и нижнем регистре т.е. всего 66 букв, а также трех специальных символов (,.;).
Напишите информационный объём этого сообщения в байтах с учётом того, что на каждый символ выделяется целое минимально возможное количество байт.
Задание 7.
Имена файлов можно задавать с помощью масок:
Символ ? означает ровно один произвольный символ;
Символ * означает любую последовательность произвольных символов произвольной длины (в том числе пустую).
Полное имя файла состоит из имени и расширения, разделенных точкой, и содержит только строчные латинские буквы и точку. Ниже приведены 6 масок:
????.*?
p*?*?*.p?*
*og.*a?
?p*?*?og.???
*p*???*.*s
pr??.?a?Известно, что существует ровно одно имя файла, которое одновременно удовлетворяет пяти из шести представленных масок (одна маска является лишней).
Определите и запишите это имя файла.
Задание 8.
Найдите наименьшее простое число P, которое удовлетворяет всем следующим условиям:
А. P>1234567892026;
Б. Сумма цифр числа P – простое число;
В. Сумма четных цифр числа строго больше суммы нечетных цифр.
Например, число 122 удовлетворяет пунктам Б и В, так как 1+2+2=5, а 5 – простое число, и 1<2+2.
Задание 9.
Бельчонок никогда ранее не работал с системами счисления, основание которых больше 36, но недавно его друг сказал, что для работы с ними можно принять, например, такое соглашение:
Буквы A-Z=0..25, a-z=26..51, 0-9=52..61, и наконец _ и - для значений 62 и 63.
Для закрепления этой информации он дал ему такой пример (здесь + обозначает стандартную операцию сложения):
UeeZaef64 + MTdUUXe64
Найдите значение этого выражения. Ответ запишите в 36-ичной системе счисления (используя стандартные обозначения: цифры 0-9 для значений 0-9 и заглавные латинские буквы A-Z для значений 10-35).
Задание 10.
Напишите натуральные значения a,b,c такие, чтобы данное логическое выражение:
соответствовало следующей таблице при заданных значениях:
| X | Y | F1 | F2 | F3 | f(X, Y, F1, F2, F3) |
|---|---|---|---|---|---|
| 1 | 3 | True | False | True | True |
| 2 | 5 | False | False | True | True |
| 3 | 6 | False | True | False | True |
и сумма a+b+c при этом имела бы наименьшее значение.