Олимпиадная задача

[Beny Benassi]

Приветствую,форумчане. Готовлюсь в олимпиаде по информатике. Никак не могу разобратсья с такой программой:



Задача 3 Удачная покупка (50 баллов)
Имя входного файла: shopping.in
Имя выходного файла: shopping.out
Максимальное время работы на одном тесте: 2 секунды
Ограничение по памяти: 64 MB
Недавно Петя решил купить себе цифровой фотоаппарат. Зайдя на сайт любимого магазина, он обнаружил в продаже огромное количество фотоаппаратов. Потратив целый день, и совершенно отчаявшись что-либо выбрать, Петя обратился за помощью к своему другу Васе. А Вася очень любит математику. Он сразу же объяснил Пете, как надо выбирать фотоаппарат:
В продаже имеется N фотоаппаратов, причем цены на все фотоаппараты различны. Вася предлагает расположить все фотоаппараты в порядке возрастания их стоимости и купить пятый с начала этого списка фотоаппарат.
Формат входных данных
Первая строка входного файла содержит целое число N (5 <= N <= 100000) – количество моделей фотоаппаратов, имеющихся в продаже. Затем идет 2N строк: сначала N строк с названиями моделей, затем N строк с ценами соответствующих фотоаппаратов. Название модели фотоаппарата – это непустая последовательность не более чем из 30 латинских символов, цифр, дефисов и пробелов. Цена фотоаппарата – целое положительное число не превышающее 1000000000.
Формат выходных данных
В текстовый файл shopping.out выведите название модели фотоаппарата, который Петя должен купить.
Вход
6
Nikon D80 Kit Вывод Pentax K20D Kit
Canon EOS 450D Kit
Nikon D40 Kit
Canon EOS 50D Body
Sony Alpha DSLR-A200 Kit
Pentax K20D Kit
23000
19550
14800
38336
15300
28000

Массив созджавать не вариант. Думал, считывать название, спускаться до цен(цикл с readln - смена положения курсора) но поднять его потом нельзя, так что и этот вариант выпадает. ЧТо делать?

[Poma][a]

Массив не будет проходить по времени..
А память давайте считать..
У нас есть 64 МБ
Максимум, что может быть это
(31 + 4) * 1024 * 1024 = 35 МБ, так что проходим..

Вас спасет поиск K-ой статистики..
Так что создаем массив структур и не паримся..

UPDATE
А хотя я ошибся.. У нас есть 2 секунды..
А максимум фотиков 100 000, а выполнять может за одну секунду может до 20 000 000 (на среднестатистическом компе)..

[Arigato]

Ну так можно в начало файла прыгнуть, или все таки массив, который займет 3000000 байт, что меньше 64Мб.

[ViktorR]

Думаю, что от массива отказываться нельзя. Вот только его надо сделать двумерным и на пять элементов (всего - десять).
В одной размерности храним цену, а во второй - номер в последовательности.
Алгорит получается такой:
1. Читаем первое число.
2. Пропускаем строки на это число.
3. Читаем первые пять ценников и пишем их в массив с порядковым номером. Сортируем. Обратите внимание, что цены все разные.
4. Продолжаем чтение до конца и всавляем в массив цены, которые больше пятого элемента. Не забываем про запись порядкового номера цены. Вставку можно делать бинарным поиском.
5. После прочтения всего файла в пятом элементе нужная нам цена и порядковый номер фотоаппарата.
6. Переоткрываем файл и читаем запись, которая располагается в позиции на 1 больше, чем порядковый номер фотоаппарата.

Как-то так, ...

[Beny Benassi]

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

[Serge_Bliznykov]

ViktorR, я тоже (вначале) думал именно такой алгоритм использовать!
Ну, я бы завёл тип record из двух полей (в одном название string[30], во втором цена LongInt).
Но есть один нехороший (мерзкий) нюансик.
Сначала идёт сто тысяч (в максимуме) названий, потом столько же - цен.
Поэтому не получится прочитать первый пять названий и первых пять цен!

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

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

нормальные, современные компиляторы (FPC, Delphi) создадут такой массив без всяких проблем.
Если же стоит задача использовать древний TurboPascal - смотрите в сторону использования динамической памяти.

[Аватар]

А временный файл в условии нет запрета создавать? Читаем за один прогон, строки во временный файл, цены и позиции как ViktorR предложил. В конце нужное наименование из временного файла читаем

[ViktorR]

Открывать файл можно только 1 раз.

А с чего это следует? Ткните, где это требование изложено.
В каждом конкретном случае такое требование должно быть представлено, если оно важно.
Можно или нельзя открывать файл повторно - это обязательное условие задачи. Если это условие отсутствует, то значит можно открывать неоднократно.
Просто на это тратится дополнительное время.
С другой стороны, прочитайте первое число. Прочитайте файл один раз и все данные перепишите в два временных файла. Затем в одном из них выбираете цену и зная порядковый номер, лезете во второй.
Но это так, ...


Как-то так, ...

[ViktorR]

Serge_Bliznykov

Но есть один нехороший (мерзкий) нюансик.
Сначала идёт сто тысяч (в максимуме) названий, потом столько же - цен.
Поэтому не получится прочитать первый пять названий и первых пять цен!

Юмор в том, что названия надо просто пропустить.
Читаем только цены и сохраняем подходящие с их порядковым номером.
Вот потом, используя порядковый номер, читаем название.


Как-то так, ...

[Serge_Bliznykov]

Сообщение от ViktorR

А с чего это следует? Ткните, где это требование изложено.
В каждом конкретном случае такое требование должно быть представлено, если оно важно.
Можно или нельзя открывать файл повторно - это обязательное условие задачи. Если это условие отсутствует, то значит можно открывать неоднократно.

да. кстати. согласен!

Beny Benassi, с чего Вы взяли, что файл нельзя открыть повторно?!!

Сообщение от ViktorR

Юмор в том, что названия надо просто пропустить.
Читаем только цены и сохраняем подходящие с их порядковым номером.
Вот потом, используя порядковый номер, читаем название.

угу! согласен!