Распечатки стека вызовов функций при ошибках — мощный инструмент отладки программ. Рассмотрим математическую модель взаимодействия между функциями в программе, которая называется граф вызовов. Пусть в программе \(n\) функций, которые могут вызывать друг друга. Обозначим все функции в программе числами от 1 до \(n\). Рассмотрим множество \(E\) пар чисел (\(f_i , g_i)\), где \(f_i\) и \(g_i\) — номера функций, такие, что \(f_i\) вызывает \(g_i\) . Размер этого множества будем называть сложностью графа вызовов.
Например, рассмотрим пример программы на примитивном языке программирования, в которой есть три функции.
function f(x)
if x > 0 then
return g(x)
else
return h(x)
function g(x)
return x
function h(x)
if x == 0 then
return 1 / x
else
return h(x + 1) + 1
Пронумеруем функции, пусть \(f\) имеет номер 1, \(g\) имеет номер 2 и \(h\) имеет номер 3. Тогда множество \(E\) выглядит следующим образом: \(E\) = {(1, 2),(1, 3),(3, 3)}, так как функция \(f\) вызывает
функции \(g\) и \(h\), функция \(g\) не вызывает других функций, а функция \(h\) вызывает себя. Сложность
графа вызовов этой программы равна 3.Распечатка стека вызовов при ошибке устроена следующим образом. Пусть в процессе выполнения программы произошла некоторая ошибка. Сначала в распечатку выводится номер функции \(i_1\), в которой произошла ошибка, далее выводится номер функции \(i_2\), из которой непосредственно была вызвана эта функция \(i_1\), далее номер номер функции \(i_3\), из которой была вызвана функция \(i_2\), и так далее.
Пусть, например, в приведенном выше примере программы был выполнен вызов \(f\)(−3). Тогда будет выполнен вызов \(h\)(−3), который выполнит \(h\)(−2), а далее в свою очередь \(h\)(−1) и h(0), в последнем вызове произойдет деление на 0. Тогда распечатка стека вызовов будет выглядеть так:
\(\)3\(\) \(\)3\(\) \(\)3\(\) \(\)3\(\) \(\)1\(\) Юра попросил Лёшу найти ошибку в его программе, прислав ему распечатку стека вызовов после ошибок. К сожалению, файл, который Юра прислал Лёше, содержит несколько распечаток стеков вызовов при различных ошибках, причем эти распечатки выведены подряд и никак не отделены друг от друга. При этом Юра утверждает, что ошибки могут происходить только в двух функциях, правда он не помнит, в каких.
Лёша понял, что ограничиться распечаткой стека вызовов не удастся, придется смотреть на программу. Но прежде чем это сделать, он хочет выяснить, какая минимальная сложность может быть у графа вызовов этой программы, если все утверждения Юры верны.
Помогите ему выяснить, какая может быть минимальная сложность графа вызовов программы, чтобы присланный ему файл мог содержать одну или несколько записанных подряд без разделителей распечаток стеков вызовов, а непосредственные ошибки происходили не более чем в двух различных функциях.
В первой строке находятся два целых числа \(n\) и \(m\) (\(1 \le n, m \le 100 000)\) — количество функций в программе Юры и количество строк в файле с распечатками стека вызовов, которые Юра прислал Лёше. В следующих m строках находятся по одному целому числу \(f_i\) (\(1 \le f_i \le n\)) — номер функции в \(i\)-й строке файла.
В первой строке выведите одно целое число \(k\) — минимальную возможную сложность графа вызовов программы Юры. В следующих \(k\) выведите по два целых числа \(a_i\) и \(b_i\) — такая пара означает, что функция с номером \(a_i\) может вызывать функцию с номером \(b_i\) . Если возможных вариантов графа вызовов несколько, выведите любой.
В примере возможна ситуация, что ошибки происходят только в функциях 1 и 3, а в приведенном файле содержится пять записанных подряд распечаток стеков вызовов. Ниже приведены те же распечатки, но разделенные пустой строкой. 1
3
3 2
3 2
1
В этом случае только функция 2 вызывает функцию 3, следовательно сложность графа вызовов равна 1.
3 7 1 3 3 2 3 2 1
1 2 3
Феоктист работает в обменном пункте на границе Флатландии и Байтландии. Каждый день он узнает по радио текущий курс обмена Флатландских флатов на Байтландские биты и вывешивает информацию об обменном курсе на дверях своего пункта.
В распоряжении Феоктиста есть \(n\) табличек, на которых записаны числа \(c_1, c_2, \dots , c_n\). Узнав сегодняшний курс обмена \(p\), Феоктист выбирает две таблички с значениями \(c_i\) и \(c_j\) , такими, чтобы значение \(c_i/c_j\) было как можно ближе к \(p\), и вывешивает их на двери, формируя таким образом объявление «меняю \(c_i\) флатов на \(c_j\) битов». Задача не из легких, и Феоктист решил её автоматизи- ровать.
Помогите Феоктисту по заданному курсу \(p\) найти две соответствующие таблички.
В первой строке входного файла заданы два целых числа \(n\) и \(p\) (\(2 \le n \le 100 000, 1 \le p \le 10^9\) ) — число табличек и текущий курс. Вторая строка содержит \(n\) целых чисел \(c_i\) (\(1 \le c_i \le 10^9\) ) — числа, записанные на табличках.
Выведите два целых числа \(i\) и \(j\) (\(1 \le i, j \le n, i \ne j\)) — номера двух табличек, таких что величина \(|(c_i/c_j ) − p|\) минимальна. Если таких пар несколько, то вы можно вывести любую из них.
3 2 1 6 3
2 3
4 3 2 3 4 5
4 1
На перемене перед уроком математики Рома решил поупражняться в определении простоты числа. Напомним, что простым называется натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Сначала он написал на доске первое простое число, после чего справа приписал к нему второе, затем третье и так далее. Всего Рома выписал на доску первые \(n\) простых чисел. В результате действий Ромы на доске появилось одно длинное число, которое начинается так: «23571113171923... ».
Когда в кабинет вошла Елена Евгеньевна, учительница Ромы, она предложила классу решить следующую задачку: вычеркнуть из написанного на доске числа \(k\) цифр так, чтобы оставшееся на доске число было максимальным.
Помогите Роме и одноклассникам решить предложенную задачу, чтобы не получить двойку от строгой учительницы.
Входной файл к этой задаче содержит несколько наборов тестовых данных. В первой строке входного файла задано число \(T\) — количество наборов в файле.
В следующих \(T\) строках идут описания наборов, каждое из которых состоит из двух целых положительных чисел \(n\) и \(k\). Гарантируется, что первые n простых чисел содержат в себе хотя бы \(k + 1\) цифру суммарно.
Сумма всех \(n\) во входном файле не превосходит 400 000.
Для каждого из тестовых наборов в отдельной строке выведите искомое максимальное число для соответствующих \(n\) и \(k\).
В первом тесте Рома выписал число 2357. Максимальное число, которое может получиться после вычеркивания из него двух цифр: 57.
Во втором тесте Рома выписал число 235711. Максимальное число, которое может получиться после вычеркивания из него трех цифр: 711.
2 4 2 5 3
57 711
Компания «Филипп индастриз» разрабатывает программу для нового робота-марсохода. Участок Марса, на котором будет работать робот, представляет собой квадратное поле размером \(n \times n\), разбитое на квадратные участки размером \(1 \times 1\), некоторые из которых могут содержать скалу \((1 \le n \le 1000\), не более 300 участков содержат скалу).
Введем на поле систему координат таким образом, что участки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), . . . ,(n, n)\). Программа для робота представляет собой последовательность инструкций, каждая из которых кодируется одной латинской буквой:
• «U» — переместиться с участка (x, y) на участок (x, y + 1).
• «D» — переместиться с участка (x, y) на участок (x, y − 1).
• «R» — переместиться с участка (x, y) на участок (x + 1, y).
• «L» — переместиться с участка (x, y) на участок (x − 1, y).
Для экономии инженеры записывают в память последовательность инструкций \(s\), пронумерованных от 1 до \(t\). Затем можно заставить робота выполнить подпрограмму — одну или несколько следующих подряд инструкций. Каждая подпрограмма, таким образом, характеризуется двумя целыми числами \((l, r)\) — номером первой и последней инструкции в подпрограмме.
В процессе лабораторного эксперимента робот был размещен на некотором участке тестового поля. Будем называть подпрограмму \((l, r)\) корректной, если при последовательном выполнении инструкций \(s[l], s[l + 1], \dots , s[r]\) робот не покидает поле и не перемещается на участок со скалой.
По описанию поля, программе для робота и его начальному положению определите, сколько у данной программы существует корректных подпрограмм.
В первой строке входного файла находятся два числа \(n\) и \(t\) (\(1 \le n \le 1000, 1 \le t \le 10^5\) ) — размер поля и количество инструкций в программе робота.
Во второй строке входного файла находится строка \(s\) длины \(t\) — программа робота. Гарантируется, что строка \(s\) состоит только из символов «U», «D», «R» и «L». Следующие \(n\) строк содержат по \(n\) символов в каждой и задают поле. Символ «.» означает, что участок пустой и по нему может перемещаться робот. Символ «#» означает, что на участке находится скала. Символ «@» означает, что в этой клетке находится стартовая позиция робота. Ось X направлена слева направо, ось Y — снизу вверх. Гарантируется, что символ «@» встречается ровно один раз, а символ «#» встречается не более 300 раз.
В единственной строке выходного файла выведите количество корректных подпрограмм.
В примере следующие подпрограммы являются корректными: (1, 1)=«U», (1, 2)=«UL», (1, 3)=«ULU», (3, 3)=«U», (3, 4)=«UR», (4, 4)=«R».
4 4 ULUR ..#. .... .#@. #.#.
6
Разбойники с большой дороги Джон и Боб ограбили караван и в качестве добычи получили три золотых слитка. Решив поделить добычу по-братски, Джон и Боб взвесили слитки и выяснили, что они весят \(x_1\), \(x_2\) и \(x_3\) фунтов, соответственно.
Теперь Джон и Боб хотят поделить слитки так, чтобы каждому из них досталось равное количество золота. Им не хотелось бы пилить слитки, но деваться некуда. Обсудив ситуацию, они решили, что если смогут, поделят добычу как есть, а если нет, то сумеют-таки распилить один слиток на две части. Распилить два или все три слитка они уже не смогут.
Помогите Джону и Бобу выбрать, какой слиток распилить на две части, и на какие части его следует распилить, чтобы после этого можно было поделить добычу поровну.
Первая строка входных данных содержит три целых числа: \(x_1\), \(x_2\) и \(x_3\) (\(1 \le x_i \le 10^8\) , сумма весов слитков чётна).
Если невозможно распилить один слиток таким образом, что после этого можно поделить золото поровну, выведите −1.
Если Джон и Боб и так могут поделить золото поровну, выведите 0.
В противном случае на первой строке выведите число 1, если следует распилить первый слиток, 2, если следует распилить второй слиток, либо 3, если следует распилить третий слиток. На второй строке выведите два положительных целых числа: веса частей, на которые следует распилить слиток. В сумме две части должны давать исходный вес слитка. Так как суммарный вес золота чётен, слиток всегда требуется распиливать на части, имеющие целый вес. Если возможных решений несколько, выведите любое.
2 3 3
2 2 1