Статья Автор: Лебедев Дмитрий

Разбор варианта Статграда (2024.10.24). Часть 1 (5.6.7.11.13. 14.15)

Первая часть разбора заданий варианта Статграда от 24 октября 2024.
В разбор включены "простые" задания, условия которых "отличаются от стандартных"
Предлагаются конкретные решения конкретных заданий "средний" сложности.
Разбираются следующие задания 
Задание 5 Задание 6 Задание 7 Задание 11 
Задание 13 Задание 14 Задание 15  
Разбор не является пособием по решению заданий. Общие подходы можно найти в других разделах  Учебника.
Вторая часть разбора  

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Если число N чётное, то к двоичной записи слева дописываются цифры 11.
    В противном случае (число N нечётное) к двоичной записи слева дописывается цифра 1, а справа – цифры 10.
3. Результатом работы алгоритма становится десятичная запись полученного числа R.
Укажите максимальное число R, которое может быть результатом работы данного алгоритма,
при условии, что N принадлежит отрезку [234 567 890; 567 891 234].

Задание несложное, поскольку несложно понять, что
  • при нечётном N к двоичной записи дописывается три знака,а при чётном только два.
    Следовательное нечётное N "выгоднее" чётного.
  • для "чётных" N преобразование "одинаковое" и сохраняет монотонность
    для "нечётных" аналогично
это дает понимание, что ответом будет R, полученное  от максимального нечётного N
Напишем функцию, получающую двоичное значение R от заданного N (получение двоичного R удобнее для проверки на примерах условия)
(достаточно было написать только нечётную ветку)


Задание 6 (ссылка на задание)

Черепаха выполнила следующую программу:

Повтори 2 [Вперёд 23 Направо 90 Вперёд 10 Направо 90]
Вперёд 3 Налево 90 Вперёд 12 Направо 90
Повтори 2 [Вперёд 9 Направо 90 Вперёд 32 Направо 90]

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

Для решения этого задания применение компьютера совсем не обязательно. Можно нарисовать чертёж на листке и провести несложные вычисления. Рассмотрим задание подробнее и для иллюстрации будем использовать компьютер.

Воспроизведем действия Черепахи можно с помощью модуля Turtle.
Программу лучше запускать частями (в примере части указаны строчками), переносить чертеж на бумагу и подписывать длины отрезков.
Если запустить следующий, то "внизу тетради" можно увидеть весь чертёж (для удобства,  значения длин отрезков увеличили в 10 раз (как бы от см перешли к мм))

Будет получен чертеж, состоящий из двух пресекающихся прямоугольников.
Для каждого (из 5) прямоугольников несложно найти стороны и площадь
код рисунок
Повтори 2 [Вперёд 23 Направо 90 Вперёд 10 Направо 90]
Повтори 2 [Вперёд 23 Направо 90 Вперёд 10 Направо 90]
Вперёд 3 Налево 90 Вперёд 12 Направо 90
Повтори 2 [Вперёд 23 Направо 90 Вперёд 10 Направо 90]
Вперёд 3 Налево 90 Вперёд 12 Направо 90
Повтори 2 [Вперёд 9 Направо 90 Вперёд 32 Направо 90]
Ответом будет наибольшая площадь (110).
Поэтапное рисование Черепашкой полезно, так как упрощает определение сторон прямоугольников
(разбиение программы на этапы практически есть в задании)

Задание 7 (ссылка на задание)
Камера дорожного наблюдения делает цветные фотографии с разрешением 1024×768 пикселей, используя палитру из 4096 цветов.
Снимки сохраняются в памяти камеры, группируются в пакеты по 100 штук и отправляются в центр обработки по каналу связи с пропускной способностью 128 Кбайт/сек.
На сколько процентов необходимо сжать изображения, чтобы передавать один пакет за 6 минут?
Заголовки и другую служебную информацию не учитывать.
В ответе запишите число – округлённый до целого процент сжатия. Знак процента писать не нужно.
Задание несложное, можно решить с помощью калькулятора, но можно написать программу для поиска ответа .
Обратим внимание на то, что количество процентов надо округлить до целого, следовательно ответ нельзя проверять "напрямую" (подстановкой в формулу), поскольку значение времени может быть больше ограничения.
Например, если в пакете было бы 150 снимков, то ответом было бы число 73% (точное значение 220/3 ), а для него время передачи было бы больше 6 минут


Задание 11 (ссылка на задание)
Каждое изделие, изготовленное на предприятии, получает уникальный код, состоящий из 30 символов.
Каждый символ кода может быть латинской буквой (заглавной или строчной), десятичной цифрой или специальным символом из особого технического набора.
В базе данных хранится таблица, содержащая все уже использованные коды.
При этом используется посимвольное кодирование, каждый символ кодируется одинаковым минимально возможным числом бит, а для хранения каждого кода в целом отводится одинаковое минимально возможное число байт.
Известно, что для хранения списка из 4700 кодов выделено не более 180 Кбайт.
Какое наибольшее количество специальных символов может входить в особый технический набор?
Задание сформулировано в "поисковой форме", его можно решить без использования программ. 
Приведем два фрагмента  кода:
  • "программное решение" поиска ответа  
  • решение вычислениями 
Второе решение явно лучше, но  требует определенной "уверенности" 



Задание 13 (ссылка на задание)

Узел с IP-адресом 121.96.174.205 принадлежит сети, в которой

  • 10 IP-адресов, двоичная запись которых содержит ровно 12 единиц.

Сколько единиц содержится в двоичной записи маски этой сети?

Задание дано в "нестандартной" формулировке. Разберем ситуацию подробно


