Информатика

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

var n: integer;
begin
  n := {1};
  while n < {2} do
  begin
    writeln(n);
    n := n + {3};
  end;
end.

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

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

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

Формат входных данных
В первой строке входных данных задается число N (1 ≤ N ≤ 50) — количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк содержат по две пары целых чисел — координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

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

Примечание

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

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

Единственная строка входных данных содержит два натуральных числа через пробел. Значения чисел не превышают 10⁹.

Выходные данные
Выведите на экран результат выражения a+b.
 
 

Реализуйте структуру данных для эффективного вычисления номера максимального из нескольких подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (\(1 <= N <= 100000\)) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

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

Числа выводите в одну строку через пробел.

У Саши есть блокнот, состоящий из \(n\) листочков, пронумерованных от 1 до \(n\). На \(i\)-м листочке написано целое число \(a_i\).

Аня собирается разорвать блокнот на \(k\) частей, для этого она выбирает \(k-1\) число \(1 \le r_1 < r_2 < \ldots < r_{k-1} < n\) и разрывает блокнот так, что листки с 1 по \(r_1\)-й оказываются в первой части, листки с \((r_1+1)\)-го по \(r_2\)-й оказываются во второй части, и т.д., последняя \(k\)-я часть содержит листки с \((r_{k-1}+1)\)-го по \(n\)-й.

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

Формат входных данных
Первая строка ввода содержит два числа: \(n\) и \(k\) (\(2 \le k \le n \le 300\)). Вторая строка содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Формат выходных данных
На первой строке выведите максимальное значение суммы, которое удастся достичь Ане. На второй строке выведите значения \(r_1, r_2, \ldots, r_{k-1}\), которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

Примечание
В приведенном примере Аня разорвала блокнот на части \([1, 10, 2]\), \([8]\), \([9]\), \([3, 5, 4]\) и \([7, 6]\). Искомая сумма равна \(1 + 8 + 9 + 3 + 6 = 27\).

Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа \(n\) на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, \(9=1+2+2+4\) является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше не является интересным, а разбиение \(9=1+3+5\) — является.

Помогите Мише вывести все интересные разбиения числа \(n\) на слагаемые.

Формат входных данных
На ввод подается одно целое число \(n\) (\(1 \le n \le 80\)).

Формат выходных данных
Выведите все интересные разбиения числа \(n\) на слагаемые. Разбиения можно выводить в любом порядке. Соблюдайте формат из примера.

Сеня решил написать операционную систему. Для начала он планирует написать подпрограмму, которая будет рисовать рамки окон.

Поле для рисования представляет собой прямоугольник \(h \times w\) пикселей, строки занумерованы сверху вниз от 1 до \(h\), столбцы — слева направо от 1 до \(w\).

На поле последовательно рисуются \(n\) рамок, \(i\)-я рамка представляет собой границы прямоугольника с противоположными углами в точках \((r_{i,1}, c_{i,1})\) и \((r_{i,2}, c_{i,2})\).

Требуется вывести получившееся изображение в виде \(h\) рядов по \(w\) символов, пискель, который не был использован при изображении рамок, следует вывести с использованием символа <<.>>, а пиксели \(i\)-й рамки с использованием \(i\)-го символа латинского алфавита (первая рамка изображается буквами <<a>>, вторая — <<b>>, и т.д.)

Формат входных данных
Первая строка содержит целые числа \(h\), \(w\) и \(n\) — размеры поля и число рамок (\(2 \le h, w \le 80\), \(1 \le n \le 26\)). Следующие \(n\) строк содержат по четыре целых числа каждая: \(r_{i,1}, c_{i,1}, r_{i,2}\) и \(c_{i,2}\) (\(1 \le r_{i,1} < r_{i,2} \le h\),. \(1 \le c_{i,1} < c_{i,2} \le w\)).

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

Маша и Петя решили выяснить, чья комната больше. Машина и Петина комнаты имеют форму прямоугольников, причем Машина комната имеет размеры \(a\) на \(b\) метров, а Петина — \(c\) на \(d\) метров.

Напишите программу, которая определит, чья комната больше: Машина или Петина.

Формат входных данных
На ввод подается четыре натуральных числа, разделенных пробелами: \(a\), \(b\), \(c\) и \(d\) (\(1 \le a, b, c, d \le 1000\)).

Формат выходных данных
Если Машина комната больше, выведите латинскую букву <<M>>. Если Петина комната больше, выведите латинскую букву <<P>>. Если комнаты ребят имеют одинаковую площадь, выведите латинскую букву <<E>>.

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

Каждый день эксперимента устроен следующим образом. Рано утром профессор достает из контейнера все свои бактерии и помещает их в инкубатор, где бактерии начинают делиться. Вместо каждой бактерии образуется \(b\) новых бактерий.

После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее \(c\) бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.

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

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).

Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

Вам заданы числа \(n\) и \(k\). Требуется найти все способы представить число \(n\) в виде суммы неубывающих чисел Фибоначчи, причем кажое число разрешается использовать не более \(k\) раз.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \le n \le 100\)).

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

Формат выходных данных
Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

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

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз суммы всех значений в каждой строке образовали неубывающую последовательность. В случае равенства суммы всех значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

Переведите {1}  из десятичной системы счисления в двоичную систему счисления.

Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратных двум кратно K. Найдите такую подпоследовательность с максимальной суммой. 

Формат входных данных
В первой строке записаны два натуральных числа N и K (1 <= N <= 1 000 000, 1 <= K <= 100). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

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

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

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

На время тура вам предоставляется файл words.txt, содержащий перечисленные в алфавитном порядке 10 000 слов. Слова из этого файла будут использоваться при тестировании вашего решения. Это означает, что во всех тестах слова будут выбираться только из этого множества. Во время тестирования файл words.txt будет вашей программе недоступен.

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



Входные данные
Входные данные содержат список неповторяющихся слов по одному в строке, выбранных. Регистр букв в словах будет тем же, что и в файле words.txt.

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

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

Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и всегда меняют местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).

Пронумеруем напёрстки от \(0\) до \(2\) слева направо. То есть левый напёрстком имеет номер \(0\), средний номер \(1\), а правый номер \(2\). Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил \(n\) действий и в итоге шарик оказался под напёрстком \(x\). Под каким напёрстком находился шарик в самом начале?

Формат входных данных
В первой строке входных данных записано одно цело число \(n\) (\(1 \leq n \leq 2 \cdot 10^9\)) — количество действий, совершённых ведущим.

Во второй строке записано одно целое число \(x\) (\(0 \leq x \leq 2\)) — номер напёрстка, под которым оказался шарик через \(n\) действий.

Формат выходных данных
Выведите одно целое число от \(0\) до \(2\), означающее номер напёрстка, под которым находился шарик в самом начале.

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

1. Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.

2. Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.

3. Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.

4. Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.

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

Решения, верно работающие при \(n \leq 100\,000\) будут набирать не менее 50 баллов.

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

1. Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).

2. Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:
   
   

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

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

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

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