Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 407 408 409 410 411 412 413 >> Отображать по:
#3898
Два капитана
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Капитаны Флинт и Джек Воробей нашли клад и хотят поделить его. Клад находится в шкатулке и состоит из чётного числа драгоценных камней. Капитан Флинт оценил \(i\)-ый камень в \(a_i\) пиастров, а Джек Воробей — в \(b_i\) долларов. Теперь они действуют следующим образом. Джек Воробей достаёт из шкатулки два камня, после чего Флинт забирает себе один из них (естественно, тот, у которого больше \(a_i\)). Оставшийся камень достаётся Воробью. После этого Джек Воробей достаёт ещё пару камней, и так далее: каждым ходом Воробей достает из шкатулки два камня, Флинт забирает себе камень с большим \(a_i\), оставшийся камень достается Воробью.

Джек Воробей знает все \(a_i\), все \(b_i\), а также может, доставая очередные два камня, подглядеть в шкатулку и выбрать, какие именно камни надо доставать. Помогите ему действовать так, чтобы доля Воробья была максимально возможной (т.е. чтобы сумма \(b_i\) полученных Воробьём камней была как можно больше).

По сравнению с камнями шкатулка ничего не стоит, поэтому её можно не учитывать при дележе.

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

Первая строка входного файла содержит одно целое число \(N\) — количество камней в кладе. Гарантируется, что \(N\) чётное и что \(2\leq N\leq 5000\). Далее следуют две строки по \(N\) целых чисел в каждой: сначала заданы все \(a_i\), потом — все \(b_i\). Гарантируется, что все \(a_i\) различны (т.е. что действия Флинта всегда однозначно определены). Гарантируется, что все \(a_i\) и все \(b_i\) положительны и не превосходят \(400\,000\).

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

В выходной файл выведите \(N/2\) строк по два числа в каждой — пары камней, в том порядке, как их должен доставать из шкатулки Джек Воробей. Камни нумеруются начиная с 1.

Числа в пределах каждой пары можете выводить в произвольном порядке. Если есть несколько оптимальных решений, выводите любое.

Примечание

Среди тестов будут такие, в которых каждый камень оба капитана оценивают одинаково: \(a_i=b_i\) для каждого \(i\) (как во втором тесте из примера); суммарная стоимость таких тестов будет 40 баллов.

Примеры
Входные данные
6
6 10 11 18 5 14
1 7 6 12 15 16
Выходные данные
5 1
2 3
6 4
Входные данные
6
6 44 2 43 7 48
6 44 2 43 7 48
Выходные данные
3 1
5 4
2 6
#3899
BWT
  
ограничение по времени на тест
0.15 second;
ограничение по памяти на тест
64 megabytes

Постройте все циклические сдвиги строки, отсортируйте их и выпишите последний столбец.

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

Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.

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

В первой строке выведите два числа - позицию (при нумерации с единицы) исходной строки в отсортированном массиве циклических сдвигов и длину строки. Во второй строке выведите последний столбец таблицы циклических сдвигов.

Примеры
Входные данные
irtucjb
Выходные данные
3 7
jubcirt
#3900
Система защиты
  
Темы: [Хеш]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

«ПермьОлимпБанк» разработал сверхнадежную систему защиты ценных бумаг. В правом верхнем углу любой бумаги должно присутствовать прямоугольное изображение в виде черно-белого рисунка. Для определения подлинности документов была создана библиотека контрольных элементов. Если документ подлинный, то в изображении на документе заданное количество раз присутствует каждый контрольный элемент из библиотеки. В библиотеке нет совпадающих элементов.

Система контроля после сканирования получает изображение в виде цифрового массива N × M, в котором цифра 1 соответствует черному цвету, а цифра 0 — белому. Затем система ищет контрольные элементы в полученном массиве.

Контрольный элемент представляется массивом размером L × L цифр, каждая из которых равна 0 или 1. В библиотеке — K контрольных элементов. Элемент библиотеки должен точно совпадать с какой-либо частью изображения. При сравнении изображения и контрольных элементов повороты не допускаются.

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

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

В первой строке входных данных записаны через пробел числа N, M, K, L (N ≤ 100 000, M ≤ 1 000, L ≤ 50, K ≤ 20).

Далее следуют по порядку К блоков, соответствующих элементам контрольного образца в библиотеке. Каждый блок состоит из L строк по L цифр (ноль или единица). После каждого блока следует пустая строка.

В последующих N строках записаны по M цифр в каждой, соответствующих изображению.

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

Выходной файл должны состоять из К строк.

В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 — если элемент не обнаружен).

Номер контрольного элемента из библиотеки в первой строке равен 1, во второй — 2 и т.д. Все числа в строках должны быть разделены пробелом.

Примечание

Каждый тест оценивается независимо от других.

Примеры
Входные данные
10 10 2 3
010
111
010

100
011
001

0010010010
0100001111
0000000100
0000100000
0001111000
0000101000
0100000010
0001000110
0011111000
0101000000
Выходные данные
1 2
2 1
#3902
Ежедневник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Васе подарили два ежедневника на i-й год. Один он использовал в i-м году и теперь интересуется, когда наступит следующий год с точно таким же календарем, чтобы он мог воспользоваться вторым ежедневником.

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

Вводится одно натуральное число i, не превышающее 2011.

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

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

Примеры
Входные данные
2011
Выходные данные
2022
Входные данные
1
Выходные данные
7
#4177
Деление нацело
  
Темы: [Остатки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Даны два целых числа a и b. Требуется найти неполное частное и остаток при делении a на b.

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

Во входных данных находятся два целых числа a и b (|a|, |b| ≤ 105, b ≠ 0).

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

Программа должна вывести два числа — неполное частное и остаток.

Примеры
Входные данные
19 4
Выходные данные
4 3
Страница: << 407 408 409 410 411 412 413 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест