Прочие прототипы —Каталог задач по ЕГЭ - Информатика

Тема 11. Количество информации и комбинаторика

11.04 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела количество информации и комбинаторика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#63193

Система мониторинга формирует и отправляет специальные сообщения, в которые могут входить только следующие символы: латинские буквы ( $26$ заглавных и $26$ строчных), цифры от $0$ до $9$ , пробел. Количество символов в сообщении может быть любым.

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

Система отправила $7$ сообщений: два сообщения по $30$ символов каждое, два сообщения по $50$ символов и три сообщения по $70$ символов. При этом всего было передано $400$ байт.

Сколько байтов содержит заголовок сообщения? В ответе запишите только целое число — количество байтов.

Показать ответ и решение

Начнем с подсчета количество всех символов:

$26 + 26 + 10 + 1 = 63$ символа. Значит вес $1$ символа будет $i 2 = 63$ .

$i = 6$ бит на $1$ символ.

Примем, что $m −$ вес заголовка, а $I−$ вес всех сообщений.

$I1−$ вес первого одного сообщения.

$I2−$ вес второго одного сообщения.

$I3−$ вес третьего одного сообщения.

Тогда получаем:

(| 30 ⋅ 6 ||| I1 = -----≈ 23 байта. ||| 8 |||{ 50 ⋅ 6 | I2 = 8 ≈ 38 байт. |||| ||| ||( 70 ⋅ 6 I3 = 8 ≈ 53 байта.

Общая формула будет выглядеть следующим образом:

$I = 2 ⋅ (I1 + m ) + 2 ⋅ (I2 + m ) + 3 ⋅ (I3 + m ) = 400$

Отсюда выразим $m$ :

$m = 400-−--2 ⋅ 23-−-2-⋅ 38-−-3-⋅ 53 = 119-= 17 7 7$ байт.

Ответ: 17

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#43649

В велокроссе участвуют $37$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли $16$ велосипедиста? (Ответ дайте в Байтах)

Показать ответ и решение

Всего участвует $37$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $6$ бит (поскольку $25 < 37 < 26$ . На информацию о $16$ велосипедистах потребуется $16 ⋅6$ бит, или же $12$ байт.

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 3#43648

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

Показать ответ и решение

Всего участвует $167$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $8$ бит (поскольку $27 < 167 < 28$ . На информацию о $104$ пловцах потребуется $104 ⋅8 = 832$ бит.

Ответ: 832

Ошибка.
Попробуйте повторить позже

Задача 4#39289

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

Показать ответ и решение

Всего участвует $193$ спортсмена, значит, на информацию об одном спортсмене понадобится выделить $8$ бит (поскольку $193 < 28$ . На информацию о $100$ велосипедистах потребуется $100⋅8 = 800$ бит, или же $100$ байт.

Ответ: 100

Ошибка.
Попробуйте повторить позже

Задача 5#39288

В написании пробника участвуют $3000$ марафонцев. Куратор фиксирует прохождение каждым из марафонцев регистрации на написание пробника, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого марафонца. Какой объём памяти потребуется выделить куратору на своем ноутбуке, чтобы зарегистрировать всех марафонцев на написание пробника? Ответ дайте в Кбайтах. В ответ запишите только целую часть числа.

Показать ответ и решение

Так как с помощью $i$ бит можно закодировать $N = 2i$ чисел, то для регистрации $N = 3000$ номеров потребуется $12$ бит, так как $211 = 2048 < 3000 ≤ 212 = 4096$ . Значит, для регистрации всех марафонцев куратору потребуется выделить $3000⋅12 = 36000$ бит, то есть $36000∕8 = 4500$ байт, то есть $4500∕1024 ≈ 4.4$ Кбайт памяти. В ответ записываем число $4$ .

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 6#37488

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

Показать ответ и решение

Всего участвует $617$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $10$ бит (поскольку $29 < 617 < 210$ . На информацию о $212$ велосипедистах потребуется $212 ⋅10$ бит, или же $265$ байт.

Ответ: 265

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#37487

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

Показать ответ и решение

Всего участвовало $98$ спортсменов. $26 < 98 < 27$ , значит, чтобы записать одного участника, хватит $7$ бит. Финиш прошли $92$ велосипедиста, то есть было потрачено $7 ⋅92 = 644$ бит.

Ответ: 644

Ошибка.
Попробуйте повторить позже

Задача 8#30255

Праздник, на котором было $19$ человек и еще Петя ( $20$ -й), подходит к концу, поэтому ребятам пришло время расходиться. Все начали прощаться друг с другом. Петя счёл интересным кодировать каждое прощание. Всего он определил три вида прощаний: мальчик с мальчиком, девочка с девочкой, девочка с мальчиком. Определите, сколько байт потребовалось Пете для кодирования этой информации. Каждое прощание кодируется минимально возможным количеством бит.

Показать ответ и решение

Есть всего три вида прощаний, поэтому для кодирования каждого из них нужно минимум 2 бит, так как $21 < 3 <= 22$ . Приглашено 19 человек. Петя является 20-тым. Тогда всего прощаний между 20 людьми равно количеству ребер в полном графе на 20 вершинах, то есть равно $20⋅19∕2 = 190$ Значит, на все кодирование всех прощаний требуется $190⋅2 = 380$ бит $= 48$ байт.

Ответ: 48

Ошибка.
Попробуйте повторить позже

Задача 9#30254

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

Петя попросил одну часть ребят придумать первые $4$ символа пароля, состоящие только из последних $15$ букв латинского алфавита в двух регистрах. Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

Другую часть ребят Петя попросил придумать следующие $6$ цифр пароля, используя десятичные цифры и символы $∗,&,%, @$ . Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

Для ещё большей надёжности Петя придумал последние два символа пароля сам. Для этого он использовал все $26$ букв латинского алфавита в нижнем регистре. Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

В итоге получился $12$ -символьный пароль, состоящий из трёх разных частей. Но Пете он не понравился, поэтому совместными усилиями таким же способом был получен новый пароль. А потом ещё. И ещё немного. После шести попыток Пете понравился результат и пароль был наконец установлен, после чего ребята отправились есть праздничный торт.

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

Показать ответ и решение

Первая часть пароля. Используется 15 букв в двух регистрах, то есть 30 символов. Для кодирования такого количества необходимо минимум 5 бит на каждый символ, так как $24 < 30 <= 25$ . Тогда на 4 символа нужно $5 ⋅4 = 20$ бит $= 20∕8 = 3$ байт.

Вторая часть пароля. Используется 10 цифр и $∗,&, %,@$ , то есть 14 символов. Для кодирования такого количества необходимо минимум 4 бит на каждый символ, так как $23 < 14 <= 24$ . Тогда на 6 символов нужно $6 ⋅4 = 24$ бит $= 24∕8 = 3$ байт.

Третья часть пароля. Используется 26 букв в одном регистре, то есть 26 символов. Для кодирования такого количества необходимо минимум 5 бит на каждый символ, так как $24 < 26 <= 25$ . Тогда на 2 символа нужно $5 ⋅2 = 10$ бит $= 10∕8 = 2$ байт.

Следовательно, на один пароль потребуется $3+ 3+ 2 = 8$ байт. Тогда на 6 паролей необходимо $6⋅8 = 48$ байт.

Ответ: 48

Ошибка.
Попробуйте повторить позже

Задача 10#30253

Другим ребятам на празднике понравилась игра Пети и Вани и они решили поиграть тоже. Петя изменил правила. Теперь изменить количество камней в куче стало возможно десятью способами, при этом игра состояла из шести ходов. Петя записывал дополнительные сведения о каждой игре, но забыл, сколько памяти для этого отводилось. Всего было проведено 20 игр, на которые было потрачено 420 байт (игры кодировались вместе с дополнительными сведениями).

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

Показать ответ и решение

Существует 10 способов сделать ход. $23 < 10 <= 24$ , поэтому для кодирования каждого хода потребуется минимум 4 бит. Так как игра состоит из 6 ходов, то для кодирования данных об одной игре потребуется $6⋅4 = 24$ бит $= 24∕8 = 3$ байт. На 20 игр с дополнительными сведениями было отведено 420 байт. Значит, на одну игру с дополнительными сведениями требуется $420∕20 = 21$ байт. Тогда для кодирования дополнительных данных об одной игре потребуется $21− 3 = 18$ байт.

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 11#30252

Наконец на день рождения пришёл Ваня. Он опоздал и был весьма удивлён выбору скучной игры с придумыванием слов, поэтому предложил другой вариант.

Ваня захватил с собой камни (обычное дело), поэтому начал с именинником играть в следующую игру. За ход можно изменить количество камней в куче одним из трёх способов. Одна игра состоит из восьми ходов. Конечно, Петя решил закодировать партии этой увлекательной игры. Каждый ход (то есть один из способов изменения количества камней в куче) кодируется минимально возможным количеством бит. Каждая игра кодируется минимально возможным количеством байт. Петя решил добавить дополнительные сведения к каждой игре, на которые уходит по 1 байт. Сколько байт потребуется для кодирования трёх игр с дополнительными сведениями о них?

Показать ответ и решение

Существует всего 3 способа сделать ход. $21 < 3 <= 22$ , поэтому для кодирования каждого хода потребуется минимум 2 бит. Так как игра состоит из 8 ходов, то для кодирования данных об одной игре потребуется $8⋅2 = 16$ бит $= 16∕8 = 2$ байт. Каждая игра с дополнительными сведениями занимает $2 + 1 = 3$ байт. Тогда для трёх игр потребуется $3⋅3 = 9$ байт.

Ответ: 9

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#30251

Ребята на дне рождения решили поиграть в игру. Все должны были придумать как можно больше последовательностей длиной $9$ символов из букв $П, Е, Т, Я$ и цифр $1,8$ . Ребята написали $40$ последовательностей. Петя решил их все закодировать. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждая последовательность — одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, который потребуется Пете.

Показать ответ и решение

Всего можно использовать $6$ символов, для кодирования каждого нужно минимум $3$ бит, так как $22 < 6 <= 23.$ Тогда для $9$ символов потребуется $9⋅3 = 27$ бит $= 27∕8 = 4$ байт. Значит, для $40$ таких последовательностей потребуется $40 ⋅4 = 160$ байт.

Ответ: 160

Ошибка.
Попробуйте повторить позже

Задача 13#30250

Петя пригласил на день рождения 19 человек. Для каждого он придумал уникальный код, который записал с помощью минимального количества бит. Каков информационный объем в байтах сообщения о кодах первых 11 человек, пришедших на праздник?

Показать ответ и решение

На 19 человек нужно минимум 5 бит для каждого кода, так как $24 < 19 <= 25.$ Тогда для первых 11 человек потребуется $11 ⋅5 = 55$ бит $= 55∕8 = 7$ байт.

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 14#27454

В некоторой базе данных хранятся записи, содержащие информацию о некоторых датах. Каждая запись содержит три поля: номер года (число от $1$ до $2100$ ), номер месяца (число от $1$ до $12$ ) и номер дня в месяце (число от $1$ до $30$ ). Каждое поле записывается отдельно от других полей с использованием минимально возможного количества бит. Определите минимальное количество бит, необходимое для кодирования одной записи. Ответ дайте в битах.

Показать ответ и решение

Так как $2100 ≤ 212$ , то номер года кодируется с помощью $12$ бит.
Так как $12 ≤ 24$ , то номер месяца кодируется с помощью $4$ бит.
Так как $30 ≤ 25$ , то номер дня в месяце кодируется с помощью $5$ бит.
Тогда минимальное количество бит, необходимое для кодирования одной записи, равно $12+ 4 + 5 = 21$

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 15#24565

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

Показать ответ и решение

Так как с помощью $i$ бит можно закодировать $N = 2i$ чисел, то для регистрации $N = 2000$ номеров потребуется $11$ бит, так как $210 = 1024 < 2000 ≤ 2048 = 211$ . Значит, для регистрации всех марафонцев куратору потребуется выделить $2000⋅11 = 22000$ бит, то есть $22000∕8 = 2750$ байт памяти.

Ответ: 2750

Ошибка.
Попробуйте повторить позже

Задача 16#23995

Каждая клетка поля $8 × 8$ кодируется минимально возможным и одинаковым количеством бит. Решение задачи о прохождении «конем» поля записывается последовательностью кодов посещенных клеток. Каков объем информации (в байтах) после $11$ сделанных ходов? (Запись решения начинается с начальной позиции коня).

Показать ответ и решение

Найдем сколько информации несет 1 клетка: $2i = 8⋅8 = 64 => i = 6$ бит.

Сделаем 11 ходов: $6⋅11 = 66$ бит.

Нам нужно в байтах, поэтому переводим: $66-≈ 9 8$ байт.

Ответ: 9

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#23498

Досье на преступников занимают $45$ Мбайт и каждое из них имеет объем $12$ страниц ( $48$ строк по $64$ символа в каждой, $1$ символ занимает $8$ бит). Чему равно число хранимых досье?

Показать ответ и решение

Один символ занимает $8$ бит, то есть $1$ байт.

Одно досье занимает: $1⋅64⋅48 ⋅12$ байт.

Общее количество: $45$ Мбайт $= 45⋅1024⋅1024$ байт.

Число хранимых досье: $45⋅1024⋅1024 1-⋅64⋅48⋅12--= 1280$ .

Ответ: 1280

Ошибка.
Попробуйте повторить позже

Задача 18#7395

Вступая в марафон Школково по информатике, вы становитесь клоном АР. Каждому клону присваивается уникальный номер и два счётчика: кол-во пробников, которые клон закрабил, и кол-во пробников, которые клон уничтожил. В системе произошёл сбой и АР потерял информацию о том, сколько максимум клонов он может держать в своей голове. АР помнит, что для подсчёта количества используются числа от 0 до 888 включительно. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Вся информация на чипе занимает минимальное целое число байт. Также у него остался доступ к базе прошлого года весом 150 КБайт с 7680 клонами. Помогите вспомнить АР потерянную информацию. В ответе запишите максимальное количество бит, которое выделено для хранения личного кода клона АР.

Показать ответ и решение

Чтобы закодировать два счётчика от 0 до 888, потребуется не менее $10 ⋅ 2 = 20$ бит (умножаем на 2, потому что это два отдельных блока), так как $29 = 512 < 889 < 210 = 1024$ .

Вся информация на чипе занимает минимальное целое число байт. Тогда вся информация об одном клоне АР занимает $150⋅1024- 7680 = 20$ байт.

Пусть i – количество бит, которое выделено для хранения личного кода клона АР. Тогда $20+i 8 ≤ 20$ , $i = 140$ бит.

Ответ: 140

Ошибка.
Попробуйте повторить позже

Задача 19#7394

Вступая в марафон Школково по информатике, вы становитесь клоном АР. Каждому клону присваивается уникальный номер и два счётчика: кол-во пробников, которые клон закрабил, и кол-во пробников, которые клон уничтожил. Для номера используются числа $0 − 4095$ . Для подсчёта количества используются числа от $0$ до $4378$ включительно. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Вся информация на чипе занимает минимальное целое число байт. В марафоне $6144$ клона. Сколько Кбайт памяти необходимо выделить АР в своей голове, чтобы удержать всю информацию о своих клонах?

Ответ округлите в большую сторону.

Показать ответ и решение

Чтобы закодировать целое число от 0 до 4095 потребуется минимально 12 бит, так как $212 = 4096$ .

Чтобы закодировать два счётчика от 0 до 4378, потребуется не менее $13 ⋅ 2 = 26$ бит (умножаем на 2, потому что это два отдельных блока), так как $212 = 4096 < 4379 < 213 = 8192.$

Вся информация на чипе занимает минимальное целое число байт. Тогда вся информация об одном клоне АР занимает $12+26 8 = 5$ байт. Чтобы удержать в голове информацию о 6144 клонах, АР необходимо выделить $6114042⋅54-= 30$ Кбайт.

Ответ: 30

Ошибка.
Попробуйте повторить позже

Задача 20#7393

Вступая в марафон Школково по информатике, вы становитесь клоном АР. Каждому клону присваивается уникальный номер и два счётчика: кол-во пробников, которые клон закрабил, и кол-во пробников, которые клон уничтожил. Для номера используются числа от $0$ до $200000$ включительно. Для подсчёта количества на одном счётчике используются числа от $0$ до $1336$ включительно. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Вся информация на чипе занимает минимальное целое число байт. В марафоне $768$ клонов. Сколько Кбайт памяти необходимо выделить АР в своей голове, чтобы удержать всю информацию о своих клонах?

Ответ округлите до целых по правилам математики.

Показать ответ и решение

Чтобы закодировать целое число от 0 до 200000 потребуется минимально 18 бит, так как $217 = 131072 < 200001 < 218 = 262144$ .

Чтобы закодировать два счётчика от 0 до 1336, потребуется не менее $11 ⋅ 2 = 22$ бит (умножаем на 2, потому что это два отдельных блока), так как $10 11 2 = 1024 < 1337 < 2 = 2048$ .

Вся информация на чипе занимает минимальное целое число байт. Тогда вся информация об одном клоне АР занимает $18+822= 5$ байт. Чтобы удержать в голове информацию о $768$ клонах, АР необходимо выделить $768⋅5-= 3, 75 1024$ Кбайт. Округляем до $4$ по правилам математики.

Ответ: 4

Предыдущий раздел

Следующий раздел