На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Г или через пункт Е, но не через оба этих пункта?
Спрятать решение
Решение.
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения найдём последовательно количество путей до каждого из городов, проходящих через пункт Г, но не проходящих через пункт Е:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3
Д = Г = 3 (Б не учитываем, поскольку путь должен проходить через Г)
Ж = Д = 3
И = Г = 3
К = И = 3
Л = Д + Ж = 6
М = К + Л = 9
Н = Ж + Л = 9
П = Н + М + Л = 24
Теперь найдём последовательно количество путей до каждого из городов, проходящих через пункт Е, но не проходящих через пункт Г:
А = 1
Б = А = 1
Д = Б = 1
Е = Д = 1
И = Е = 1
Ж = Д = 1
К = И + Е = 2
Л = Е = 1
М = Л + К = 3
Н = Л = 1
П = Л + М + Н = 5
Таким образом, ответ — 24 + 5 = 29.
Приведем другое решение.
Найдем количество путей из пункта А в пункт П, проходящих через Г, но не через Е. Оно равно произведению количества путей из пункта А в пункт Г и количества путей из пункта Г в пункт П, не проходящих через пункт Е.
Найдем количество путей из пункта А в пункт Г:
А = 1
Б = А = 1
В = А = 1
Г = А + Б + В = 3.
Найдем количество путей из пункта Г в пункт П, не проходящих через Е (при этом Г — исходный пункт):
Г = 1
Д = Г = 1
Ж = Д = 1
И = Г = 1
К = И = 1
Л = Д + Ж = 2
М = К + Л = 3
Н = Ж + Л = 3
П = Н + М + Л = 8.
Тогда количество путей из пункта А в пункт П, проходящих через Г, но не через Е, равно 3 · 8 = 24.
Теперь найдем количество путей из пункта А в пункт П, проходящих через Е, но не проходящих через Г. Оно равно произведению количества путей из А в Е и количества путей из Е в П, при этом путь из А в Е не должен проходить через Г.
Заметим, что существует единственный путь из А в Е, не проходящий через Г. Это путь А—Б—Д—Е.
Найдем количество путей из Е в П (при этом Е — исходный пункт):
Е = 1
И = Е = 1
К = Е + И = 2
Л = Е = 1
М = К + Л = 2 + 1 = 3
Н = Л = 1
П = Л + М + Н = 1 + 3 + 1 = 5.
Тогда количество путей из пункта А в пункт П, проходящих через Е, но не через Г, равно 1 · 5 = 5.
Таким образом, ответ — 24 + 5 = 29.
Ответ: 29.
За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: повышенный.
Средний процент выполнения: 60.5%
Ответом к заданию 13 по информатике может быть цифра (число) или слово.
Разбор сложных заданий в тг-канале
Задачи для практики
Задача 1
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
| К | З | И | Ж | Е | В | Б | Д | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px(K) = Px1 (K) + Px2 (K) + Px3 (K).
Для вершины К в таблицу заносим значение PК(K) = 1.
Следующей идёт вершина З. Из этой вершины выходит путь только в одну вершину К. PЗ(K) = PК(K) = 1.
Из вершины И выходят два пути в вершины З и К.
PИ(K) = PЗ(K) + PК(K) = 1 + 1 = 2.
Из вершины Ж выходит путь только в одну вершину К.
PЖ(K) = PК(K) = 1.
Из вершины Е выходят два пути в вершины Ж и К.
PЕ(K) = PЖ(K) + PК(K) = 1 + 1 = 2.
Из вершины В выходит путь только в одну вершину З.
PВ(K) = PЗ(K) = 1.
Из вершины Б выходят пути в вершины Е, Ж и В. Следовательно, PБ(K) = PЕ(K) + PЖ(K) + PВ(K) = 2 + 1 + 1 = 4.
Из вершины Д выходит путь только в одну вершину И.
PД(K) = PИ(K) = 2.
Из вершины Г выходят два пути в вершины И и Д.
PГ(K) = PД(K) + PИ(K) = 2 + 2 = 4.
Из вершины А выходят пути в вершины Б, В, Г и Д. Следовательно, PА(K) = PБ(K) + PВ(K) + PГ(K) + PД(K) = 4 + 1 + 4 + 2 = 11.
Получим:
| К | З | И | Ж | Е | В | Б | Д | Г | А |
| 1 | 1 | 2 | 1 | 2 | 1 | 4 | 2 | 4 | 11 |
Ответ: 11
Задача 2
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, не проходящих через пункт Ж?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину Л. Затем те вершины, из которых в Л ведёт прямой путь и из которых в вершину Л можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
| Л | К | Ж | Е | И | Д | Г | В | Б | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(Л) из просматриваемой вершины x в Л, не проходящих через пункт Ж. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в Л, не проходящих через пункт Ж, будет равно сумме путей, ведущих из x1, x2, и x3 в Л.
То есть Px(Л) = Px1(Л) + Px2 (Л) + Px3(Л).
Для вершины Л в таблицу заносим значение PЛ(Л) = 1.
Следующей идёт вершина К. Из этой вершины выходит путь только в одну вершину Л. PК(Л) = PЛ(Л) = 1.
Следующей в таблице идёт вершина Ж. Так как мы ищем пути, не проходящие через эту вершину, то PЖ(Л) = 0.
Из вершины Е выходят два пути в вершины Ж и К.
PЕ(Л) = PК(Л) + PЖ(Л) = 1 + 0 = 1.
Из вершины И выходят два пути в вершины Л и Ж.
PИ(Л) = PЖ(Л) + PЛ(Л) = 0 + 1 = 1.
Из вершины Д выходит путь только в одну вершину И.
PД(Л) = PИ(Л) = 1.
Из вершины Г выходит путь только в вершину Е. PГ(Л) = PЕ(Л) = 1.
Из вершины В выходят пути в вершины Д, Ж, Е и Г. Следовательно, PВ(Л) = PД(Л) + PЖ(Л) + PЕ(Л) + PГ(Л) = 1 + 0 + 1 + 1 = 3.
Из вершины Б выходят два пути в вершины Д и В.
PБ(Л) = PД(Л) + PВ(Л) = 1 + 3 = 4.
Из вершины А выходят два пути в вершины Б и Г.
PА(Л) = PБ(Л) + PГ(Л) = 4 + 1 = 5.
Получим:
| Л | К | Ж | Е | И | Д | Г | В | Б | А |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 4 | 5 |
Ответ: 5
Задача 3
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через пункт В?
Решение
Построим граф, соответствующий данной схеме дорог. На графе будем для каждого города отмечать все возможные перемещения в города, связанные с ним исходящими дорогами.
Согласно условию задачи, требуется определить количество путей, проходящих через город В.
По графу определяем, что существует всего 10 различных путей, проходящих через город В.
Ответ: 10
Задача 4
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение
Построим таблицу. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину К. Затем те вершины, из которых в К ведёт прямой путь и из которых в вершину К можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
| К | И | Е | З | Ж | Б | В | Г | Д | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px(K) из просматриваемой вершины x в K. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px(K) = Px1(K) + Px2(K) + Px3(K).
Например, из вершины Ж выходят пути в вершины Е, З и К. Следовательно, PЖ(K) = PЕ(K) + PЗ(K) + PК(K) = 1 + 2 + 1 = 4. Получим:
| К | И | Е | З | Ж | Б | В | Г | Д | А |
| 1 | 1 | 1 | 2 | 4 | 1 | 6 | 6 | 7 | ‘20 |
Ответ: 20
Задача 5
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город В?
Решение
Заметим, что количество путей из города А в город О, проходящих через город В равно произведению количества путей из города А в город В на количество путей из города В в город О. Разобъём заданный граф на два: один из которых будет содержать только города и соответствующие дороги, ведущие из А в В, а другой — только города и соответствующие дороги из В в О.
Построим таблицу, соответствующую каждой из полученных схем. В первую строку таблицы запишем наименование всех вершин в следующем порядке.
Для первой схемы сначала запишем вершину В. Затем те вершины, из которых в В ведёт прямой путь и из которых в вершину В можно попасть только через уже просмотренные вершины. Получим:
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px (B) из просматриваемой вершины x в B. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px (B) = Px1 (B) + Px2 (B) + Px3 (B). Получим:
Количество путей из А в В равно 3.
Для определения количества путей из города В в О аналогично построим таблицу, соответствующую второй схеме.
| О | Н | М | З | И | Л | К | Д | Ж | Е | В |
| 1 | 1 | 1 | 3 | 3 | 3 | 6 | 9 | 9 | 18 | 36 |
Количество путей из В в О равно 36.
Следовательно, количество путей из города А в город О, проходящих через город В, равно 3 · 36 = 108.
Ответ: 108
Задача 6
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О?
Решение
Построим таблицу, соответствующую заданной схеме. В первую строку таблицы запишем наименование всех вершин в следующем порядке. Сначала запишем вершину О. Затем те вершины, из которых в О ведёт прямой путь и из которых в вершину О можно попасть только через уже просмотренные вершины. Далее вершины, из которых в уже просмотренные вершины ведёт прямой путь и из которых можно попасть только через уже просмотренные вершины. Получим:
| О | Н | М | З | И | Л | К | Д | Ж | Е | В | Б | Г | А |
Вторую строку таблицы заполним числами, соответствующими количеству исходящих путей Px (O) из просматриваемой вершины x в O. Если из вершины x выходит несколько путей, например, в вершины x1, x2, и x3, то количество путей, ведущих из этой вершины в К, будет равно сумме путей, ведущих из x1, x2, и x3 в К.
То есть Px (O) = Px1 (O) + Px2 (O) + Px3 (O). Получим:
| О | Н | М | З | И | Л | К | Д | Ж | Е | В | Б | Г | А |
| 1 | 1 | 1 | 3 | 3 | 3 | 6 | 9 | 9 | 18 | 36 | 45 | 54 | 135 |
Ответ: 135
Задача 7
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М?
Задача 8
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е,Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Р, не проходящих через города Б и М?
Задача 9
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Р, не проходящих через города Е и Н?
Задача 10
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Р, проходящих через города З иМ?
Задача 11
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город Е и не проходящих через город И?
Задача 12
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, проходящих через город Д и не проходящих через город Л?
Задача 13
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, не проходящих через город В?
Задача 14
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, не проходящих через город Д?
Задача 15
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город О, не проходящих через город Д?
Задача 16
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Е?
Задача 17
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Б?
Задача 18
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е,Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Д?
Задача 19
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Задача 20
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Рекомендуемые курсы подготовки
Тип 1 № 26975 
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и В на схеме. В ответ запишите без разделителей сначала номер пункта Б, потом номер пункта В.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | * | * | * | |||||
| 2 | * | * | ||||||
| 3 | * | * | * | |||||
| 4 | * | * | * | |||||
| 5 | * | * | * | |||||
| 6 | * | * | * | |||||
| 7 | * | * | ||||||
| 8 | * | * | * |
2. Тип 2 № 15814
Логическая функция F задаётся выражением (x ≡ ( w ∨ y)) ∨ ((w → z ) ∧ (y → w)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| ??? | ??? | ??? | ??? | F |
| 1 | 1 | 0 | ||
| 1 | 0 | |||
| 1 | 1 | 0 |
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 2 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
3. Тип 3 № 37507
В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
3.xlsx
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. занесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.
| ID операции | Дата | ID магазина | Артикул | Тип операции | Количество упаковок, шт. |
Цена, руб./шт. |
Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.
| Артикул | Отдел | Наименование | Ед. изм. | Количество в упаковке |
Поставщик |
Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.
На рисунке приведена схема указанной базы данных.
Используя информацию из приведённой базы данных, определите, сколько рублей выручили магазины Октябрьского района от продажи риса (всех видов) за период с 1 по 10 июня включительно.
В ответе запишите только число.
4. Тип 4 № 18553
По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 101, В — 010, И — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
5. Тип 5 № 18785
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 1, а справа 0. Например, для исходного числа 1002 результатом будет являться число 11000;
б) если число нечётное, то к двоичной записи числа слева дописывается 11 и справа дописывается 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 52. В ответе запишите это число в десятичной системе счисления.
6. Тип 6 № 47248
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись
Повтори k [Команда1 Команда2 … КомандаS]
означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм:
Повтори 4 [Вперёд 10 Направо 90]
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
7. Тип 7 № 18557
Для хранения в информационной системе документы сканируются с разрешением 600 dpi и цветовой системой, содержащей 224 = 16 777 216 цветов. Методы сжатия изображений не используются. Средний размер отсканированного документа составляет 12 Мбайт. В целях экономии было решено перейти на разрешение 300 dpi и цветовую систему, содержащую 216 = 65 536 цветов. Сколько Мбайт будет составлять средний размер документа, отсканированного с изменёнными параметрами?
8. Тип 8 № 18558
Иван составляет 5-буквенные коды из букв И, В, А, Н. Буквы в коде могут повторяться, использовать все буквы не обязательно, но букву И нужно использовать хотя бы один раз. Сколько различных кодов может составить Иван?
9. Тип 9 № 35467
Электронная таблица содержит результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Определите, сколько раз за время измерений результат очередного измерения оказывался выше результата предыдущего на 2 и более градусов.
Задание 9
10. Тип 10 № 35468
Определите, сколько раз в тексте произведения А. С. Пушкина «Дубровский» встречается существительное «ключ» в любом числе и падеже.
Задание 10
11. Тип 11 № 18819
Сотрудникам компании выдают электронную карту, на которой записаны их личный код, номер подразделения (целое число от 1 до 1200) и дополнительная информация. Личный код содержит 17 символов и может включать латинские буквы из 26-символьного латинского алфавита (заглавные и строчные буквы различаются), десятичные цифры и специальные знаки из набора @#$%^&*(). Для хранения кода используется посимвольное кодирование, все символы кодируются одинаковым минимально возможным количеством битов, для записи кода отводится минимально возможное целое число байтов. Номер подразделения кодируется отдельно и занимает минимально возможное целое число байтов. Известно, что на карте хранится всего 48 байтов данных. Сколько байтов занимает дополнительная информация?
12. Тип 12 № 16443
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 84 единиц?
НАЧАЛО
ПОКА нашлось (11111)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
13. Тип 13 № 27300
На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, проходящих через пункт Г или через пункт Е, но не через оба этих пункта?
14. Тип 14 № 13362
Значение арифметического выражения: 125 + 253 + 59 – записали в системе счисления с основанием 5. Сколько значащих нулей содержит эта запись?
15. Тип 15 № 13745
Для какого наибольшего целого числа А формула
((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9))
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?
16. Тип 16 № 4657
Алгоритм вычисления значения функции F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = 2 * G(n–1) + 5 * n, при n >1
G(1) = 1
G(n) = F(n–1) + 2 * n, при n >1
Чему равно значение функции F(4) + G(4)?
В ответе запишите только натуральное число.
17. Тип 17 № 39763
Файл содержит последовательность неотрицательных целых чисел, не превышающих 10 000. Назовём тройкой три идущих подряд элемента последовательности. Определите количество троек чисел таких, которые могут являться сторонами остроугольного треугольника. В ответе запишите два числа: сначала количество найденных троек, а затем — максимальную сумму элементов таких троек. Если таких троек не найдётся — следует вывести 0 0.
Задание 17
Ответ:
18. Тип 18 № 35476
Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в правый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму.
Исходные данные записаны в электронной таблице.
Задание 18
Пример входных данных (для таблицы размером 4 × 4):
| 4 | 21 | −36 | 11 |
| 37 | −12 | 29 | 7 |
| −30 | 24 | −1 | −5 |
| 8 | −8 | 9 | 21 |
Для указанных входных данных ответом будет число 95 (робот проходит через клетки с числами 4, 37, 24, 9, 21).
19. Тип 19 № 27768
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать
ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 84. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 84 или больше камней.
В начальный момент в первой куче было 16 камней, во второй куче — S камней, 1 ≤ S ≤ 67.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, т.е не гарантирующие выигрыш независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
20. Тип 20 № 27769
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать
ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 84. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 84 или больше камней.
В начальный момент в первой куче было 16 камней, во второй куче — S камней, 1 ≤ S ≤ 67.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, т.е не гарантирующие выигрыш независимо от игры противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
21. Тип 21 № 27770
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать
ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 84. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 84 или больше камней.
В начальный момент в первой куче было 16 камней, во второй куче — S камней, 1 ≤ S ≤ 67.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, т.е не гарантирующие выигрыш независимо от игры противника.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
22. Тип 22 № 47583
В файле 22_3.xlsx содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1;2 |
| 4 | 7 | 3 |
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 — через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.
23. Тип 23 № 15932
Исполнитель РазДваТри преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает его на 3.
Программа для исполнителя РазДваТри — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 44 и при этом траектория вычислений содержит число 13 и не содержит числа 29?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 18, 19, 38.
24. Тип 24 № 35482
Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (ABC…Z).
Необходимо найти строку, содержащую наименьшее количество букв G (если таких строк несколько, надо взять ту, которая находится в файле раньше), и определить, какая буква встречается в этой строке чаще всего. Если таких букв несколько, надо взять ту, которая позже стоит в алфавите.
Пример. Исходный файл:
GIGA
GABLAB
AGAAA
В этом примере в первой строке две буквы G, во второй и третьей — по одной. Берём вторую строку, т. к. она находится в файле раньше. В этой строке чаще других встречаются буквы A и B (по два раза), выбираем букву B, т. к. она позже стоит в алфавите. В ответе для этого примера надо записать B.
Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.
Задание 24
25. Тип 25 № 35483
Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Ответ:
26. Тип 26 № 27885
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
Задание 26
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 3000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50
Ответ:
27. Тип 27 № 35485
В текстовом файле записан набор натуральных чисел, не превышающих 108. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наибольшую сумму можно при этом получить?
Входные данные.
Файл A
Файл B
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
Пример входного файла:
4
5
8
14
11
В данном случае есть четыре подходящие тройки: 5, 8, 11 (сумма 24); 5, 8 14 (сумма 27); 5, 14 11 (сумма 30) и 8, 14, 11 (сумма 33). В ответе надо записать число 33.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Просмотр содержимого документа
«ЕГЭ 2023 Январь Информатика Вариант 1»
На уроке рассматривается решение 13 задания ЕГЭ по информатике
Содержание:
- Объяснение заданий 13 ЕГЭ по информатике
- Графы. Поиск количества путей
- Решение заданий 13 ЕГЭ по информатике
13-е задание: «Информационные модели»
Уровень сложности
— повышенный,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 3 минуты.
Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
До ЕГЭ 2021 года — это было задание № 15 и № _ ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
«Игнорирование указаний в условии задания, что путь должен включать (или не включать) заданные промежуточные вершины»
ФГБНУ «Федеральный институт педагогических измерений»
Графы. Поиск количества путей
- Если в город
Rиз городаAможно добраться только из городовX,YиZ, то количество различных путей из городаAв городRравно сумме числа различных путей проезда изAвX, изAвYи изAвZ, то есть: - где NR — это количество путей из вершины
Aв вершинуR - Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
- Часто задачи с графами целесообразней решать с конца.
NR = NX + NY + NZ
Решение заданий 13 ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube: 
Задание демонстрационного варианта 2022 года ФИПИ
13_1:
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?
✍ Решение:
- Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:
- Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
- 1. А — Б — В — И — М
- 2. А — Б — В — Е — И — М
- 3. А — Б — В — Е — М
- 4. А — Б — В — Е — К — М
- Теперь посчитаем результаты по оставшимся вершинам:
М = И + Е + К
-----
И = Е
Е = Г + Ж
Г = Б + А + Д = 1 + 1 + 1 = 3
Ж = Г = 3
К = Е + Ж
Теперь возвращаемся, подставляя найденные значения: ↑
Е = Г + Ж = 3 + 3 = 6
Ж = Г = 3
И = Е = 6 (получили из последующих шагов)
К = Е + Ж = 6 + 3 = 9
М = И + Е + К = 6 + 6 + 9 = 21
Результат: 21
Видео ЕГЭ по информатике (аналитическое решение):
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
13_2:
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?
✍ Решение:
- Удалим ребра, которые проходят через вершину Г:
- Теперь посчитаем результаты по оставшимся вершинам:
М = И + Е + К
-----
И = В + Е
В = 1
Е = В + Ж
Ж = 1
Теперь возвращаемся, подставляя найденные значения: ↑
Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3
К = Е = 2
М = И + Е + К = 3 + 2 + 2 = 7
Результат: 7
Подробное решение данного 13 задания в видеоуроке:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
13 задание. Демоверсия ЕГЭ 2018 информатика:
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
✍ Решение:
Результат: 20
Подробное решение 13 задания демоверсии ЕГЭ 2018 года смотрите на видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
13_4:
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М?
Длиной пути считать количество дорог, составляющих этот путь.
✍ Решение:
ЕГЭ 2023. Экзаменационная работа состоит из 27 заданий с кратким ответом, выполняемых с помощью компьютера. На выполнение экзаменационной работы по информатике отводится 3 часа 55 минут (235 минут).
В конце варианта приведены правильные ответы ко всем заданиям. Вы можете свериться с ними и найти у себя ошибки.
Скачать тренировочный вариант ЕГЭ: Скачать
Файлы для варианта: Скачать
Интересные задания:
4. Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово СПОРТЛОТО кодируется как 10010100110011110000100. Какой код соответствует букве Л, если известно, что коды подбирались под минимальную длину заданного слова. Примечание: под условием Фано понимается такой метод кодирования, при котором ни одно кодовое слово не является началом другого кодового слова. Такой способ кодирования позволяет получить однозначно декодируемый код.
5. На вход алгоритма подаётся натуральное число N большее 4. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Далее эта запись обрабатывается по следующему правилу:
а) если количество цифр в двоичной записи числа нечётное, то центральный бит двоичного представления инвертируется;
б) если количество цифр в двоичной записи числа чётное, то два центральных бита двоичного представления инвертируется; Например, для исходного числа 610 = 1102 результатом является число 1002 = 410, а для исходного числа 910 = 10012 результатом является число 11112 = 1510. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 100 и меньшее N. В ответе запишите это число в десятичной системе счисления.
7. Спутник каждую секунду делает снимок 20 на 7.6 километра. Размер пикселя на местности 0.65х0.65 метра. Цвет пикселя выбирается из палитры в 256 цветов. Оцените объем памяти (в МБ) для хранения одного изображения. Сжатие не производится. Ответ округлите до большего целого числа.
8. Определите количество десятизначных чисел, записанных в восьмеричной системе счисления, в записи которых ровно пять цифры 7 и при этом никакая нечетная цифра не стоит рядом с цифрой 7.
9. Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнено строго одно из условий:
– в строке есть повторяющиеся числа;
– в строке есть ровно три нечетных числа. В ответе запишите только число.
10. Текст произведения Ника Горькавого «Теория Катастроф» представлен в виде текстового файла. Откройте файл и определите, сколько бифуркационных технологий содержал итоговый список. В ответе запишите только число.
11. Вася решил закодировать персональные данные всех 1347 учеников всей школы. Для каждого ученика был сформирован ID из нескольких полей: номер класса, буква (а,б,в,г,д), пол, день и месяц рождения, номер имени по таблице имен (всего 103), номер фамилии по таблице фамилий (всего 733). Сперва Вася для каждого поля выделил минимальное количество байт. Затем попробовал закодировать все поля непрерывной битовой строкой и для каждого ID выделил минимальное количество байт. Сколько байт сэкономил Вася во втором случае для кодирования всех учеников школы?
Вам будет интересно:
ЕГЭ 2023 по информатике 11 класс. Новый тренировочный вариант №6 — №221107 (задания и ответы)
* Олимпиады и конкурсы
* Готовые контрольные работы
* Работы СтатГрад
* Официальные ВПР
Поделиться:
В решение заданий демо-версии используется язык программирования Python.
|
Задание 1. Анализ информационных моделей На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт В и из пункта F в пункт A. В ответе запишите целое число.
|
На графе расставим веса вершин. Далее 2 и 7 вершины ведут нас к 5, значит А это 5, оставшаяся «тройка» это вершина Е под номером 6. Сумма дорог BD + AF = 53 + 5 = 58 Ответ: 58 |
||||||||||||||||||
|
Задание 2. Построение таблиц истинности логических выражений Миша заполнял таблицу истинности логической функции F F= ¬(y → x) v (z→ w) v ¬z , но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Функция задана выражением ¬x v y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид. В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
|
¬(y → x) v (z→ w) v ¬z=0. Следовательно y → x =1, z→ w=0, z=1. Значит третий столбец z. z→ w=0, значит w=0, и это может быть только 4 столбец. y → x =1, следовательно из второй строки мы видим, что первый столбец может быть только у, а второй х.
Решение на Python
Ответ: YXZW |
||||||||||||||||||
Задание 3. Базы данных. Файловая система В прикрепленном файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц. Таблица «Движение товаров» содержит записи о поставках товаров в
На рисунке приведена схема указанной базы данных. Используя информацию из приведённой базы данных, определите общий вес |
На третьем листе книги применим фильтр по району и получим ID четырех магазинов.
На втором листе применим фильтр по товару и получим ID товара.
На первом листе применим фильтры по ID товара и ID магазинов и типу операции. Все даты попадают в интервал от 1 до 8 июня. Получим:
Поступило в продажу 710 упаковок. В упаковке 0,5 кг. Получим 355 кг. Ответ: 355 |
||||||||||||||||||
|
Задание 4. Кодирование и декодирование информации По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код,удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? |
Ответ: 14 |
||||||||||||||||||
|
Задание 5. Анализ и построение алгоритмов для исполнителей На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему 1. Строится двоичная запись числа N. Полученная таким образом запись является двоичной записью искомого числа R.Например, для исходного числа 610 = 1102 результатом является число |
Минимальное R, большее 40, это 41.
ИЛИ программное решение
Ответ: 16
|
||||||||||||||||||
|
Задание 6. Определение результатов работы простейших алгоритмов Исполнитель Черепаха действует на плоскости с декартовой системой координат. Черепахе был дан для исполнения следующий алгоритм: Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 5 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n– целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n– целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m– целое число), вызывающая изменение направления движения на m градусов против часовой стрелки. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Определите, сколько точек с целочисленными координатами будут находиться внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого пересечения. |
Сначала нужно построить фигуру.
Далее мы находим уравнения прямых, которыми ограничена фигура и решаем
ИЛИ
Ответ: 1 задание — 38, 2 задание — 128 |
||||||||||||||||||
|
Задание 7. Кодирование и декодирование информации. Передача информации Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 28 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 3,5 раза выше и частотой дискретизации в 2 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер полученного при повторной записи файла в Мбайт. В ответе запишите только целое число, единицу измерения писать не нужно. |
I = ν ⋅ i ⋅ t ⋅ k, где ν — частота дискретизации (Гц), i — разрешение (бит), t — время (с), k — количество дорожек (1 -моно, 2- стерео, 4 — квадро) I1 = ν ⋅ i ⋅ t I2 = 3,5 · 28 = 98 Ответ: 98 |
||||||||||||||||||
|
Задание 8. Перебор слов и системы счисления Определите количество пятизначных чисел, записанных в восьмеричной системе счисления, в записи которых только одна цифра 6, при этом никакая нечётная цифра не стоит рядом с цифрой 6. |
* * * * * — пятизначное число. 6 * * * * — вариантов 3 ⋅ 7 ⋅ 7 ⋅ 7 = 1029 Ответ: 2961 |
||||||||||||||||||
Задание 9. Работа с таблицами Файл с данными Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия: |
Для решения этой задачи понадобится 10 вспомогательных столбцов. Сначала мы посчитаем количество повторяющихся чисел в каждой строке. Затем сумму каждой строки диапазона H:M. Если повторений нет, то эта сумма равна 6. Далее мы найдем среднее арифметическое неповторяющихся значений.
Затем найдем сумму повторяющихся значений.
Затем проверим соблюдение двух условий. И подсчитаем количество строк, в которых соблюдаются оба условия.
Ответ: 2241 |
||||||||||||||||||
Задание 10. Поиск символов в текстовом редакторе Файл с данными Текст произведения Льва Николаевича Толстого «Севастопольские рассказы» представлен в виде файлов различных форматов. Откройте один из файлов и определите, сколько раз встречается в тексте отдельное слово «теперь» со строчной буквы. Другие формы этого слова учитывать не следует. |
В текстовом редакторе используем инструмент найти (по умолчанию он не учитывает регистр, в расширенном поиске есть кнопка больше, где можно проверить настройки). Ищем слово целиком. Ставим галочку учитывать регистр. Слово теперь со строчной буквы встречается 45 раз. Ответ: 45 |
||||||||||||||||||
|
Задание 11. Вычисление количества информации При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 250 символов и содержащий только десятичные цифры и символы из 1650-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Кбайт), необходимый для хранения 65 536 идентификаторов. В ответе запишите только целое число – количество Кбайт. |
I = K · i, N = 2 i ID : ****….**** – всего 250 различных символов в наборе N = 10 + 1650 = 1660, 1024<1660<2048, 2048 = 211, значит для кодирования одного символа нужно 11 бит. IID = 250 · 11 = 2750 бит = 343,75 байт ≈ 344 байт – отводится на идентификатор целое число байт I65536 = 65536 ⋅ 344 = 22544384 байта = 22016 Кбайт– всего Ответ: 22016 |
||||||||||||||||||
|
Задание 12. Выполнение алгоритмов для исполнителей Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Цикл выполняется, пока условие истинно. В конструкции ЕСЛИ условие выполняется команда 1 (если условие истинно). В конструкции ЕСЛИ условие выполняется команда 1 (если условие истинно) или команда 2 (если условие ложно). Дана программа для Редактора: |
def pr(n): #функция определяет простое ли число for n in range(100): #перебираем n if ‘>2’ in s: if ‘>0’ in s: sum_s = 0 Ответ: 5 |
||||||||||||||||||
|
Задание 13. Поиск путей в графе На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
|
Начнем подсчет из вершины Е налево через В и возвращаемся в Е через Л. Ответ: 21 |
||||||||||||||||||
|
Задание 14. Кодирование чисел. Системы счисления Операнды арифметического выражения записаны в системе счисления с основанием 15. |
for x in range(15): if n%14 == 0: Ответ: 8767 |
||||||||||||||||||
|
Задание 15. Преобразование логических выражений На числовой прямой даны два отрезка: D = [17; 58] и C = [29; 80]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение |
def deli(n,m): for A in range(1,1000): if Ok: Ответ: 94 |
||||||||||||||||||
|
Задание 16. Рекурсивные алгоритмы Алгоритм вычисления значения функции F(n), где n – натуральное число, |
F(2023) = 2023! = 2023 ⋅ 2022! F(2023)/F(2020) = (2023 ⋅ 2022 ⋅ 2021 ⋅ 2020!)/2020! = 2023 ⋅ 2022 ⋅ 2021 = = 8266912626 Ответ: 8266912626 |
||||||||||||||||||
Задание 17. Проверка на делимость Файл с данными В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите количество пар последовательности, в которых |
f= open(’17.txt’) k = 0 for i in p: for i in range(1,len(p)): #Осторожно, скобки! print(k,PP)
Ответ: 180 190360573 |
||||||||||||||||||
Задание 18. Робот-сборщик монет Файл с данными Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.Пример входных данных:
Для указанных входных данных ответом должна быть пара чисел 41 и 22. |
Сначала скопируем таблицу рядом, начиная со столбца АА, можно уменьшить ширину столбца до 4-5. Ячейка АА1=А1. Ячейка АВ1 = АА1+В1, протягиваем ее до АТ1. Ячейка АА2 = АА1 + А2, протягиваем ее до АА20. Далее ячейка АВ2 = В2+МАКС(АА2;АВ1), протягиваем ее на весь оставшийся диапазон, копируем только значения, не трогая стен. Справа от стен формулы повторяют крайний левый рял, столбец АА, снизу от стен формулы копируют верхнюю строку 1.
Далее делаем замену всех формул МАКС на МИН.
Ответ: 1099 1026 |
||||||||||||||||||
|
Задание 19. Выигрышная стратегия. Задание 1 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 129 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 128. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. |
При значениях S < 64 у Пети есть возможность сделать такой ход, что Ваня не сможет выиграть своим первым ходом. При значении S = 64 Петя своим первым ходом может получить 65 или 128 камней в куче. Во всех случаях Ваня увеличивает количество камней в куче в два раза и выигрывает своим первым ходом. Ответ: 64 |
||||||||||||||||||
|
Задание 20. Выигрышная стратегия. Задание 2 Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
Найденные значения запишите в порядке возрастания. |
Значение S должно быть меньше 64, поскольку иначе Ваня сможет выиграть своим первым ходом. Ответ: 32 63 |
||||||||||||||||||
|
Задание 21. Выигрышная стратегия. Задание 3 Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
Если найдено несколько значений S, в ответе запишите минимальное из них. |
Ответ: 62 |
||||||||||||||||||
|
Задание 22. Многопроцессорные системы В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. |
В независимых процессах время считается от 0, Ответ: 17 |
||||||||||||||||||
|
Задание 23. Анализ программы с циклами и условными операторами Исполнитель преобразует число на экране. |
def f(x, y): print (f(1,10) * f(10, 35)) Ответ: 98 |
||||||||||||||||||
Задание 24. Анализ программы с циклами и условными операторами Файл с данными Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих подряд пар символов вида согласная + гласная |
f=open(’24.txt’) PP = [‘CA’, ‘CO’, ‘DA’, ‘DO’, ‘FA’, ‘FO’] for i in range(1, len(p), 2): Ответ: 95 |
||||||||||||||||||
|
Задание 25. Анализ программы с циклами и условными операторами Назовём маской числа последовательность цифр, в которой также могут Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 1?2139*4, делящиеся на 2023 без остатка. |
Самый простой способ использовать библиотеку fnmatch.
или так полным перебором: y = {»,’0′,’00’,’000′} for x in range (1000): Ответ: 162139404 80148 |
||||||||||||||||||
Задание 26. Анализ программы с циклами и условными операторами В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. |
|||||||||||||||||||
Задание 27. Анализ программы с циклами и условными операторами У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Файл А Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. |
Ответ: 51063 5634689219329 |
ЕГЭ информатика 13 задание разбор, теория, как решать.
Поиск путей в графе, (П) — 1 балл
Е13.26 ненулевой длины, которые начинаются и заканчиваются в городе Е
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не …
Читать далее
Е13.25 из пункта А в пункт С, проходящих ровно через один из пунктов Ж и М
На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И , К , Л , М , Н , П, Р , С . П о к аждой д ороге м ожно п ередвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих …
Читать далее
Е13.24 из города А в город Л, проходящих через город 3
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город 3? Ответ: Апробация ЕГЭ по информатике 19 февраля 2022 – задание …
Читать далее
Е13.23 Сколько существует различных путей из пункта А в пункт С, проходящих через пункты Е и М
На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И , К , Л , М , Н , П, Р , С . По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих через пункты Е и М? …
Читать далее
Е13.22 Сколько существует различных путей из города Г в город Т, не проходящих через Л?
Сколько существует различных путей из города Г в город Т, не проходящих через Л? На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответ: Тренировочный вариант №1 от 13.09.2021 «ЕГЭ 100БАЛЛОВ»
Читать далее
Е13.21 Какова длина самого короткого пути из города А в город М
Какова длина самого короткого пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответ: Источник: «03.05.2021 ЕГЭ 100БАЛЛОВ, …
Читать далее
Е13.20 Какова длина самого длинного пути из города А в город М
Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответы: Источник: «19.04.2021 ЕГЭ 100БАЛЛОВ, …
Читать далее
Е13.19 Какова длина самого длинного пути из города А в город Л?
Какова длина самого длинного пути из города А в город Л? На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город Л? Длиной пути считать количество дорог, …
Читать далее
Е13.18 проходящих через пункт Г или через пункт Е, но не через оба этих пункта
проходящих через пункт Г или через пункт Е, но не через оба этих пункта. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город …
Читать далее
Е13.17 различных путей пункта А в пункт Н, проходящих через пункт Е
Сколько существует различных путей из пункта А в пункт Н, проходящих через пункт Е? На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Ответ: Тренировочный вариант от 09.11.2020 «Евгений Джобс»
Читать далее