Информатика

7 829 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
ТР02-Д. Задание 12. Один проход машины Тьюринга#101459

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя, включая специальный пустой символ λ.

Время работы исполнителя делится на дискретные такты — шаги. На каждом такте головка находится в одном из допустимых состояний q0, q1, … . В начальный момент головка находится в состоянии q0.

Головка обозревает одну ячейку ленты — текущую ячейку. За один такт исполнитель записывает в неё указанный символ, после чего может сдвинуться в соседнюю ячейку и перейти в указанное состояние либо завершить работу. Записываемый символ может совпадать с уже находящимся в ячейке.

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

Каждая команда состоит из трёх элементов, разделённых запятыми:

  1. символ, записываемый в текущую ячейку;
  2. направление: L — сдвиг на одну ячейку влево, R — сдвиг на одну ячейку вправо, S — завершение работы после записи символа без сдвига;
  3. состояние, в которое переходит головка.

Например, команда X, L, q2 означает: записать X в текущую ячейку, сдвинуться в соседнюю слева ячейку и перейти в состояние q2. Запись символа производится до сдвига.

Пример выполнения программы

Пусть на ленте подряд записаны три символа Z, остальные ячейки пусты, головка находится на первой пустой ячейке справа от слова ZZZ в состоянии q0. Для этой иллюстрации используется следующая программа:

Состояние λ Z
q0 λ, L, q0 X, L, q1
q1 λ, S, q1 X, L, q1

Начальное расположение ленты и головки:

… λ λ Z Z Z λ λ …
            ▲ q0    

Лента и головка после остановки:

… λ λ X X X λ λ …
    ▲ q1            

Головка перемещается влево, заменяет все Z на X и останавливается на первой пустой ячейке слева от слова XXX. Пример поясняет правила чтения таблицы и не является программой основного задания.

Выполните задание

На ленте в соседних ячейках записано двоичное представление числа 1733 без ведущих нулей. Все остальные ячейки заполнены пустым символом λ. В начальный момент головка находится в состоянии q0 в ближайшей пустой ячейке справа от записи числа.

Программа работы исполнителя:

Состояние λ 0 1
q0 λ, L, q1    
q1 λ, S, q1 1, L, q1 0, L, q1

Определите число, двоичная запись которого получится на ленте после завершения программы. Ведущие нули, если они появились, не влияют на значение числа. В ответе запишите число в десятичной системе счисления.

ЕГЭ_информатикаЕГЭ-12. Выполнение алгоритмов для исполнителя (МТ)
—Войти и решать
ТР02-Д. Задание 11. Число идентификаторов в памяти#101458

Каждому объекту в информационной системе присваивается идентификатор, состоящий из 55 символов. В идентификаторах используют десятичные цифры, 26 прописных и 26 строчных латинских букв, а также 20 специальных знаков. Все перечисленные символы различны.

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

Для хранения идентификаторов выделено 192 Кбайт памяти. Определите максимальное количество объектов, идентификаторы которых можно сохранить в этой памяти. В ответе запишите целое число. Считать, что 1 Кбайт = 1024 байт.

ЕГЭ_информатикаЕГЭ-11. Вычисление информационного объема сообщения
—Войти и решать
ТР02-Д. Задание 10. Количество адресов устройств#101457

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла относится к адресу сети, а какая — к адресу узла в этой сети. В маске сначала идут единицы, затем нули. Адрес сети получают поразрядной конъюнкцией IP-адреса узла и маски.

Для узла с IP-адресом 172.20.52.131 задана маска сети 255.255.252.0.

Определите максимальное количество устройств, которым можно назначить IP-адреса в этой сети. В ответе запишите только число.

ЕГЭ_информатикаЕГЭ-10. Компьютерные сети. Адресация в Интернете
—Войти и решать
ТР02-Д. Задание 09. Суммы чётных и нечётных чисел#101456
Задание выполняется с использованием прилагаемых файлов.

Откройте файл электронной таблицы, содержащей в каждой строке шесть натуральных чисел. Числа не превышают 1000. Таблица не содержит строки заголовков.

Определите количество строк, для которых одновременно выполнены оба условия:

  • в строке ровно три чётных и три нечётных числа;
  • сумма чётных чисел строки больше суммы её нечётных чисел.

Повторяющиеся числа учитываются каждый раз, когда они записаны в строке. В ответе запишите только число.

ЕГЭ_информатикаЕГЭ-09. Анализ числовых данных в электронных таблицах
—Войти и решать
ТР02-Д. Задание 08. Перестановки букв с повторением#101455

Из всех букв слова ПЛАНЕТА составляют семибуквенные слова. Каждая буква используется столько раз, сколько она встречается в исходном слове: буква А — два раза, остальные буквы — по одному. Одинаковые слова, полученные перестановкой двух букв А, считаются одним словом.

Сколько различных слов можно составить, если слово должно начинаться согласной буквой и заканчиваться гласной? В этой задаче гласными являются А и Е, согласными — П, Л, Н, Т. Слово — любая последовательность букв, не обязательно осмысленная.

ЕГЭ_информатикаЕГЭ-08. Кодирование, комбинаторика
—Войти и решать
ТР02-Д. Задание 07. Объём растрового изображения#101454

Камера формирует растровое изображение размером 1408 × 900 пикселей. Изображение может содержать 200 различных цветов. Для кодирования цвета каждого пикселя используется одинаковое и минимально возможное количество бит.

Коды пикселей записываются подряд без промежутков. Сжатие не производится; служебная информация и заголовок файла не учитываются.

Определите наименьшее целое количество Кбайт, достаточное для хранения одного такого изображения. В ответе запишите только число. Считать, что 1 Кбайт = 1024 байт, 1 байт = 8 бит.

ЕГЭ_информатикаЕГЭ-07. Кодирование информации (графика, звук)
—Войти и решать
ТР02-Д. Задание 06. Точки внутри пересечения#101453

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

У исполнителя имеются команды:

  • Поднять хвост — перейти к перемещению без рисования.
  • Опустить хвост — перейти в режим рисования.
  • Вперёд n — переместиться на n единиц в направлении головы; Назад n — на n единиц в противоположном направлении, не меняя направления головы.
  • Направо m — повернуть на m градусов по часовой стрелке; Налево m — на m градусов против часовой стрелки.

Здесь n и m — целые числа. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что указанная последовательность команд выполняется k раз.

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

Повтори 4 [Вперёд 26 Направо 90 Вперёд 18 Направо 90]
Поднять хвост
Вперёд 8
Направо 90
Вперёд 6
Налево 90
Опустить хвост
Повтори 2 [Вперёд 30 Направо 90 Вперёд 25 Направо 90]

Определите количество точек с целочисленными координатами, находящихся строго внутри области пересечения фигур, ограниченных линиями этого алгоритма. Точки на границе пересечения учитывать не нужно.

ЕГЭ_информатикаЕГЭ-06. Определение результатов работы алгоритма для исполнителя
—Войти и решать
ТР02-Д. Задание 05. Перестановка двоичных разрядов#101452

На вход алгоритма подаётся натуральное число N, большее 1. Алгоритм строит по нему новое число R следующим образом.

  1. Строится двоичная запись числа N без ведущих нулей.
  2. Последняя цифра этой записи переносится в её начало. Порядок остальных цифр не меняется.
  3. Полученная запись рассматривается как двоичная запись числа R. Ведущий нуль, если он появился, не влияет на значение числа. Результат переводится в десятичную систему счисления.

Например, для N = 1310 = 11012 получается запись 11102, то есть R = 14. Для N = 1010 = 10102 получается запись 01012, то есть R = 5.

Укажите минимальное число N, после обработки которого R больше 180. В ответе запишите число в десятичной системе счисления.

ЕГЭ_информатикаЕГЭ-05. Анализ простых алгоритмов
—Войти и решать
ТР02-Д. Задание 04. Кодирование по концам кодовых слов#101451

По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Г, Д и Е. Для передачи используется неравномерный двоичный код, удовлетворяющий следующему условию: никакое кодовое слово не является концом другого кодового слова. Это условие позволяет однозначно декодировать сообщение, начиная с его правого конца.

Кодовые слова некоторых букв известны:

БукваКодовое слово
А00
Б010
В110
Г01

Для букв Д и Е кодовые слова ещё не определены. Укажите кратчайшее кодовое слово для буквы Д, при котором можно подобрать кодовое слово для Е так, чтобы весь код удовлетворял указанному условию.

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

ЕГЭ_информатикаЕГЭ-04. Кодирование и декодирование информации
—Войти и решать
ТР02-Д. Задание 03. Изменение запаса товаров#101450
Задание выполняется с использованием прилагаемых файлов.

В файле приведён фрагмент базы данных «Хозяйственные товары» о поступлении и продаже товаров в магазинах районов города. База данных состоит из трёх связанных прямоугольных таблиц.

Таблица «Движение товаров» содержит записи о поступлении товаров в магазины и продаже товаров. Поле «Тип операции» содержит значение «Поступление» или «Продажа», а в поле «Количество упаковок, шт.» указано, сколько упаковок товара поступило в магазин или было продано.

ID операции Дата ID магазина Артикул Количество упаковок, шт. Тип операции

Таблица «Товар» содержит информацию об основных характеристиках каждого товара.

Артикул Отдел Наименование товара Ед_изм Количество в упаковке Цена за упаковку

Таблица «Магазин» содержит информацию о местонахождении магазинов.

ID магазина Район Адрес

Схема базы данных

Используя информацию из приведённой базы данных, определите, на сколько упаковок увеличился запас всех видов шампуня в магазинах Заречного района за период с 4 по 12 июня включительно.

Изменение запаса за указанный период определяется как разность между количеством поступивших и количеством проданных упаковок.

В ответе запишите только число.

ЕГЭ_информатикаЕГЭ-03. Поиск в базах данных
—Войти и решать
ТР02-Д. Задание 02. Таблица истинности с пропусками#101449

Миша заполнял таблицу истинности логической функции F

\(F = (x \land \neg y) \lor (y \equiv z) \lor w\),

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу соответствует каждая из переменных w, x, y, z. Некоторые значения в таблице пропущены.

        F
  0 1 0 0
1 0   0 0
1   0 1 0

Определите, какому столбцу соответствует каждая переменная. В ответе запишите буквы w, x, y, z в порядке следования соответствующих столбцов: сначала букву первого столбца, затем второго и так далее. Буквы пишите подряд, без разделителей.

Например, для функции ¬x ∨ y строка с первым значением 0, вторым значением 1 и значением функции 0 соответствует порядку переменных yx. Этот пример не относится к исходной функции F.

ЕГЭ_информатикаЕГЭ-02. Таблицы истинности
—Войти и решать
ТР02-Д. Задание 01. Граф и таблица дорог#101448

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог в километрах. Все дороги двусторонние.

Определите сумму протяжённостей дорог из пункта A в пункт D и из пункта B в пункт E. В ответе запишите целое число.

ЕГЭ_информатикаЕГЭ-01. Анализ информационных моделей
—Войти и решать
Кто успешно сдал контрольную#101423

Контрольная состоит из четырёх обязательных задач с номерами от 1 до 4. В журнале записаны идентификатор ученика, номер задачи и балл за отправленное решение. Одну задачу можно отправлять несколько раз.

За каждую задачу учитывается лучший результат ученика среди всех его попыток по этой задаче. Если ученик не отправлял решение некоторой задачи, его результат по ней равен нулю.

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

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

Входные данные

В первой строке дано целое число N — количество записей (1 ≤ N ≤ 100000).

В каждой из следующих N строк даны три целых числа: идентификатор ученика, номер задачи и балл за попытку. Идентификатор находится в диапазоне от 1 до 1000000000 включительно, номер задачи — от 1 до 4, балл — от 0 до 100. Записи перечислены в порядке отправки решений; он может быть любым относительно номеров учеников и задач.

Выходные данные

Выведите через пробел количество сдавших контрольную и идентификатор выбранного ученика. Если контрольную не сдал никто, выведите 0 0.

ЕГЭ_информатикаСловари
—Войти и решать
Итоговый балл участника#101422

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

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

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

Входные данные

В первой строке дано целое число N — количество записей (1 ≤ N ≤ 100000).

В каждой из следующих N строк даны три целых числа: идентификатор участника, номер задачи и балл за попытку. Идентификаторы участников и номера задач находятся в диапазоне от 1 до 1000000000 включительно, баллы — от 0 до 100 включительно. Записи перечислены в порядке отправки решений; он может быть любым относительно номеров участников и задач.

Выходные данные

Выведите через пробел идентификатор победителя и его итоговый балл.

ЕГЭ_информатикаСловари
—Войти и решать
Стабильные датчики#101421

Датчики передают измерения температуры. Каждая запись содержит номер датчика и целую температуру. Один датчик может передать несколько измерений.

Датчик считается подходящим, если одновременно выполнены два условия:

  • он передал не менее K измерений;
  • разность между наибольшей и наименьшей переданными им температурами не превышает D.

Определите количество подходящих датчиков и наименьший номер среди них. Учитывайте только датчики, представленные в журнале.

Входные данные

В первой строке даны три целых числа N, K и D: количество записей, необходимое количество измерений и допустимая разность температур. Ограничения: 1 ≤ N ≤ 100000, 1 ≤ K ≤ 100000, 0 ≤ D ≤ 200.

В каждой из следующих N строк даны номер датчика и температура. Номер датчика — целое число от 1 до 1000000000 включительно, температура — целое число от −100 до 100 включительно. Записи перечислены в произвольном порядке.

Выходные данные

Выведите через пробел количество подходящих датчиков и наименьший их номер. Если подходящих датчиков нет, выведите 0 0.

ЕГЭ_информатикаСловари
—Войти и решать
Выручка по справочнику#101420

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

Выручка по одной записи равна цене товара, умноженной на количество проданных единиц. Выручка магазина равна сумме выручек по всем его записям.

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

Входные данные

Оба набора данных поступают последовательно через стандартный ввод.

Сначала дано целое число N — количество товаров в справочнике (1 ≤ N ≤ 100000). Следующие N строк содержат по два целых числа: код товара и цену одной единицы в рублях. Все коды в справочнике различны.

Затем дано целое число M — количество записей в журнале продаж (1 ≤ M ≤ 100000). Следующие M строк содержат по три целых числа: номер магазина, код товара и количество проданных единиц.

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

Выходные данные

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

ЕГЭ_информатикаСловари
—Войти и решать
Продажи товара в магазине#101419

В журнале продаж каждая запись содержит номер магазина, код товара и количество проданных единиц. Один товар может продаваться в нескольких магазинах. Для одной пары «магазин — товар» в журнале может быть несколько записей.

Найдите пару «магазин — товар» с наибольшим суммарным количеством проданных единиц. Если таких пар несколько, выберите пару с меньшим номером магазина. Если и номер магазина совпадает, выберите меньший код товара.

Входные данные

В первой строке дано целое число N — количество записей (1 ≤ N ≤ 100000).

В каждой из следующих N строк записаны три целых числа: номер магазина, код товара и количество проданных единиц. Каждое из этих чисел находится в диапазоне от 1 до 1000000000 включительно. Записи перечислены в произвольном порядке.

Выходные данные

Выведите через пробел три целых числа: выбранный номер магазина, код товара и суммарное количество проданных единиц для этой пары.

ЕГЭ_информатикаСловари
—Войти и решать
Две пары в строке#101418

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

  • два различных числа встречаются ровно по два раза, а ещё два различных числа — ровно по одному разу;
  • сумма четырёх элементов с повторяющимися значениями больше суммы двух элементов с неповторяющимися значениями.

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

Входные данные

В первой строке дано целое число N — количество строк таблицы (1 ≤ N ≤ 100 000).

Каждая из следующих N строк содержит ровно шесть целых чисел от 1 до 109 включительно, разделённых пробелами.

Выходные данные

Выведите одно целое число — количество строк, удовлетворяющих обоим условиям.

ЕГЭ_информатикаСловари
—Войти и решать
Буква после двух одинаковых#101417

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

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

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

Входные данные

В единственной строке дана строка длиной от 3 до 1 000 000 символов. Все символы — заглавные латинские буквы от A до Z.

Выходные данные

Выведите выбранную букву и через пробел количество подходящих троек, в которых она стоит третьей.

ЕГЭ_информатикаСловари
—Войти и решать
Лучший результат участника#101416

Участники выполняют несколько попыток. Для каждой попытки известны идентификатор участника и набранный им балл. В зачёт участнику идёт только лучший из всех его результатов.

Определите количество участников, чей зачётный результат не меньше заданного порога P. Учитываются только участники, у которых есть хотя бы одна запись во входных данных.

Входные данные

В первой строке даны два целых числа: количество попыток N и порог P (1 ≤ N ≤ 100 000, 0 ≤ P ≤ 100).

В каждой из следующих N строк записаны идентификатор участника и балл за одну попытку. Идентификатор — целое число от 1 до 109, балл — целое число от 0 до 100. Записи могут идти в любом порядке.

Выходные данные

Выведите одно целое число — количество участников с зачётным результатом не меньше P.

ЕГЭ_информатикаСловари
—Войти и решать
Поделиться
Класснуть