Информатика

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
1	0	0	0
0	0	0	1
1	1	1	0

 

Какое выражение соответствует F?

1) ¬X ∨ ¬Y ∨ Z

2) X ∧ Y ∧ Z

3) X ∨ Y ∨ Z

4) ¬X ∧ ¬Y ∧ ¬Z

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
0	0	1	1
0	1	0	0
1	0	0	1

 

Какое выражение соответствует F?

1) X ∨ Y ∨ Z

2) X ∨ ¬Y ∧ ¬Z

3) X ∨ ¬Y ∨ Z

4) ¬X ∧ Y ∧ ¬Z

 

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
0	1	1	0
1	0	0	1
0	0	1	0

 

Какое выражение соответствует F?

1) (X ∨ ¬Y) ∧ Z

2) (X ∧ ¬Y) ∨ Z

3) (X ∨ ¬Y) ∨ ¬Z

4) X ∧ ¬Y ∧ ¬Z

Статья, набранная на компьютере, содержит 12 страниц на каждой странице 16 строки, в каждой строке 64 символа. Определите максимальное количество символов в алфавите, при помощи которого была набрана статья, если известно, что её информационный объём равен 15 килобайт.

Статья, набранная на компьютере, содержит 20 страниц на каждой странице 32 строки, в каждой строке 64 символа. Определите максимальное количество символов в алфавите, при помощи которого была набрана статья, если известно, что её информационный объём равен 60 килобайт.

Статья, набранная на компьютере, содержит 11 страниц на каждой странице 16 строк, в каждой строке 256 символов. Определите максимальное количество символов в алфавите, при помощи которого была набрана статья, если известно, что её информационный объём равен 55 килобайт.

Статья, набранная на компьютере, содержит 12 страниц на каждой странице 64 строки, в каждой строке 256 символов. Определите максимальное количество символов в алфавите, при помощи которого была набрана статья, если известно, что её информационный объём равен 288 килобайт.
 

Статья, набранная на компьютере, содержит 17 страниц на каждой странице 32 строки, в каждой строке 256 символов. Определите максимальное количество символов в алфавите, при помощи которого была набрана статья, если известно, что её информационный объём равен 187 килобайт.

 

Волшебник ORZ любит колдовать над числами. Вы решили проверить его силу и дали ему массив a, состоящий из n целых чисел, а также целое число z. Нумерация элементов массива начинается с 1.

Волшебник ORZ проделывает следующую операцию любое количество (возможно, ноль) раз:

• Он выбирает целое число i, такое что 1<= i <= n. Затем он шепчет заклинание и после этого одновременно число  ai превращается в число равное (ai or z), а число z превращается в число, равное (ai and z). 

Здесь or и and обозначают операции побитового ИЛИ и побитового И соответственно.

Найдите максимально возможное значение максимального элемента в массиве a после некоторого (возможно, нулевого) количества превращений.

Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 2³⁰). Вторая строка набора входных данных содержит n целых чисел: a1, a2,...,an (0 <= ai < 2³⁰). Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 10⁴.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	2 3 3 4	7	Одной из оптимальных последовательностей действий является следующая: Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 3) = 3, а z становится равным (3 and 3) = 3. Выполнить операцию для i = 2. Теперь a2 становится равным (4 or 3) = 7,, а z становится равным (3 and 3) = 0. Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 0) = 3, а z становится равным (3 and 0) = 0. После этих операций последовательность a становится равной [3,7], и максимальное значение в ней равно 7. Можно доказать, что максимальное значение в a не может превосходить 7 ни при какой последовательности операций, так что ответ равен 7.
2	5 5 0 2 4 6 8	13

 У Громозеки есть n-1 целое число, записанные на карточках и разложенные в ряд в произвольном порядке. Он вычислил побитовый исключающий ИЛИ (xor) между всеми записанными числами. Вычисленное число (X) он записал на новую карточку и добавил ее в конец всех карточек с числами. Теперь у него есть n карточек с числами. Он перемешал все карточки и снова разложил их в ряд в произвольном порядке. 

Громозека показал вам все n карточек и просит вас угадать число X, которое было записано на новой карточке.

Входные данные
Первая строка входных данных содержит целое число n - количество карточек с числами (2 <= n <= 100). Вторая строка содержит n целых чисел - числа записанные на карточках (каждое число принадлежит промежутку [0, 127]). 

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

Примеры

№	Входные данные	Выходные данные
1	4 4 3 2 5	2

Громозека изучает битовые операции. Сегодня он изучит побитовую операцию И (&). Теперь ему стало интересно, при каком наибольшем целом значении k будет выполняться условие, записанное ниже.
 
Входные данные
Первая строка входных данных содержит целое число t (1 <= t <= 3*10⁴) - количество целых чисел x, для которых необходимо найти ответ. Далее программа получает t строк, в каждой из которых записано по одному целому числу x (1<= x <= 10⁹). 

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

Примеры

№	Входные данные	Выходные данные
1	3 2 5 17	1 3 15

Вы получили доступ к одной из камер наблюдения в особо секретной огранизации. В зоне видимости камеры находится табло, с которого вы постоянно считываете информацию. Теперь вам нужно написать программу, которая по состоянию табло определяет, какая буква изображена на нём в данный момент. Табло представляет из себя квадратную таблицу, разбитую на n × n равных квадратных светодиодов. Каждый диод либо включён, либо выключен. Введём систему координат, направив ось OX вправо, а ось OY — вверх, приняв сторону диода равной 1.
На табло могут быть изображены только следующие буквы:
• I — прямоугольник из горящих диодов.
• O — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом границы выключенного прямоугольника не должны касаться внешнего, то есть x1 < x3 < x4 < x2 и y1 < y3 < y4 < y2.
• C — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правая граница выключенного прямоугольника находится на правой границе внешнего прямоугольника, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 < y2.


• L — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правые верхние углы выключенного прямоугольника и внешнего прямоугольника совпадают, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 = y2.
• H — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом выключенные прямоугольники должны иметь одинаковую
ширину, находиться строго один под другим, один прямоугольник должен касаться верхней стороны, а другой прямоугольник должен касаться нижней стороны внешнего прямоугольника, то есть x1 < x3 = x5 < x4 = x6 < x2 и y1 = y3 < y4 < y5 < y6 = y2.


• P — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом правый нижний угол первого выключенного прямоугольника должен совпадать с правым нижним углом внешнего прямоугольника, а другой выключенный прямоугольник должен находиться строго выше и не касаться границ других прямоугольников, также левые границы двух выключенных прямоугольников должны совпадать, то есть x1 < x3 = x5 < x6 < x4 = x2 и y1 = y3 < y4 < y5 < y6 < y2.


• Любое другое состояние табло считается буквой X.
По виду табло определите, какая буква на нём изображена.

Входные данные
В первой строке входных данных находится одно число n (1 ≤ n ≤ 10) — сторона табло.
В следующих n строках находятся строки длины n из символов «.» и «#» — строки таблицы.
«.» обозначает выключенный квадратный диод табло, а «#» — горящий.

Выходные данные
Программа должна вывести единственный символ: если данная таблица подходит под одно из описаний букв I, O, C, L, H, P, то выведите её (все буквы — английские). Если же данная таблица не подходит ни под какие условия, то выведите X.

 Примеры

№	Входные данные	Выходные данные
1	4 .##. .##. .##. ....	I
2	5 #...# .#.#. ..#.. .#.#. #...#	X

Дан прямоугольник из N ×M квадратов. Назовём квадраты на границе прямоугольника крайними. Расстоянием от какого-либо квадрата до края назовём количество перемещений, которое нужно сделать из данного квадрата в соседний по стороне квадрат, чтобы добраться от данного квадрата до крайнего квадрата. Квадраты с максимальным расстоянием до края, будем называть центральными. При этом квадрат может быть одновременно и крайним, и центральным.
На рисунке изображён прямоугольник для N = 7 и M = 8, в каждом квадрате которого записано расстояние от этого квадрата до края. У этого прямоугольника два центральных квадрата.

По данным N и M определите количество центральных квадратов в прямоугольнике.
 

Примеры

№	Входные данные	Выходные данные
1	7 8	2

Математической моделью является:

1) модель автомобиля;
2) сборник правил дорожного движения;
3) формула закона всемирного тяготения;
4) номенклатура списка товаров на складе.

Сколько моделей может соответствовать одному объекту?

1) 1
2) 2
3) 10
4) много

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

1) предмет
2) знак
3) модель
4) образ

Укажите метод познания, заключающийся в создании и исследовании моделей.

1) формализация
2) проектирование
3) моделирование
4) умозаключение

Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город Ai и город Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.

• Пусть di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города a_i,1, ..., ai,di,перечисленных в порядке возрастания.
• I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.

Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 10⁵, 1 <= M <= 10⁵). Далее следует M строк, каждая из которых содержит 2 числа Ai и Bi (1 <= A_i < B_i <= N, 1 <= i <= M).
Если i≠j, то (Ai, Bi)≠(Aj, Bj). Все числа целые.

Выходные данные
Выведите N строк по формату, описанному в условии задачи.
 
 

Примеры

№	Входные данные	Выходные данные
1	6 6 3 6 1 3 5 6 2 5 1 2 1 6	3 2 3 6 2 1 5 2 1 6 0 2 2 6 3 1 3 5
2	5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5	4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

• 1 <= l <= r <= n;
• al = al+1 = al+2 =…=ar;
• l = 1 или al-1 > al;
• r = n или ar < ar+1;

Примеры 

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

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

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел ai (1 <= ai <= 10⁹) — количество решенных Лукой задач в i-й день .

Выходные данные
Выведите YES, если сборы Луки оказались эффективными, и NO в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	7 5 3 3 2 3 3 4	YES
2	11 2 2 2 3 4 4 5 6 7 7 8	YES
3	7 1 2 3 4 3 2 1	NO