Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 498 499 500 501 502 503 504 >> Отображать по:
#113527
Encoding
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вася не только играет в компьютерные и настольные игры, но и решает олимпиадные задачи по программированию. Три года назад он зарегистрировался на одном очень популярном сайте—KodeForces (KF) и с тех пор уже сдал целых 11 задач из архива! Вася не намерен останавливаться на достигнутом и планирует решить еще 1-2 задачи в ближайший месяц - полтора.

Однако сейчас его мозг занят совсем другой проблемой. Раз в год на KF случается чудо — любой пользователь сайта может изменить свой логин (имя пользователя). «Такую возможность упускать нельзя!», — подумал Вася и решил сделать свой логин лаконичным , т.е. состоящим из одинаковых букв.

Однако в этом году все не так то просто... Изменять логин можно только согласно следующему правилу: можно выбрать все одинаковые буквы имени и заменить их все на предыдущую или последующую букву в алфавитном порядке. Например, можно заменить все e на d или f . При этом, z можно заменить на a или y , а a на z или b .

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

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

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

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

Выведите единственное число—минимальное количество действий, за которое можно сделать логин Васи лаконичным.

Примечание

В первом примере Вася может сначала заменить все буквы a на b , а затем буквы b на c . Т.е.aaac => bbbc => cccc.

Во втором примере Васе необходимо заменить все a на b , а затем изменить букву c на b . Т.е. bbaaaac => bbbbbbc => bbbbbbb.

Примеры
Входные данные
aaac
Выходные данные
2
Входные данные
bbaaaac
Выходные данные
2
#113529
Arkady's Game
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Аркадий и Алексей придумали новую игру. Листок клетчатой бумаги размером 2 N ×2 M клеток заполняется цифрами (по одной цифре в каждую клетку). Затем начинается собственно игра: тот, чья очередь ходить, разрезает листок пополам вдоль короткой стороны (или любой стороны, если листок квадратный), выбирает любую из половин и выбрасывает ее; оставшаяся половина передается другому игроку. При этом игрок получает очки за каждую пару клеток, бывших соседними до разрезания:

• если в соседних клетках были одинаковые цифры, то игрок получает 3 очка;

• если в соседних клетках были цифры одинаковой четности, то игрок получает 1 очко;

• если в соседних клетках были цифры разной четности, то игрок получает 0 очков.

Резать листок можно только по линиям, разделяющим клетки. Игра завершается, когда от листка остается одна клетка — ее разрезать нельзя. Побеждает тот, кто наберет больше очков. Аркадий ходит первым и его интересует, какую максимальную разницу между его очками и очками Алексея он может получить, если оба они будут играть оптимально. Аркадию и Алексею доступны только такие листки, у которых N и M отличаются не более чем на 1.

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

В первой строке записаны два целых числа N и M ( 0 ≤ N , M ≤ 10 , | N − M | ≤ 1 ). Данный листок имеет размеры 2 N ×2 M клеток. В следующих 2 N строках записано содержимое листка. В каждой строке записано 2 M десятичных цифр без пробелов. Каждая цифра соответствует одной клетке исходного листка.

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

Выведите единственное число — максимально возможную разницу между количествами очков Аркадия и Алексея.

Примечание

В первом примере Аркадий может разрезать квадрат по горизонтали, получив 2 очка (за пары 1, 3 и 2, 4). Оставив Алексею половинку с цифрами 1, 2, Аркадий не даст ему шанса заработать ни одного очка. Если же Аркадий разрежет исходный квадрат по вертикали, то он не получит ни одного очка, зато при разрезании любой из оставшихся половин ( или Во втором примере Алексей наберет больше очков, как бы не играл Аркадий. Первым ходом Аркадий может только разрезать листок по вертикали, не получив очков. Если отдать Алексею левую половину, то это позволит ему получить 6 очков, разрезав ее по вертикали (за пары 2, 2 и 1, 1). При этом Аркадию достанется листок , разрезание которого не принесет очков. Если же отдать Алексею правую половину исходного листка, то он сможет получить 1 очко, разрезав листок любым способом. Но для максимизации своего выигрыша Алексей разрежет листок по вертикали и отдаст Аркадию половинку , разрезание которой не принесет последнему очков. Итоговый счет 0:1 в пользу Алексея.

Примеры
Входные данные
1 1
12
34
Выходные данные
2
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113539
Продажа картин
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Продажа картин ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
32 megabytes

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).

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

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

Разбалловка для личной олимпиады

Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.

Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.

Примеры
Входные данные
2 2
1 1
1 1
1
1 1 1
Выходные данные
1
Входные данные
2 2
1 2
2 3
2
1 2 2
2 2 2
Выходные данные
4
4
Входные данные
4 2
1 2 3 4
1 2 3 4
1
4 1 1
Выходные данные
66
#113540
Игра Мирко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Игра Мирко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мирко большой любитель шахмат и программирования, но обычные шахматы уже наскучили ему, поэтому он начал экспериментировать и придумал свою игру. Он взял шахматную доску с N рядами и N столбцами и расположил на ней K ладей. Игра Мирко следует таким правилам: 1. У каждой ладьи есть своя сила, заданная натуральным числом. 2. Ладья видит все клетки поля в своем ряду и своем столбце кроме той, на которой стоит сама. 3. Клетка считается атакованной в том случае, если побитовый XOR сил всех ладей, которые видят эту клетку, положителен. Изначально Мирко некоторым образом расположил ладьи на поле, и теперь собирается сделать P перемещений. Каждый раз он будет брать одну ладью и ставить ее на другую клетку поля (при этом ладья не обязательно будет перемещена вдоль ряда или столбца в котором она стоит). После каждого перемещения, определите сколько клеток на поле атакованы.

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

Первая строка содержит 3 целых числа N , K , P ( 1 ≤ N ≤ 1000000000 , 1 ≤ K , P ≤ 10000 ). Каждая из следующих K строк содержит 3 натуральных числа R i , C i , X i ( 1 ≤ R i , C i ≤ N , 1 ≤ X i ≤ 1000000000 ), которые обозначают что на клетке ( R i , C i ) стоит ладья с силой X i . Каждая из следующих P строк содержит 4 натуральных числа R 1 , C 1 , R 2 , C 2 ( 1 ≤ R 1, C 1, R 2, C 2 ≤ N ), которые означают что ладья, стоящая на клетке ( R 1, C 1 ), была передвинута на поле ( R 2, C 2 ). Гарантируется, что в момент перемещения на клетке ( R 1, C 1 ) есть ладья и что ни в какой момент времени на одной клетке нет двух и более ладей.

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

Выведите P строк, где в k -й строке записано единственное число - количество клеток поля, атакованных после первых k перемещений.

Примеры
Входные данные
2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2
Выходные данные
4
0
Входные данные
2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2
Выходные данные
4
2
Входные данные
3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2
Выходные данные
6
7
7
9
Страница: << 498 499 500 501 502 503 504 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест