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

Разбор Статграда от 2024-12-17. Часть 1( 1, 4, 6, 7, 10, 11)

Вариант Статграда от 2024-12-17 содержит несколько задач, отличающихся нестандартной формулировкой. 
Попробуем разобрать все задания варианта.

Задание 1. 
Известно, что дорога АГ короче дороги ГД.
Определите длину дороги ЖИ.

Вопрос настораживает дополнительным условием (АГ< ГД).
Беглый взгляд на граф дает понять, что он симметричен
Вершина Ж имеет степень 3 и таких вершин всего две
Поэтому рассматриваем два варианта:
  1. Ж=П6  =>  И=П8 => K=П1 => Е=П2 => Д= П4 => Г=П9 => А=П3
    АГ=17 и ГД=18 подходит, значит ЖИ=16
  2.   Для проверки можно построить вариант два:
    Ж=П7  =>  И=П5 => K=П3 => Е=П9 => Д= П4 => Г=П2 => А=П1
    АГ=21 и ГД=15 не подходит
Конечно, при выполнении этого задания решение логично сопровождать "подписями" 

Задание 4.
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны:
И – 00010, Н – 100, Ф – 11, О – 001, Р – 0000, М – 1010, А – 011, Т – 1011, К – 010.
Укажите возможный код минимальной длины для буквы Ю. Если таких кодов несколько, укажите тот из них, который имеет наименьшее числовое значение.
Главной особенностью этого задание является "все заглавные буквы". Значит нужно оставить "окошко" для этих  букв (обозначим *)
Подсчитаем, сколько 5-ти буквенных обозначений "закрывают" известные буквы.
Для пояснения  заполним таблицу:
буква обозначение закрывают пояснение
И  00010 1  
Н 100 4 10000,10001,10010,10011
Ф 11 8 11000,11001,11010,11011,
11100,11101,11110,11111
О 001 4  
Р 0000 2  
М 1010 2  
А 011 4  
Т 1011 2  
К 010 4  
всего   31  
 
Значит для продолжения есть только ОДНО пятибуквенное значение...
Легко видеть, что это 00011, которое требуется "раздвоить" на 000110 и 000111
Для Ю выберем наименьшее 000110, а  для "окошка"  000111
Такой способ не требует рисования  дерева, что экономит время

Задание 7
Фотографию отсканировали с разрешением 150 dpi и сжали изображение на 40 %. В результате получился файл размером 6 Мбайт.
Затем ту же фотографию отсканировали в том же цветовом режиме с разрешением 300 dpi.
На сколько процентов необходимо сжать полученное изображение, чтобы размер файла составил 12 Мбайт?
Заголовки и другую служебную информацию не учитывать.
В ответе запишите число – округлённый до целого процент сжатия. Знак процента писать не нужно.
Задание можно решать разными способами. Приведем один из них.
  •  Если разрешение увеличить в два раза, то "объем" изображения увеличиться в четыре раза
    (сторону квадрата увеличили в два раза, площадь увеличилась в четыре раза)
  • Значит сжатый на 40%  процентов файл изображения занимал бы 24 Мбайта (4*6)
  • Сжатие на 40% это умножение начального размера на 0,6, а надо ещё уменьшить в два раза (2 = 24/2)
    Значит умножать надо на 0,3 (0,6/2=0,3)
  • Умножение на 0,3 означает сжатие на 70% (100 -0,3*100 = 70)

Задание 11
Предприятие выпускает партии изделий. Каждая партия получает уникальный код, состоящий из 19 заглавных латинских букв.
Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии.
Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию.
Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется минимально возможным количеством битов. Номер изделия записывается как целое число, для записи каждого номера используется одинаковое минимально возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов.
Для записи дополнительной информации о каждом изделии требуется 40 байт.
Известно, что для хранения информации обо всех изделиях одной партии используется не более 20 Кбайт.
Какое наибольшее количество изделий может быть в партии?
Задание поискового типа, причем от искомого значения зависят несколько параметров.
Пусть N -количество изделий в партии (N - искомый параметр). Тогда:
  • буквенная часть кода кодируется 19*5 бит = 95 битами, а числовая округлением "вверх" log2(N) 
  • полученное число округляется до целого числа байт и увеличивается на 40 (пусть это X)
  • X  умножается на N и сравнивается с 20 Кбайт
 Как это решать? 
  • Можно написать программу
  • Можно сделать прикидку, понимая, что
    • 95 + log2(N) >=96, значит X >= 52
    • 20*1024/52 < 394, следовательно N не более 400 (и наверное больше 256), а тогда "округленный" log2(N) равен 9 и
    • 95+9=104 бит = 13 байт, следовательно X = 53, следовательно 20*1024/53 = 386,415
Получаем N = 386 
 

Задание 10
Определите, сколько раз в файле, содержащем книгу братьев Стругацких «Понедельник начинается в субботу»,
встречается сочетание букв «от» в составе других слов, но не как отдельное слово.
Строчные и заглавные буквы в этом задании не различаются.
Задание выполняется с помощью текстового редактора WORD.
Выполнение задания может содержать следующие шаги:
  1. Открытие файла
  2. Замена "от" в режиме отдельного слова на любой симлов( например на 9) - 196 замен (значение не важно)
  3. Замена "от" на любой специальный/отсутствующий символ - 2227 замен
Желательно выполнить задание двумя различными способами
 

Задание 6

В начальный момент на поле находятся две Черепахи.
Первая Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат).
Вторая Черепаха находится в неизвестной точке поля и направлена вправо (вдоль положительного направления оси абсцисс).
Каждая Черепаха выполнила следующую программу:
Повтори 2 [Вперёд 15 Направо 90 Вперёд 8 Направо 90]
Определите максимально возможное количество точек с целочисленными координатами,
которые могут оказаться внутри пересечения фигур, нарисованных двумя Черепахами. Точки, находящиеся на линиях, не учитывать.

Новая формулировка задания - сразу две черепахи:

  • одна рисует "стандартный" прямоугольник
  • другая рисует такой же, но с поворотом на 90 градусов и из произвольной точки
Максимальное пересечение этих прямоугольников квадрат, со стороной равной ширине прямоугольника.
Вроде можно писатьт ответ = (b - 1)2, где b - ширина прямоугольника.но .... не слишком ли ПРОСТО?
Этот ответ "легко" получается, если рисовать на бумаге в клетку или в Кумире
Напишем "полную" программу для черепашки на Python

Запустив программу с указанными параметрами ( ms = 12; x = - 60, y =120) получим ответ 49 точек (8-1)2, 
но запустив с (ms = 14; x = - 60, y =120) увидим 56 точек ( на одну линию точек больше). Почему?
Ответ несложный, поскольку это ответ на вопрос:
Сколько целочисленных точек на интервале (x; y)  ?
  • будем считать что, x,y - положительные и больше 1 (иначе добавим к ним необходимое)
  • найдем количество целых от 1до y:
    • если у не целое, то [y] 
    • иначе y - 1  (или [y] - 1)
  • найдем количество целых от 1до x включительно: [x]
  • ответ будет равен:
    •  [y] - [x], если y  не целочисленное
    • [y]-1-[x], если y  целочисленное 
Таким образом, правильным ответом будет b*(b-1), где b - меньшая сторона (ширина)

Надо ли писать на экзамене программу? Ответ НЕТ, но надо
  • внимательно записать координаты вершин общего прямоугольника/ квадрата 
  • определить возможное число внутренних точек по ширине и длине 
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать