Информатика

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
 
 
 (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) \/ (x + A ≥ 70)
 
 
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; и пусть на числовой прямой дан отрезок B = [40; 50].
Для какого наибольшего натурального числа А формула
 
 
ДЕЛ(x, A) \/ ((x ∈ B) → ¬ДЕЛ(x, 11))
 
 
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
 
 
 (ДЕЛ(x, 2) → ¬ДЕЛ(x, 3)) \/ (x + A ≥ 100)
 
 
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; и пусть на числовой прямой дан отрезок B = [50; 70].
Для какого наибольшего натурального числа А формула
 ДЕЛ(x, A) \/ ((x ∈$$ B) → ¬ДЕЛ(x, 16))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; и пусть на числовой прямой дан отрезок B = [50; 60].
Для какого наибольшего натурального числа А формула
 ДЕЛ(x, A) \/ ((x $\in$ B) → ¬ДЕЛ(x, 13))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; и пусть на числовой прямой дан отрезок B = [50; 70].
Для какого наибольшего натурального числа А формула
 ДЕЛ(x, A) \/ ((x $\in$ B) → ¬ДЕЛ(x, 21))
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
 

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например,
14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.
 
Для какого наименьшего неотрицательного целого числа А формула
 
((x & 52 ≠ 0) /\ (x & 36 = 0)) → ¬ (x & А = 0)
 
тождественно истинна (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?
 

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например,
14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.
 
Для какого наименьшего неотрицательного целого числа А формула
 
((x & 42 ≠ 0) /\ (x & 34 = 0)) → ¬ (x & А = 0)
 
тождественно истинна (т.е. принимает значение 1) при любом неотрицательном целом значении переменной х?
 

Для какого наименьшего целого неотрицательного числа А логическое выражение
(x≥12) \/ (3x < y) \/ (xy <A)
тождественно истинно (т.е. принимает значение 1) при любых целых неотрицательных x и y?
 

Для какого наибольшего целого неотрицательного числа А выражение
 
(x > A) \/ (y > A) \/ (y < x − 2) \/ (y > 2x − 10)
 
тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?
 

Для какого наименьшего целого неотрицательного числа A выражение
 
(x + 2y < A) \/ (y > x) \/ (x > 60)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
 

Для какого наибольшего целого неотрицательного числа A выражение
 
(y + 3x > A) \/ (x < 30) \/ (y < 30)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
 

Для какого наибольшего целого неотрицательного числа A выражение
 
(3x + 2y > A) \/ (y < x) \/ (x < 10)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
 

Для какого наименьшего целого неотрицательного числа A выражение
 
(x < A) \/ (y < A) \/ (x + 2y > 50)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?
 

Для какого наименьшего целого неотрицательного числа A выражение
 
(y + 2x < A) \/ (x > 25) \/ (y > 25)
 
тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая "— оленей, третья "— белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно бОльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

В первой строке входных данных записано целое число \(t\) — количество лет (\(1 \le t \le 100\)). В каждой из последующих \(t\) строк записано целое число \(n_i\)"— общая сумма грантов, которую необходимо полностью распределить в \(i\)-м году.

Выходные данные должны содержать \(t\) строк по три целых числа в каждой — суммы грантов, которые следует выделить каждой из трёх организаций в соответствующий год. Если оптимальных вариантов распределения несколько, необходимо вывести любой из них.

На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.

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

Для \(i\)-й фотографии известно максимальное количество пингвинов \(k_i\), изображение которых могло попасть на характерную полосу. Поэтому эту полосу пикселей необходимо заменить на упрощённую полосу той же длины, которая будет состоять не более чем из \(k_i\) отрезков, каждый из которых либо полностью чёрный, либо полностью белый. Из всех возможных упрощённых полос нужно выбрать оптимальную — то есть ту, которая получается из характерной путём изменения цвета минимального числа пикселей.

Требуется написать программу, решающую поставленную задачу.

Входные данные
В первой строке входных данных содержится число \(t\) — количество фотографий. Далее следуют \(t\) пар строк, \(i\)-я пара строк описывает \(i\)-ю фотографию.

Первая строка описания фотографии содержит два числа: \(n_i\) — длину характерной полосы \(i\)-й фотографии, и \(k_i\) — максимальное количество пингвинов, которые могут быть на ней изображены (\(k_i \le n_i\)).

Вторая строка описания состоит из \(n_i\) символов 0 и 1, где 0 обозначает чёрный, а 1 — белый пиксель.

Выходные данные
Выходные данные должны содержать \(t\) строк, где \(i\)-я строка состоит из \(n_i\) символов 0 и 1 и описывает упрощённую полосу, полученную из характерной полосы \(i\)-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера \(1 \times k\). Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты \((0, 0)\), то левые нижние углы плиток будут иметь координаты \((i \cdot k+j,j)\) для всех целых \(i\) и \(j\).

На площади было решено установить памятник известному архангельскому писателю и художнику Писахову. Для установки памятника необходимо удалить все плитки, полностью или частично попадающие под его основание. Основание памятника имеет форму многоугольника с целочисленными координатами вершин, все стороны которого параллельны осям координат. Известно, что любая прямая, пересекающая основание памятника и параллельная одной из осей координат, в пересечении с основанием образует один отрезок.

Для установки памятника необходимо выбрать место на площади таким образом, чтобы количество удалённых плиток было минимальным. При выборе места основание разрешается только передвигать параллельно осям координат.

Требуется написать программу, вычисляющую минимальное количество плиток, которые придётся .

Входные данные
Первая строка входных данных содержит два числа \(n\) и \(k\) — количество вершин в основании памятника и размер плитки.

Каждая из последующих \(n\) строк содержит два целых числа \(x_i\), \(y_i\) — координаты \(i\)-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

Замечание

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

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

Требуется написать программу, которая по данным \(n\) тройкам \((a_i, b_i, c_i)\) значений характеристик каждого из пользователей определяет количество пар потенциальных друзей, то есть таких пар индексов \(i < j\), что из трёх равенств \(a_i = a_j\), \(b_i = b_j\), \(c_i = c_j\) выполняется ровно одно.

Входные данные
Первая строка входных данных содержит число \(n\) — количество пользователей (1 ≤ n ≤ 100 000). Каждая из последующих \(n\) строк содержит три целых положительных числа \(a_i\), \(b_i\) и \(c_i\) — значения характеристик \(i\)-го пользователя (1 ≤ a_i , b_i , c_i ≤ 100)

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

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

Дано натуральное число N. Требуется представить его в виде суммы двух натуральных чисел A и B таких, что НОД (наибольший общий делитель) чисел A и B — максимален.

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

Входные данные
Во входных данных записано натуральное число N (2 ≤ N ≤ 10⁹)

Выходные данные
Выведите два искомых числа A и B. Если решений несколько, выведите любое из них.