--->
45 задач
<---
Источники
Имеется n банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды?
В первой строке даны два числа — n и V (1 ≤ n ≤ 105, 1 ≤ V ≤ 109). Во второй строке даны n чисел — объемы банок (1 ≤ Vi ≤ 109).
Выведите «YES», если можно, и «NO», если нельзя.
2 5
2 7
YES
2 5
2 4
NO
В первом примере мы можем набрать 7 литров во вторую банку, а потом вылить из нее 2 литра в первую. Оставшиеся 5 литров перельем в сосуд.
Зачет проводится в аудитории, в которой стоит один большой круглый стол, за которым ровно N мест; студентов в группе тоже ровно N. За время семестра преподаватель успел выделить несколько пар студентов, которые, по его мнению, могут списывать друг у друга, при этом каждый студент входит не более чем в одну такую пару. Теперь он хочет придумать такую рассадку для студентов, чтобы они все решали задачи самостоятельно.
Преподаватель считает, что списывать сложнее всего, если тот, у кого списывают, находится на расстоянии ровно L от того, кто списывает. Таким образом, преподаватель хочет рассадить студентов так, чтобы между каждыми двумя студентами, которые могут списывать друг у друга, сидело бы ровно L - 1 других студентов. Помогите преподавателю найти такую рассадку. Примечание. Ясно, что в зависимости от того, с какого именно из двух студентов начинать считать, и в зависимости от того, в какую сторону считать, получится разное количество человек, сидящих между ними. Преподавателю требуется лишь, чтобы для каждой пары, начиная с хотя бы какого-нибудь из этих двух студентов, хотя бы в какую-нибудь сторону до другого насчитывался бы ровно L - 1 студент.
Первая строка входного файла содержит три числа: N, L и K, где N — количество студентов в группе, L — оптимальное “антисписывательное” расстояние, а K — количество пар студентов, которые могут друг у друга списывать. Далее следуют K строк по два числа в каждой — номера студентов, входящих в очередную пару. Студенты нумеруются от 1 до N. Все числа во входном файле натуральные и не превосходят 8 000 гарантируется, что L ≤ N.
Если искомая рассадка существует, то выведите в выходной файл любой из возможных ответов, т. е. N чисел — номера студентов в порядке обходе стола против часовой стрелки, начиная с любого места. Если решения не существует, то выведите - 1.
5 3 2 1 4 2 3
1 2 5 4 3
Вася очень любит учиться, но некоторые уроки в школе—полная скукотища. Для того чтобы скрасить время, они с Петей придумали игру. Перед началом партии ребята пишут на листочке два различных натуральных числа aиb . Затем по очереди делают ход: среди записанных чисел выбирают p и q такие, что модуля их разности | p − q | еще нет на листке, и дописывают его. Проигрывает тот, кто не может сделать ход. Определите, кто из ребят окажется победителем при правильной игре обоих. Вася вежливый мальчик, поэтому всегда ходит вторым.
В первой и единственной строке записано два различных натуральных числа 1 ≤ a , b ≤ 10^9 , разделенные пробелом—два исходных числа на листке.
Выведите имя победителя
В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Вася может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Вася.
6 2
Petya
4 1
Vasya
Маша и Маша - лучшие подруги. Однажды Маша и Маша пошли по магазинам. Оказалось, что Маша не хочет заходить в каждый a -ый магазин, а Маша в каждый b -ый. Но так как Маша любит Машу как подругу, а Маша как подругу любит Машу, Маша и Маша не заходят в магазин, если в него не хочет заходить ни Маша, ни Маша. В сколько магазинов зайдут Маша и Маша, если на их пути было n магазинов.
Единственная строка содержит три целых числа — a , b , n ( 1 ≤ a , b , n ≤ 10 9 )
Выведите единственное число — количество посещённых магазинов
Программы, работающие корректно для n ≤ 1000 получат 40 баллов.
Программы, работающие корректно для n ≤ 10000 получат 70 баллов.
1 1 10
0
1 2 5
3
2 3 9
8
Легенда этой задачи слишком велика, чтобы она уместилась на этой странице, поэтому ее здесь не будет.
Вам дан массив \(V\) длины \(n\), и вы хотите уметь осуществлять над ним следующие операции:
1) get(\(a\), \(b\)) - узнать наибольший общий делитель чисел на отрезке от \(a\) до \(b\).
2) update(\(a\), \(b\), \(k\)) - для всех \(j\) от \(a\) до \(b\) увеличить \(j\)-е число на \(k \cdot (j - a + 1)\), т.е.
\(V_a += k\)
\(V_{a+1} += 2 \cdot k\)
...
\(V_b += (b - a + 1) \cdot k\)
Первая строка входного файла содержит два числа \(1 \le n \le 10^5\) - кол-во числе в массиве и \(1 \le q \le 10^5\) - кол-во запросов. Следующая строка содержит \(n\) чисел - массив \(V\) \(1 \le V_i \le 2 \cdot 10^8\).
Далее в \(q\) строках идет информация о запросах:
Каждый запрос get задается тремя числами 0 \(a\) \(b\)
Каждый запрос update задается четырьмя числами 1 \(a\) \(b\) \(k\) (\(1 \le k \le 2 \cdot 10^8\))
Для каждого запроса get выведите наибольший общий делитель чисел на отрезке от \(a\) до \(b\)
Подзадача 1(20 баллов) \(1 \le n \le 1000\), \(1 \le q \le 1000\)
Подзадача 2(20 баллов) нет запросов update
Подзадача 3(60 баллов) нет дополнительных ограничений
8 3 2 8 12 24 66 33 21 7 0 2 4 1 1 4 2 0 2 4
4 2