Информатика

Петя и Ваня играют в следующую игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в четыре раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 150. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 150 или больше камней. В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤143.
 

Задание 19

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

Задание 20

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания. 

 

Задание 21

Найдите такое значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
 

Формат ввода ответов 

На каждое задание ответы пишите с новой строки. Например, если ответ на задание 19 - 1, на задание 20 -  2 и 3, на задание 21 - 4, то ответы надо записать так:

1
2 3
4

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

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

Типовой пример организации данных в файле:

Вводится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно.

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

Алгоритм вычисления значения функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n + 5, если n < 10;
F(n) = n % 5 + G(F(n/5)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите количество различных значений n, не превосходящих 10⁶,  при котором значение функции F(n) кратно значению функции G(n)?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.
 

Укажите наименьшее целое значение А, при котором выражение истинно для любых целых положительных значений x и y.

Операнды арифметического выражения записаны в системе счисления с основанием 17. В записи чисел переменными x и y обозначены неизвестные цифры. Определите наименьшее значение х, при которых значение данного арифметического выражения кратно 181. Для найденных значений x и y вычислите частное от деления значения арифметического выражения на 181 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

Два узла, находящиеся в разных подсетях, имеют IP-адреса 192.168.128.153 и 192.168.224.185. В масках обеих подсетей одинаковое количество единиц. Укажите наименьшее возможное значение третьего слева байта этой маски. Ответ запишите в виде десятичного числа

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w
обозначают цепочки символов.
А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды 
заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождении? цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение
«истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

ПОКА условие
    последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (63) ИЛИ нашлось (664) ИЛИ нашлось (6665)
  ЕСЛИ нашлось (63) ТО заменить (63, 4)
  ИНАЧЕ
    ЕСЛИ нашлось (664) ТО заменить (664, 65)
    ИНАЧЕ
      ЕСЛИ нашлось (6665) ТО заменить (6665, 663) КОНЕЦ ЕСЛИ
    КОНЕЦ ЕСЛИ
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся и заканчивающаяся цифрой «5», а между ними записана n раз цифра «6» (3 < n < 10 000). Определите количество возможных различиных значений суммы цифр результирующей строки, при различных значениях n.

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 156 символов и содержащийтолько десятичные цифры и символы из 1377-символьного специального алфавита. В базе данных ддя хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объем памяти (в Кбайт), необходимый для хранения 32768 идентификаторов. 
В ответе запишите только целое число - количество Кбайт. 

С помощью текстового редактора определите, сколько раз встречается сочетание букв "или" только в составе других слов, но не как отдельное слово, в тексте глав с IX по XI рассказа А.И. Куприна "Гранатовый браслет". В ответе укажите только число.

Файл к заданию

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

Файл к заданию

Сколько существует семиричных шестизначных чисел, кратных пяти и содержащих в своей записи ровно одну цифру 5, и при этом никакие две одинаковые цифры не стоят рядом.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 602х898 пикселей, используя палитру из 16777216 цветов. Для передачи снимки группируются в пакеты по 128 штук, затем передаются в центр обработки информации со скоростью 1024 бит/с.  Сколько секунд требуется для передачи одного пакета фотографий?
В ответе запишите целую часть полученного числа.
 

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её
голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять
хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая
передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

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

Повтори 4 [Налево 90 Повтори 2 [Вперёд 4 Направо 90] Вперёд 4]
Поднять хвост
Налево 90 Вперёд 3 Направо 90 Назад 3
Опустить хвост
Повтори 4 [Вперёд 10 Направо 90]

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

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

Например, для исходного числа 13 = 1101₂ результатом является число 1001101₂ = 77, а для исходного числа 12 = 1001₂ это число 1011₂ = 11. 

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

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц. Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. занесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Таблица «Магазин» содержит информацию о местонахождении магазинов. На рисунке приведена схема указанной базы данных.
Используя информацию из приведённой базы данных, определите на сколько увеличилось суммарное количество кг сахара любого вида, имеющихся в наличии в магазинах Первомайского района, за период с 1 по 10 августа включительно. В ответе запишите только число.


Файл к заданию

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100). В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.
 

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Дано неориентированное дерево "— связный граф из \(n\) вершин без циклов, и число \(k\). Зафиксируем некоторую вершину \(s\) дерева и назовем ее столицей.

Ориентируем ребра дерева в направлении от столицы. Иными словами, ориентируем ребро \((u, v)\) в направлении \(u \to v\), если при подвешивании дерева за вершину \(s\) вершина \(u\) является родителем вершины \(v\). Заметим, что при таком ориентировании ребер каждая вершина достижима из столицы.

Определим расстояние до вершины \(v\) графа как минимальное количество ребер на пути из \(s\) в \(v\). Назовем доступностью вершины \(s\) максимальное из расстояний до всех вершин.

Разрешается добавить в дерево не более \(k\) дополнительных ориентированных ребер.

Для каждой вершины \(s\) дерева определите, какой минимальной доступности можно достичь, если выбрать вершину \(s\) в качестве столицы.

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

Формат входных данных
Первая строка содержит три целых числа \(n\), \(k\) и \(t\) (\(2 \le n \le 2 \cdot 10^5\), \(1 \le k \le n - 1\), \(n \cdot k \le 2 \cdot 10^5\), \(0 \le t \le 1\)) — количество вершин дерева, ограничение на максимальное количество добавленных ребер и число \(t\), равное \(0\), если нужно вывести ответ только для вершины с номером \(1\), и равное \(1\) иначе.

Каждая из следующих \(n - 1\) строк содержит два целых числа \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) — ребра дерева.

Гарантируется, что заданные ребра образуют дерево.

Формат выходных данных

В случае, если \(t = 0\), выведите единственное целое число: минимальную доступность, которую можно достичь, выбрав вершину с номером \(1\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

В случае, если \(t = 1\), выведите \(n\) чисел: \(i\)-е число равняется минимальной доступности, которую можно достичь, выбрав вершину \(i\) в качестве столицы, и добавив не более \(k\) дополнительных ориентированных ребер.

На рисунке приведены иллюстрации к первому примеру. Пунктирными линиями обозначены добавленные ребра. Для вершин \(1\) и \(2\) минимальная доступность равняется \(1\), а для вершин \(3\), \(4\) и \(5\) минимальная доступность равняется 2.

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

Формат выходных данных
Выведите единственное число — максимальное количество пар обуви.

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести. 

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк si; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n. 
 

Ограничения

• 1 <= k <= 600
• 1 <= длина si <= 100
• si состоит только из цифр '0' and '1'.
• 1 <= m, n <= 100

Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества  {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.