2. Известный профессор Mr. Steinicke считает делом всей своей жизни создание каталога галактических объектов Newest Galactic Catalogue. К сожалению, из-за огромного количества объектов, у него не хватает времени следить за тем, чтобы все внесенные в каталог галактики имели оригинальные названия. В этом ему решил помочь его аспирант, который составил списки оригинальных и вторичных названий.
Задание. Написать программу NGC, которая находит количество галактик, оригинальные названия которых не являются вторичными ни для какой из галактик.
Входные данные. Первая строка текстового файла NGC.DAT содержит целое число N -количество объектов в каталоге (1<=N<=1000). В последующих N строках дан список названий галактик. Первое название в каждой строке - оригинальное название галактики, которая есть в каталоге, за ней следует список ее вторичных названий. Названия объектов отделяются друг от друга одним пробелом и состоят ровно из 7 больших латинских букв, цифр и знаков подчеркивания, причем первый символ не может быть цифрой. Длина строк во входном файле не превышает 5000 символов. Всего в файле содержится не более 2500 разных названий. 
Выходные данные. В единственную строку текстового файла NGC.SOL необходимо вывести
количество галактик,  имеющих оригинальное  название,  не совпадающее  ни с  каким
вторичным названием какой-либо из галактик.
Пример входных и выходных данных
NGC.dat
8
NGC_125 PGC6564 IC__435 PP_2434
NGC_345 PGC5345
NGC_457 NGC_125 PGC9034
NGC8954 P_50904
NGC3423 NGC_345 NGC3958 NGC3423
NGC5345 NGC8534
NGC6565 NGC8534
NGC8534

NGC.SOL
4

Решение: Отхипсортить вторичные названия (отсортировать за NlogN) и  для каждой вершины искать повторения дихотомией (еще называется бинарный поиск, или двоичный поиск). Исходя из условия максимум может быть 625 тыс названий, так что на сортровку уйдет порядка  625 000*18*7 ~1млрд 200 млн операций - что  как  по мне довольно долго (секунд 10).

Добавлено @ 18:21 
А вообще плохая задача - никто не заметил что написано "не более 2500 РАЗНЫХ названий", и поэтому все на ней слетели из-за маленького заведенного массива

Это сообщение отредактировал(а) FireSnake - 23.2.2007, 18:22

625 000*18*7 ~1млрд 200 млн

(kirin's head calculator)


ну такой у меня калькулятор!

Это сообщение отредактировал(а) FireSnake - 26.2.2007, 21:30