РИВ. Разделяй и властвуй (1). Задача A. Количество инверсий
 Скачать 137.96 Kb.
|
|
Задача A. Количество инверсий Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 3 секунд Ограничение по памяти: 64 мегабайта Напишите программу, которая для заданного массива A = ha 1 , a 2 , ..., a n i нахо- дит количество пар (i, j) таких, что i < j и a i > a j Обратите внимание на то, что ответ может не влезать в 32-битный тип данных. Используйте long long в C++. Формат входных данных Первая строка входного файла содержит натуральное число n (1 6 n 6 100 000) количество элементов массива. Вторая строка содержит n попарно различных элементов массива A целых неотрицательных чисел, не превосходящих 10 9 Формат выходных данных В выходной файл выведите одно число ответ на задачу. Примеры stdin stdout 5 6 11 18 28 31 0 8 999994 999989 999982 999972 999969 999961 999954 999950 28 Задача B. Сокровища Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 2 секунд Ограничение по памяти: 64 мегабайта Дочь короля Флатландии собирается выйти за прекрасного принца. Принц хо- чет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать. В коллекции принца n бриллиантов, каждый характеризуется весом w i и сто- имостью v i . Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит брилли- антов суммарным весом меньше L. Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимо- сти, чтобы суммарный вес был в отрезке [L, R]. Формат входных данных Первая строка содержит число n (1 6 n 6 32), L и R (0 6 L 6 R 6 10 18 ). Следующие n строк описывают бриллианты и содержит по два числа вес и стоимость соответствующего бриллианта (1 6 w i , v i 6 10 15 ). Формат выходных данных Первая строка вывода должна содержать k количество бриллиантов, которые нужно подарить принцессе. Вторая строка должна содержать номера даримых бриллиантов. Бриллианты нумеруются от 1 до n в порядке появление во входных данных. Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода. Примеры stdin stdout 3 6 8 3 10 7 3 8 2 1 2 Задача C. Небоскрјбы Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 2 секунд Ограничение по памяти: 256 мегабайта Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом. Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева на- право. Для i -го небоскреба, известна его высота H i и количество золотых монет G i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскре- бов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрјб, находящийся справа от него, но так, чтобы высота нового небоскрјба была не меньше того небоскрјба, на котором сейчас сидит Брани- мир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возмож- но, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень. Бранимир хочет узнать, сколько существует способов сыграть в эту игру так, чтобы перейти на следующий уровень. Две игры называются разными, если суще- ствует небоскреб который был посещен в одной игре, но не был посещјн в другой. Формат входных данных Первая строка содержит 2 натуральных числа N и K ( 1 6 N 6 40 , 1 6 K 6 4 · 10 10 ) число небоскрјбов и количество монет, которые надо набрать соответственно. Следующие N строк содержат информацию о небоскрјбах. В i -й строке даны 2 числа H i и G i ( 1 6 H i , G i , 6 10 9 ) высота и количество монет на i -м небоскрјбе. Формат выходных данных В единственной строке вывода выведите число возможных игр, в которых Бра- нимир сможет пройти на следующий уровень. Примеры stdin stdout 4 6 2 1 6 3 7 2 5 6 3 2 7 4 6 3 5 0 4 15 5 5 5 12 6 10 2 1 4 Задача D. Ближайшая пара точек Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 2 секунд Ограничение по памяти: 64 мегабайта На плоскости задана совокупность точек. Гарантируется, что никакая пара то- чек не совпадает. Напишите программу, находящую минимальное среди всех рас- стояний между этими точками, иначе говоря расстояние между парой ближай- ших точек. Формат входных данных Первая строка содержит целое количество точек n (2 6 n 6 123456), затем следуют n строк, каждая из которых содержит разделјнные пробелом x- и y- координаты точки (целые числа, не превышающие по модулю 10 8 ). Формат выходных данных Программа должна вывести единственное число найденное минимальное рас- стояние. Ответ будет засчитываться, если относительная погрешность не превысит 10 ?9 Примеры stdin stdout 3 1 4 -1 1 3 2 2.8284271247 Задача E. Восстановление числа Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 2 секунд Ограничение по памяти: 64 мегабайта Мистер Саламандер едет в поезде. Он записал два числа n и m и отлучился. Когда он вернулся, оказалось, что его чай залил некоторые цифры числа n. Мистер Саламандер любит головоломки, поэтому ему стало интересно: какой наименьший остаток от деления на m могло давать исходное число n? Вам дана строка, представляющее залитое число n, в которой на каждой пози- ции находится либо цифра, либо знак вопроса, обозначающий, что данная цифра залита чаем, и модуль m. Формат входных данных В первой строке находится непустая строка n и натуральное число m модуль (1 6 m 6 10 9 ). Cтрока n состоит из цифр и знаков вопроса, не имеет ведущих нулей, и ее длина не превосходит 14. Формат выходных данных В единственной строке выведите наименьший остаток от деления, который мож- но получить, заменив знаки вопросов на цифры, так, чтобы получившееся число не имело ведущих нулей. Примеры stdin stdout 3?1? 3215 0 ?? 20 0 ?1? 730 80 Задача F. Дружелюбные хомячки Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 3 секунд Ограничение по памяти: 256 мегабайта На плоскости живут n хомячков. Каждый в точке с целыми координатами. Хомячки дружат, если существует прямоугольник со сторонами, параллельными осям координат, содержащий этих двух хомячков и не содержащий никаких дру- гих. Прямоугольник содержит хомячка, если точка, в которой он живет, лежит внут- ри прямоугольника или на его границе. Сколько пар хомячков дружат? Формат входных данных На первой строке число n, 1 6 n 6 100 000. Следующие n строк содержат по два целых числа координаты точек, в кото- рых живут хомячки. Все точки различны, а координаты целые, по модулю не превосходят 10 9 Формат выходных данных Выведите одно целое число количество пар дружащих хомячков. Примеры stdin stdout 5 0 0 0 2 2 0 2 2 1 1 8 |