Страница: << 171 172 173 174 175 176 177 >> Отображать по:
#113519
Swap
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вам предоставляется последовательность из n чисел x 1 , x 2 , ..., x n . Каждое число 1, 2, ..., n появляется ровно один раз в последовательности.

Вы можете изменить последовательность с помощью свопов. Существует n - 1 последовательных "поворотов" пронумерованных k = 2, 3, ..., n . При "повороте" k вы можете либо менять значения x k и x ⌊ k / 2⌋ в последовательности, либо ничего не делать.

Последовательность a 1 , a 2 , ..., a n лексикографически меньше, чем последовательность b 1 , b 2 , ..., b n , если существует индекс j (1 ≤ j ≤ n ) такой, что a k = b k для всех k < j и a j < b j .

Какова минимальная лексикографическая последовательность, которую вы можете получить?

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

Первая строка ввода содержит целое число n.

Вторая строка ввода содержит n целых чисел: числа в последовательности.

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

Вы должны вывести n целых чисел: лексикографически минимальную последовательность.

Примечание

Подгруппа 1(10 баллов)

1 ≤ n ≤ 20

Подгруппа 2(11 баллов)

1 ≤ n ≤ 40

Подгруппа 3(27 баллов)

1 ≤ n ≤ 1000

Подгруппа 4(20 баллов)

1 ≤ n ≤ 5 * 10 4

Подгруппа 5(32 балла)

1 ≤ n ≤ 2 * 10 5

Примеры
Входные данные
5
3 4 2 5 1
Выходные данные
2 1 3 4 5
#113520
Лабиринт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Уолеви разработал игру, в которой игрок собирает монеты в лабиринте. На данный момент проблема в том, что игра слишком проста. Могли бы вы создать несколько сложных лабиринтов для игры? Каждый лабиринт представляет собой прямоугольную сетку, состоящую из полов (.) И стен (#). Одна из ячеек является базой (x), а некоторые ячейки могут содержать монеты (0). Игрок начинает в базе и может перемещаться влево, вправо, вверх и вниз. Задача игрока - собрать все монеты в лабиринте, а затем вернуться на базу. Трудность лабиринта - это длина кратчайшего пути, который начинается на базе, собирает все монеты и возвращается на базу.

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

Ввод начинается с целого числа t: количество лабиринтов. После этого следуют t строк. Каждая такая строка содержит три целых числа n, m и k. Это означает, что размер лабиринта должен быть n * m ячеeк, и должно быть ровно k монет.

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

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

Входные данные
2
3 3 1
4 7 2
Выходные данные
###
#.x
#o#

.o.####
.#..x.#
...##.#
###o...
Примечание

Трудность первого лабиринта - 4, а трудность второго лабиринта - 18.

Это задача только для вывода, и есть только один входной файл . Вы можете скачать входной файл здесь. Вы должны представить выходной файл, содержащий все лабиринты, указанные во входном файле.

Для каждого лабиринта ваш счет max(0, 100 - 3(d - x)) - где x трудность вашего лабиринта и d сложность самого сложного лабиринта, найденного жюри. Ваш общий балл для задания - это среднее значение всех оценок, округленное до целого.

#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
Страница: << 171 172 173 174 175 176 177 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест