Ограничение по памяти – 256 Мб

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

И теперь художественный руководитель хочет знать, сколько разных вариантов начальной позиции он может придумать.

 

Входной файл

В единственной  строке входного файла содержатся целое число N (1  ≤  N ≤ 500).

 

Выходной файл

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

 

Примеры входных и выходных данных

 

dancing. in	dancing. out
1	1
3	14

 

 

Задача «Торрент» (от 2 до 6 баллов)

Имя файла с исходными данными   films. in

Имя файла с результатом работы программы     films. out

Ограничение по времени работы программы – 2 секунды

Ограничение по памяти – 256 Мб

Торрент (BitTorrent) – это интернет-протокол, позволяющий быстро скачивать большие файлы. В отличие от скачивания с обычного сайта, при использовании торрента файл забирается по кусочкам у большого количества пользователей. Но сервер все же есть, только он играет роль распределителя, который направляет и координирует, чтобы не было путаницы.  

Однако, путаницу могут вносить сами пользователи. Пусть на некотором торрент-трекере, в который пользователи скидывают торренты фильмов, разрешили всем пользователям называть фильмы под таким названием, под которым они запомнили название фильма. Например, пользователи один и тот же фильм могут указать под оригинальным или транслитерируемом, например, «Аватар» или «Avatar». Так же у одного фильма на сервере может быть несколько раздач с одинаковым названием. После того, как фильм появился на торренте, пользователи ставят «лайки», если фильм понравился, и «дизлайки» – если нет.

В данный момент на торренте в списке N фильмов. Нужно навести какой-то порядок, составить списки похожих по названию фильмов, отсортировать их по разнице «лайков» и «дизлайков», удалить фильмы, у которых нет лайков и есть дизлайки и т.д. Назовем разницу лайков и дизлайков рейтингом фильма.

Задач для наведения порядка на торренте много. В зависимости от уровня решения задачи Вы получите разное количество баллов.

1) 2 балла: выдать упорядоченный по рейтингу список названий фильмов, при этом, рейтинг фильма считается как сумма рейтингов всех раздач с таким названием, N ≤ 100;

2) 3 балла: задание такое же, как для предыдущего пункта, но N ≤ 100000;

3) 4 балла: выдать упорядоченный по рейтингу список названий фильмов, у которых названия совпадают с учетом транслита (то есть «Аватар» и «Avatar» - это совпадающие с учетом транслита слова), N ≤ 10000; (http://transliteration.ru/gosdep/)

Входной файл

В первой строке входного файла содержится целое число N. Далее в файле содержатся 2N строк, каждая из которых описывает один фильм. В первой строке указывается название фильма, состоящее из пробелов, больших и маленьких букв латинского и русского алфавита, а также цифр (кодировка Windows 1251). Длина строки не превышает 100 символов. Во второй строке описания фильма содержится количество лайков и дизлайков.

 

Выходной файл

В выходной файл Вы должны вывести результат в соответствии с выполняемым уровнем задания. Для каждого фильма дополнительно выводится рейтинг. При совпадении рейтинга фильмы выводятся в том порядке, в котором они заданы во входном файле. Пример вывода приведен в задании.

При сравнении строк пробелы игнорируются. Разница между большими и маленькими буквами отсутствует. Фильмы, у которых отсутствуют лайки, игнорируются и в итоговом списке не должны появляться. При обработке транслита два варианта записываются в строке через знак “/”, причем сначала указывается тот вариант, который появляется в исходном файле раньше.

 

Примеры входных и выходных данных

 

films. in	films. out	Баллы за решение
9 Аватар 10 1 Шрэк 4 2 Морские дьяволы 7 1 Камерон Аватар 4 4 АватарHD 11 0 Аватар 4 0 Шрэк 3 0 2 Морские дьяволы. Смерч 4 2 Avatar 6 4	Аватар 14 1 13 АватарHD 11 0 11 Морские дьяволы 7 1 6 Шрэк 4 2 2 Морские дьяволы. Смерч 4 2 2 Avatar 6 4 2 Камерон Аватар 4 4 0	2
	Аватар/Avatar 20 5 15 АватарHD 11 0 11 Морские дьяволы 7 1 6 Шрэк 4 2 2 Морские дьяволы. Смерч 4 2 2 Камерон Аватар 4 4 0	4