Темы
Информатика(2656 задач)
--->
36 задач
<---
Слон постоянно шалит в своей школе. На уроках ему становится скучно, и он начинает хулиганить. Учитель решил успокоить слона, поэтому дал ему очень сложную математическую задачу.
Учитаель дал слону арифметическое выражение A и числа P и M . Слону надо ответить на такой вопрос: "Каково минимальное неотрицательное значение переменной x в выражении A , такое что остаток от деления A на M равно P ?". Гарантируется, что решение всегда существует.
Кроме того, после применения законов распределения к выражению A , x содержится в A только в первой степени.
В первой строке содержится выражение A ( 1 ≤ | A | ≤ 10 5 ). Вторая строка содержит два целых числа P и M ( 0 ≤ P < M ≤ 10 6 ). A состоит только из символов +, -, *, (, ), x и цифр от 0 до 9. Каждый оператор +, -, * применяется ровно к двум значения, умножения всегда обозначены явно.
Выведите одно число – ответ на задачу
Пояснение к первому примеру:
(5 + 3 + x ) mod 10 при x = 0 равно 8.
(5 + 3 + x ) mod 10 при x = 1 равно 9. Значит, ответ x = 1 .
5+3+x 9 10
1
20+3+x 0 5
2
3*(x+(x+4)*5) 1 7
1
|
Дан массив a длины n , состоящий из натуральных чисел в диапозоне [1; k ] . Вам необходимо обработать 2 типа запросов:
1 p u — изменить значение элемента на позиции p на u .
2 — сообщить длину кратчайшего подотрезка, содержащего все числа от 1 до k или - 1 если такого подотрезка не существует.
В первой строке входного файла задано 3 целых числа n , k и m (1 ≤ n , m ≤ 10 5 , 1 ≤ k ≤ 50) — длина массива, максимальное число в массиве и число запросов, соответственно.
В следующей строке содержится n чисел (1 ≤ a i ≤ k ) — элементы массива.
В последующих m строках содержатся запросы в формате, указанном выше.
Для каждого запроса второго типа выведите ответ на него.
11 баллов — (1 ≤ n , m ≤ 40) .
47 балла — (1 ≤ n , m ≤ 5 000) .
42 балла — (1 ≤ n , m ≤ 10 5 ) потестовая оценка.
4 3 5 2 3 1 2 2 1 3 3 2 1 1 1 2
3 -1 4
Мирко получил в подарок на свой день рождения квадратный стол N x N , где в каждой клетке записано неотрицательное целое число. К сожалению, некоторые числа кажутся Мирко слишком большими, поэтому он собирается положить на стол K фишек домино, которые закроют некоторые слишком большие числа. Точнее, он собирается положить фишки домино в соответствии со следующими правилами:
1. Каждая фишка домино покрывает две клетки, соседних по строчке или столбцу..
2. Фишки домино не накладываются друг на друга (но могут соприкасаться).
3. Сумма чисел на всех видимых (непокрытых) клетках минимальна.
Ваша задача - определить минимально возможную сумму чисел на видимых клетках. Тесты к задаче таковы, что на поле всегда можно положить K не накладывающихся друг на друга фишек домино.
Первая строка содержит два целых числа: N ( 1 ≤ N ≤ 2000 ) - размер стола, и K ( 1 ≤ K ≤ 8 ) - количество фишек домино. Каждая из следующих N строк содержит N целых чисел (в диапазоне [0, 1000]) - числа в соответствующих клетках поля.
Выведите единственное целое число - минимально возможную сумму чисел в клетках после установки фишек домино.
Решения, работающие при K ≤ 5 , будут оцениваться в 70 баллов.
3 1 2 7 6 9 5 1 4 3 8
31
4 2 1 2 4 0 4 0 5 4 0 3 5 1 1 0 4 1
17
Дано 2 числа N и M , и их надо преобразовать следующим образом: выпишем их друг под другом (если числа имеют разную длину, дополним меньшее из них ведующими нулями) и будем сравнивать их отдельно в каждой цифре. Из того числа, где цифра меньше, эта цифра вычеркивается. Если цифры равны, то ничего не происходит. Если, в итоге, из числа вычеркнули все цифры, то вместо него надо вывести 'YODA' .
Найдите те числа, которые получатся в результате преобразования.
Первая строка содержит число N ( 1 ≤ N ≤ 10 9 ), первое из двух чисел.
Вторая строка содержит число M ( 1 ≤ M ≤ 10 9 ), второе из двух чисел.
В первой строке выходного файла выведите новое значение первого числа.
В второй строке выходного файла выведите новое значение второго числа.
Решения, в которых 100 ≤ N ≤ 999 , будут оцениваться в 30 баллов.
300 500
0 500
65743 9651
673 95
2341 6785
YODA 6785
Хан не хотел учиться один, поэтому он пригласил своего друга Доминика позаниматься вместе с ним. После того, как они решили рекордное количество задач за вечер, Доминик поехал домой. Внезапно его остановила полиция, подозревая, что он водил в пьяном виде. Чтобы проверить Доминика, полицейские начали задавать ему вопросы.
Полицейский: Давайте начнём с чего-то простого. Какова асимптотика сортировки пузырьком?
Доминик: О, это просто. O ( n 2 ) .
Полицейский: Скажите английский алфавит наоборот.
Доминик: Легко, zyxwvutsrqponmlkjihgfedcba.
Полицейский: Вы просто запомнили это. Представьте, что строчные буквы латинского алфавита записаны по кругу по часовой стрелке. Начинайте с буквы 'a' и называйте все буквы подряд. После каждой сказанной буквы я могу приказать теперь называть в обратном порядке, спросить сколько раз была названа какая-то буква или ничего не делать. Приступайте.
Доминик: Хм... a, b, c...
Возможно, Доминик не настолько трезв, чтобы решить эту задачу. Помогите ему.
Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) – количество приказов полицейского. Каждая из последующих Q строк содержит один из приказов в формате "SMJER n" или "UPIT n x". Приказ первого типа обозначает, что после n -й сказанной буквы требуется поменять направление. Приказ второго типа обозначает, что Доминик должен сказать, сколько раз он произнес букву x после n сказанных букв.
Во всех запросах 1 ≤ n ≤ 10 9 , а x – строчные латинские буквы. В запросах n идут в строго возрастающем порядке.
Для каждого запроса вида "UPIT n x", выведите ответ на этот запрос, каждый в отдельной строке, в том же порядке, что и в вводе.
40 баллов: n ≤ 1000
60 баллов: n ≤ 10 5
100 баллов: n ≤ 10 9
В первом примере Доминик говорит a, b, c, d, c, b, a, z, y, x.
Во втором примере Доминик говорит a, z, a, z, y, x, w.
5 UPIT 1 b UPIT 3 b SMJER 4 UPIT 7 a UPIT 10 z
0 1 2 1
5 SMJER 1 SMJER 2 SMJER 3 UPIT 5 a UPIT 7 w
2 1
4 UPIT 100 a UPIT 200 c UPIT 300 a UPIT 400 b
4 8 12 16