Ваня занимается работой с большими данными. Его проект занимается обработкой гигантских таблиц статистических данных. Ваня отвечает за разработку модуля преобразования таблиц, который выполняет перестановку строк, столбцов и ячеек таблицы.
Модуль занимается обработкой таблицы, состоящей из \(h\) строк и \(w\) столбцов, строки пронумерованы сверху вниз от \(0\) до \(h−1\), столбцы пронумерованы слева направо от \(0\) до \(w −1\). Ячейка в \(i\)-й строке, \(j\)-м столбце таблицы обозначается как \([i, j]\). Исходно ячейка \([i, j]\) содержит число \(i \times w + j\). На рис. 1. приведен пример исходного заполнения таблицы для \(h = 3,\ w = 5\).
Помогите Ване выполнить все операции и вычислить контрольную сумму таблицы, которая получится в итоге.
Поскольку входные данные для этой задачи слишком велики, чтобы задавать их непосредственно, для ввода вам потребуется процедура расширения массива. Эта процедура не имеет специфических особенностей, которые надо использовать в решении задачи, предполагаемое жюри решение этой задачи в явном виде генерирует все массивы и далее работает с ними так же, как если бы оно считало их из входных данных.
Опишем процедуру генерации массива длины \(n\) по массиву длины \(2 \le k \le n\). Пусть задан массив целых неотрицательных чисел \(A\) = (\(a[1]\), \(a[2]\), \(\dots\), \(a[k]\)).
Массив целых чисел \(Ax \ = \ (ax[1], \ ax[2], \dots, \ ax[n])\) будем называть расширением массива \(A\) по модулю \(r\) до размера \(n\), если его элементы вычисляются по следующим формулам.
- Если \(1 \le i \le k\), то \(ax[i] \ = \ a[i]\).
- Если \(k + 1 \le i \le n\), то \(ax[i] \ = \ (10007 \times ax[i − 2] + 10009 \times ax[i − 1] + 87277) \ mod \ r\).
Например, выполним расширение массива \(A\) = (1, 4, 3) до 5 элементов по модулю 13
\(ax[1] \ = \ a[1] \ = \ 1\).
\(ax[2] \ = \ a[2] \ = \ 4.\)
\(ax[3] \ = \ a[3] \ = \ 3.\)
\(ax[4] \ = \ (10007 \times ax[2] + 10009 \times ax[3] + 87277) \ mod \ 13 = 157332 \ mod \ 13 = 6.\)
\(ax[5] \ = \ (10007 \times ax[3] + 10009 \times ax[4] + 87277) \ mod \ 13 = 177352 \ mod \ 13 = 6.\)
Таким образом, \(Ax \ = \ (1, 4, 3, 6, 6)\).
Первая строка ввода содержит числа \(h\), \(w\), \(n\) — размеры таблицы и число преобразований, которые необходимо выполнить (\(1 \le h, w \le 5 000,\) \(2 \le n \le 10^6\) ).
Вторая строка содержит строку \(s\) длины \(n\) — последовательность типов преобразований, \(s[i]\) = «c» задает операцию обмена столбцов, \(s[i]\) = «r» — операцию обмена строк, \(s[i]\) = «f» — операцию обмена ячеек.
Следующие четыре строки задают массивы \(A\), \(B\), \(C\), \(D\), соответственно. Каждый массив задается числом \(k, 2 \le k \le n, k \le 1000\), после чего следует \(k\) чисел — элементы массива. Элементы массивов \(A\) и \(C\) удовлетворяют ограничению \(0 \le a[i], c[i] \le h − 1\), элементы массивов \(B\) и \(D\) удовлетворяют ограничению \(0 \le b[i], d[i] \le w − 1\).
Пусть \(Ax\) является расширением массива \(A\) по модулю \(h\) до размера \(n\), массив \(Bx\) является расширением массива \(B\) по модулю \(w\) до размера \(n\), массив \(Cx\) является расширением массива \(C\) по модулю \(h\) до размера \(n\) и массив \(Dx\) является расширением массива \(D\) по модулю \(w\) до размера n.
Операции, которые требуется выполнить с таблицей, определяются следующим образом: тип \(i\)-й операции задается символом \(s[i]\), а параметры получаются из массивов \(Ax\), \(Bx\), \(C\)x, \(Dx\).
- Если \(s[i]\) = «c», то \(i\)-я операция «c Bx[i] Dx[i]»;
- Если \(s[i]\) = «r», то \(i\)-я операция «r Ax[i] Cx[i]»;
- Если \(s[i]\) = «f», то \(i\)-я операция «f Ax[i] Bx[i] Cx[i] Dx[i]»;
Выведите одно число — контрольную сумму таблицы после выполнения всех преобразований.
3 5 3 crf 3 0 0 0 3 0 0 1 3 0 1 1 3 1 0 2
564830737
Это интерактивная задача.
В Далёкой-Далёкой Галактике \(10^{18}\) планет, и все они пронумерованы натуральными числами от 1 до \(10^{18}\) .
В Архивах джедаев были сохранены сведения о всех планетах Галактики: по кругу в огромном зале были расположены ячейки, пронумерованные против часовой стрелки от 1 до \(10^{18}\). Исходно Архивы были устроены очень просто: в ячейке с номером \(i\) хранились сведения о планете с номером \(i\). Поэтому, зная лишь номер планеты, всегда можно было легко найти информацию о ней.
Вот и Оби-Вану Кеноби понадобилось узнать координаты планеты Камино, которая имеет номер \(x\). Однако, заглянув в Архивы, он с удивлением обнаружил, что кто-то удалил из Архивов m ячеек со сведениями о некоторых планетах. Кроме того, оставшиеся ячейки были заново пронумерованы, начиная с 1, против часовой стрелки (возможно, начиная не с той, с которой они нумеровались исходно), и теперь в ячейке с номером \(i\) могут храниться сведения о совсем другой планете.
Оби-Ван в затруднении. Ему нужно срочно найти данные о планете Камино. Оби-Ван может проверить содержимое ячейки и узнать, данные о какой планете в ней находятся. У Оби-Вана мало времени, поэтому он может проверить содержимое не более чем десяти ячеек.
Помогите ему выяснить, в какой ячейке находятся данные о планете Камино, если, конечно, они не были удалены из Архивов.
Сначала вашей программе подаётся на вход в отдельной строке два числа: \(x\) — номер планеты Камино (\(1 \le x \le 10^{18}\)) и \(m\) — число удаленных из Архивов ячеек (\(0 \le m \le 500\)).
После этого ваша программа может делать запросы: «посмотреть, сведения о какой планете записаны в ячейке номер v». Для этого нужно вывести в выходной поток на отдельной строке «? v» (\(1 \le v \le 10^{18} − m\)). В ответ на запрос во входном потоке на отдельной строке будет записано одно число — номер планеты, сведения о которой записаны в ячейке \(v\). Вы можете сделать не более десяти таких запросов, иначе ваша программа получит вердикт «Wrong answer».
В конце вы должны вывести в выходной поток «! a», где \(a\) — это номер ячейки, в которой записаны сведения о планете Камино. Если данные о планете Камино были удалены из Архива, то следует вместо номера ячейки вывести −1, таким образом последнее сообщение должно быть «! -1».
После каждого действия вашей программы выводите символ перевода строки. Если вы используете «writeln» в Паскале, «cout << ... << endl» в C++, «System.out.println» в Java или «print» в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать «flush» не обязательно. Если вы используете другой способ вывода, рекомендуется делать «flush», но все равно обязательно требуется выводить символ перевода строки.
Ниже приведены наиболее типичные причины получения тех или иных сообщений об ошибке.
Если ваша программа соблюдает протокол, но неверно определяет искомый номер ячейки либо выполняет слишком много запросов, вы получите результат «Wrong Answer».
Если ваша программа выводит некорректно отформатированные сообщения программе жюри, то вы получите результат «Presentation Error» либо «Wrong Answer».
Если ваша программа нарушила протокол и ждет ввода в то же время, когда его ждет и программа жюри, то вы получите результат «Idleness Limit Exceeded». Обратите внимание, что к такому же результату может привести и то, что вы не переводите строку после каждого выведенного сообщения или выводите не тем способом, который описан в начале раздела, и не делаете «flush».
При входных данных:
16 3 10 12 13 16выход будет следующим:
? 1 ? 2 ? 3 ? 4 ! 4В примере из Архива были удалены данные о планетах с номерами 11, 14 и 15, а ячейки были перенумерованы, начиная с ячейки, содержащей сведения о планете с номером 10.
В Федеральном Университете Флатландии открылся музей спортивных достижений. Главная гордость этого музея — зал, в котором расположены сувениры со всевозможных соревнований по спортивному программированию.
Программирование становится всё популярнее, и заинтересованных посетителей этого зала становится всё больше, поэтому директор музея начинает беспокоиться о сохранности своих сувениров. Для начала директор решил оградить одну или две зоны с сувенирами от посетителей так, чтобы они не могли свободно бродить между ними, а могли лишь смотреть со стороны.
Зал имеет форму выпуклого многоугольника, а сувениры — это точки внутри этого многоугольника. Директор хочет выбрать один или два треугольника с вершинами в углах зала, так чтобы эти треугольники не имели общей внутренней части (то есть площадь их пересечения была равна нулю), а каждый сувенир оказался внутри одного из треугольников.
Директор хочет доставить посетителям как можно меньше неудобств, поэтому суммарная площадь выбранных треугольников должна быть минимальной, при этом площадь каждого треугольника должна быть строго положительной.
Помогите директору оградить экспонаты.
Входные данные содержат один или несколько тестовых примеров.
В первой строке находится число \(t\) — количество тестовых примеров. Далее следуют \(t\) блоков, каждый из которых выглядит следующим образом.
В первой строке блока находится два целых положительных числа \(n\) и \(m\) — количество вершин в многоугольнике, форму которого имеет зал, и количество сувениров в зале (\(3 \le n \le 2000, 1 \le m \le 2000\)).
В следующих \(n\) строках находятся по два целых числа \(xh_i \ и \ yh_i\) — координаты вершин многоугольника в декартовой системе координат (\(−10^9 \le xh_i , yh_i \le 10^9\) ). Вершины даны в порядке обхода против часовой стрелки.
В следующих \(m\) строках находятся по два целых числа \(xs_i , ys_i\) — координаты сувениров (\(−10^9 \le xs_i , ys_i \le 10^9\) ) .
Гарантируется, что все сувениры находятся строго внутри зала, а также что никакие три из данных \(n + m\) точек не лежат на одной прямой. Сумма всех \(n\) и сумма всех \(m\) во всех тестовых примерах одних входных данных не превосходят 2000 каждая.
Для каждого из \(t\) тестовых примеров выведите следующее.
Если невозможно выбрать один или два треугольника требуемым образом, выведите в отдельной строке −1.
Иначе выведите в первой строке целое число \(k \ (1 \le k \le 2)\) — количество выбранных треугольников, и в каждой из следующих \(k\) строк выведите по три целых числа — номера вершин зала, которые являются вершинами треугольника.
Если оптимальных ответов несколько, выведите любой из них.
Обратите внимание, что требуется минимизировать только суммарную площадь выбранных тре- угольников.
На рисунке показаны оптимальные способы выбрать треугольники в первом и третьем тестовых примерах, а также расположение сувениров во втором тестовом примере, где выбрать один или два треугольника нельзя.
3 4 1 0 0 5 0 4 4 0 4 2 3 5 3 0 0 6 -6 11 0 8 4 3 4 3 2 7 3 8 -2 8 4 -4 -4 0 -7 4 -4 6 0 4 4 0 7 -4 4 -6 0 -2 -5 2 -5 3 2 -3 2
1 1 4 3 -1 2 1 3 2 4 8 6
Петя — обычный мальчик. Каждый раз перед началом каждого учебного года у него появляется желание взяться за ум. И в этом году он не отступил от своей цели сразу после начала учебы. Внимательно слушая учителя и выполняя все домашние задания, он стал лучшим учеником в классе.
Учитель заметил успехи Пети и выдал ему самый сложный вариант контрольной по математике. Почти все задания мальчик решил за урок, но с одной так и не справился.
Дано целое положительное число \(x\). Требуется найти число \(y > x\), у которого не менее 100 делителей. Причем число \(y\) должно превышать число \(x\) не более чем на 1%, то есть должно выполняться неравенство \(x \le y \le 1.01x\).
Помогите Пете решить эту сложную задачу.
Первая строка ввода содержит число \(x \ (1 \le x \le 10^{16})\).
Если подходящего числа не существует, то выведите −1, иначе выведите любое подходящие число.
Число 510510 имеет ровно 128 делителей.
5
-1
510000
510000
Перед очередной лекцией на всемирной конференции полиглотов ее участники собрались в небольшой комнате. Всего в комнате \(n\) человек, каждый из которых разговаривает на некоторых из \(k\) языков. По стечению обстоятельств, все из них оказались интровертами, а поэтому общению с другими участниками предпочитают мирное прочтение книги.
Иногда, однако, один участник конференции решается-таки сообщить какую-то информацию другому. Два человека могут поговорить либо напрямую, либо через цепочку посредников. При общении напрямую два человека могут выбрать любой язык, которые знают оба собеседника. При общении через цепочку посредников любые два соседних человека в цепочке должны выбрать язык, на котором они будут говорить, среди тех, который знают оба собеседника. Таким образом, тот, кто хочет передать информацию, расскажет её первому посреднику, тот затем расскажет её второму посреднику, и так далее, пока информация не дойдёт до того, кому она предназначается.
Однако, когда происходит общение на каком-то языке, все в комнате, кто знает этот язык, слышат разговор на знакомом языке и отвлекаются от своей книги. Тот, кто передает информацию, хочет потревожить как можно меньше людей, поэтому планирует цепочку посредников таким образом, чтобы как можно меньше людей отвлеклось во время передачи информации.
Найдите для каждой пары людей \((A, B)\), какое минимальное людей можно отвлечь, чтобы передать информацию от \(A\) к \(B\).
В первой строке входных данных содержатся 2 числа \(n\) и \(k\) — число людей в комнате и число различных языков, на которых они разговаривают (\(2 \le n \le 300\), \(1 \le k \le 300\)).
Следующие \(n\) строк содержат описания людей, \(i\)-я из этих строк описывает языки, которые знает \(i\)-й человек, в следующем формате: \(k_i a_{i,1} a_{i,2} \dots a_{i,k_i}\) — количество языков и сами языки в порядке возрастания номеров (\(1 \le k_i \le k, 1 \le a_{i,j} \le k, a_{i,j} < a_{i,j+1}\)).
Выведите \(n\) строк, в каждой по \(n\) чисел \(f_{i,j}\) , разделенных пробелами — минимальное количество людей, которые отвлекутся при оптимальном способе передаче информации от \(i\)-го человека к j\(-\)му. На главной диагонали должны стоять нули. Если передать информацию от \(i\)-го человека к \(j\)-му невозможно, выведите вместо соответствующего числа −1.
6 4 2 1 2 2 2 3 1 2 1 1 2 3 4 1 4
0 3 3 2 4 5 3 0 3 4 2 3 3 3 0 4 4 5 2 4 4 0 5 6 4 2 4 5 0 2 5 3 5 6 2 0
4 3 2 1 2 1 1 1 2 1 3
0 2 2 -1 2 0 3 -1 2 3 0 -1 -1 -1 -1 0