Пусть маска имеет вид m-s, то есть содержит m единиц и k нулей. 
Пусть X - количество единиц в IP адресе.  X = am + bs , где 
  • am - кол-во единиц на первых m местах и это число одинаково для всех адресов сети
    (и это число не может быть больше x)  
  • bs - кол-во единиц на последних k местах и оно должно быть равно X - am
Количество двоичных последовательностей длины n, имеющих ровно k единиц равно \(C_n^k\) - числу сочетаний k предметов по n местам
В условиях задания получаем, что \(C_n^k = 10\) . Достаточно очевидно, что этому удовлетворяют только два набора (n=10, k=1) и (n=5, k=2)
Осталось сделать проверку и убедиться, что подходит только вариант (n=10,k=1)


Запустив программу получаем, что
  • при маске 22-10 в "базовой" части 11 единиц и 12 единиц будет в 10 адресах из 1024 
  • при маске 27-5 в базовой части было бы 14 единиц и 16 единиц могло быть в 10 адресах из 32

Задание 14 (ссылка на задание)

В числах F29x8EAD637 и BAxDE0C1B37 переменная x обозначает некоторую цифру из алфавита системы счисления с основанием 37. Определите наибольшее значение x, при котором произведение приведённых чисел кратно 36.
В ответе запишите значение числа 1x237 в десятичной системе счисления.

Обычно задания этого типа были связаны с делимостью суммы, а в этом задание нужна делимость произведения.
Вроде "усложнение" (тем более, что делитель 36 не простое число). Однако, если вспомнить правила модульной арифметики, то найдется "простое решение".
 

Некоторые правила модульной арифметики (записанные с помощью операторов программирования wink)
  • число A делиться на число P тогда и только тогда, когда  истинно A % P == 0
  • (A + B) % P = ((A % P ) + (B % P)) % P ( остаток суммы равен остатку от суммы остатков)
  • (A * B) % P = ((A % P ) * (B % P))  % P  ( остаток произведения равен остатку от произведения остатков)
  • (Ak) % P = (A % P)k % P  ( остаток степени равен остатку от степени остатка)
Вспомним про развернутую форму записи числа  ( \(\widehat{a_n\dots a_0} = \sum_0^n a_i\cdot 10^i \)) и то, что 10 % (10-1) = 1 в системе счисления с любым основанием.
Тогда для чисел F29x8EAD637  и BAxDE0C1B37 будет несложно найти остатки по модулю 36
  • \(F29x8EAD6_{37}\ \%\ 36 = ((F+2+9+8+E+A+D+6)\ \%\ 36\ +\ x)\ \%\ 36 = ((15+2+9+8+13+10+14+6)\%36+x)\%36 = (x +5)\%36\)
  • \(BAxDE0C1B_{37}\ \%\ 36 = ((B+A+D+E+C+1+B)\ \%\ 36\ +\ x)\ \%\ 36 = ((11+10+13+14+12+1+11)\%36+x)\%36 = (x +0)\%36\)
Таким образом надо найти максимальное значение для x из range(37), такое, что (x+5)x % 36 == 0. Это можно сделать и без программы : x=36 => 1x237 = 372 + 6*37 + 2 = 2703
Можно ли это сделать программно. Да! Сделаем это с "пользой,  реализовав расширенную функцию int
 


С помощью несложной (и очень полезной программы)  удалось найти все возможные значения x  и определить результат  

Задание 15. (ссылка на задание)
На числовой прямой даны три отрезка: P = [3; 43], Q = [18; 91], R = [72; 115].
Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ Q) → (¬(x ∈ P) → ((¬(x ∈ R) ∧ ¬(x ∈ A)) → ¬(x ∈ Q)))
истинно (т.е. принимает значение 1) при любом значении переменной x.
Задание на систему отрезков и решать желательно путем преобразования формулы (ручным способом)
Однако, решив несколько таких заданий, можно понять, что:
  • прямая, границами отрезков, разбивается на два луча ("левый" и "правый") и несколько отрезков
    (\(\mathbb{R} = (-\infty ; 3]\cup[3;18]\cup [18;43]\cup[43;72]\cup [72;91]\cup [91;115]\cup [115;\infty) \) )
  • внутренние точки отрезков/лучей входят в ответ "целиком"
  • если в вопросе требуется найти "наименьшее значение" для длины отрезка A, то 
    • A в формуле без отрицания 
    • ответ "покрывает" систему "пустот"
  • если в вопросе требуется найти "наибольшее значения" для длины отрезка A, то
    • то в формуле A с отрицанием
    • ответ "заполняет" одну из слитных пустот
Эти наблюдения можно использовать для поиска решения

  1. В задании речь про "наименьшую" длину, значит в формуле A без отрицания
  2. Найдем все отрезки, для которых условие \(x \in A \) необходимо. Для этого в формуле ему надо задать значениу False ( условию \(x \notin A \) значение True)
  3.  Вычислим значение преобразованной формулы (x ∈ Q) → (¬(x ∈ P) → ((¬(x ∈ R) ) → ¬(x ∈ Q))) для "представителей" внутренних точек отрезков


 Из вывода программы видно, что результат False получен только для точки из отрезка [43; 72], значит A должен "накрыть" этот отрезок и длины будет 72 - 43 = 29
Решим задание путем преобразования логического уравнения (для удобства опустив знаки x ∈
  • Q → (¬P →( (¬R ∧ ¬A) → ¬Q)) = ¬Q or P or ¬(¬R and ¬A)) or ¬Q = ¬Q  or P or R or A  => A = ¬(¬Q or P or R) = Q and ¬P and ¬R  
    применив "метод отрезков" (или что-то похожее) получим для A значение [43; 72] и длину 29
Попробуйте, при тренировке, использовать оба подхода devil
 
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать