>>Вообще, мне в начале дано начало слова, а надо из этих 200000
>>выбрать K<=2000 слов, начинающихся также. А если их больше К, то
>>те у которых самые большие числа.
По моему никаких seek тут не должно быть. Имеем файл записей <Число, строка>. Файл читается в один проход по записям, каждая строка сравнивается с заданным шаблоном. Если подходит, то кладётся в отсортированный по числу массив. Если массив заполнился, то элемент с меньшим числом замещается.
А уж 2000 элементов паскалевский массив вполне потянет.
Ну буфер хорошая идея… Только вопрос как ориентироваться в буфере тоже интересен:)
Дмитрий мне также интересно КАК можно запретить использование системных функций:)
Жека, ну естественно, я с тобой согласен:)
ЛЮДИ, я предложил способ, который вам ясен и понятен, но достаточно громоздк и неудобен, чтобы и мне и вам не нравится… так может лучше кто нибудь предложит что то еще? А то обсудить все хороши, а как вперед выйти-страшно, а вдруг поезд навстречу пустят?:)
имхо fseek может быть доступен не всегда – например при чтении из пайп-файла
если это – олимпиадная задача, то там время исполнения зачастую ограничено. лучше создать буфер и читать буфером, разбирая прочитанный кусок после каждого чтения
Время в хороших олимпиадных задачах обычно тратится не на чтение из файла. Если, конечно, не выпендриваться и не пользоваться seek'ом, а решать как следует
>Не разрешено копировать, изменять файл…а множественное обращение очень даже можно…
Не знаю как у вас, а у нас в Днепропетровске на городских и обласных олимпиадах по программированию это запрещено
Что значит множественное обращение к файлу? Что за странные олимпиады, открыл, пробежался раз, потом второй раз, потом закрыл.
я из своего небогатого опыта знаю только про ограничение на память..
Эффективный алгоритм иногда с ходу не придумать, как например сейчас…а олимпиадное время то течет…я не говорю конечно, что стоит втупую сразу использовать первые пришедшие на ум схемы…иначе получится забивание гвоздей микроскопом…
Просто подумать и использовать то что считаешь наиболее подходящим-вот и все что нужно:) У меня опыт олимпиад большой, нравятся мне такие заморочные задачки…
Это уже не хитрость, а изуверство – задача состоит в том, чтобы придумать эффективный алгоритм, а не в том, чтобы использовать memory-mapped файлы и т.п.
В данном случаем Станислав прав…
здесь надо обрабатывать строки по одной… в этом то и изюминка задачи, что все что есть ты не загонишь в оперативу как переменную…тут либо динамическая память, либо хитрость…
А хитрость тут можно такую применить-зачем все гнать в оперативу, если файл-это тоже память?М? только хранится на жестком, и доступ к ней чуть сложнее… Нужен указатель – не вопрос, создай переменную, которая хранит положение местоположение указателя в файле, нужно считать значение-позиционируйся в файле и считывай;) и ты ды…тут фантазия нужна;) Так как твоя задача наверняка не относится к задачам реального времени, то на скорость обработки никто внимания не обратит…удачи;)
Даже вашим методом, зачем вам массив для слов?
Проще же читать строку: сравнил слово, если подходит -> записал номер строки + число занести в упорядоченный массив. При обработке следующей строки, которая подходит, проверить к>2000 и если да, то текущее число больше или меньше самого меньшего. Больше – вставить и выкинуть самое меньшее, меньше – откинуть строку. Потом строки просто скопировать из исходного файла на вывод.
А вообще можно даже еще проще..
Нет, там не 200000 строк из чисел, а 200000 строк, где кождая строка включает в себя строку и число. Вообще, мне в начале дано начало слова, а надо из этих 200000 выбратьK<=2000 слов, начинающихся также. А если их больше К, то те у которых самые большие числа.
Выдаёт две ошибки:
1) Error 29: Ordinaltype exepted—- когда создаю массив из 200000 эл.
2) Еrror 22: Structure too large—-когда уменьшаю число эл. до 20000
А задача сводится к следующему:
Мне дан файл где N<=200000 строк следующего вида: <строка-число>,
где строка по длине <=10 символов, а число<=10^9
Как решать я знаю, проблема в том, чтобы всё это загнать в паскаль
есть вариант попроще выделения памяти. можно просто восьпользоваться Делфи, если писать в консольном для консоли, все тоже самое что и на паскале, только первую строчку дописать {$apptype console} и расширение файла не пас а .dpr
Если из под голого ДОС без менеджера памяти, то структуру в 2Мб не создать – памяти не хватит. Хотя сомневаюсь, что тут такой случай – времена дос и машин с 640кб памяти кончились вроде как давно =)
Думаю все же косяк в коде – скинь сюда ошибку дословно с ее числовым кодом. Чтобы создать такую структуру есть 2 варианта:
вариант №1
var
myarr: array[1..200000] of string[10];
вариант №2
type
Tmyarr=array[1..200000] of string[10];
Pmyarr=^Tmyarr;
var
myarr:Pmyarr;
затем в коде
new(myarr);
ченить типо
type
TStr = string[10];
TArr = array [1..200000] of TStr;
PArr = ^Tarr;
var
arr: PArr;
begin
if (MaxAvail < sizeof (arr)) then
begin
writeln ('not enough memory');
halt;
end;
new (PArr);
end.
не проверял, может чето немного не так
а вообще, зачем такой массив? дай задачу – 100% можно обойтись без таких геморроев
В паскале нужно обьявить массив(одномерный) из 200000 элементов, каждый – это строка длинной в 10 символов. Он ругается, что слишком большая переменная. Что делать не знаю.Please help me.
5 марта 2008 в 21:02
>>Вообще, мне в начале дано начало слова, а надо из этих 200000
>>выбрать K<=2000 слов, начинающихся также. А если их больше К, то
>>те у которых самые большие числа.
По моему никаких seek тут не должно быть. Имеем файл записей <Число, строка>. Файл читается в один проход по записям, каждая строка сравнивается с заданным шаблоном. Если подходит, то кладётся в отсортированный по числу массив. Если массив заполнился, то элемент с меньшим числом замещается.
А уж 2000 элементов паскалевский массив вполне потянет.
5 марта 2008 в 20:00
=))
5 марта 2008 в 18:02
Найдут – не найдут, это смотря как код напишешь;) =)
4 марта 2008 в 16:02
запрещено правилами, а не програмно. т.е. если найдут могут исключить
4 марта 2008 в 10:01
Дмитрий мне также интересно КАК можно запретить использование системных функций:)
Жека, ну естественно, я с тобой согласен:)
ЛЮДИ, я предложил способ, который вам ясен и понятен, но достаточно громоздк и неудобен, чтобы и мне и вам не нравится… так может лучше кто нибудь предложит что то еще? А то обсудить все хороши, а как вперед выйти-страшно, а вдруг поезд навстречу пустят?:)
3 марта 2008 в 23:04
имхо fseek может быть доступен не всегда – например при чтении из пайп-файла
если это – олимпиадная задача, то там время исполнения зачастую ограничено. лучше создать буфер и читать буфером, разбирая прочитанный кусок после каждого чтения
3 марта 2008 в 23:04
Время в хороших олимпиадных задачах обычно тратится не на чтение из файла. Если, конечно, не выпендриваться и не пользоваться seek'ом, а решать как следует
3 марта 2008 в 23:00
У вас запрещен системный вызов fseek? Каким образом, интересно?
3 марта 2008 в 21:04
>Не разрешено копировать, изменять файл…а множественное обращение очень даже можно…
Не знаю как у вас, а у нас в Днепропетровске на городских и обласных олимпиадах по программированию это запрещено
3 марта 2008 в 10:05
Динамический массив,и все должно получиться.
3 марта 2008 в 9:04
Не разрешено копировать, изменять файл…а множественноеобращение очень даже можно…
2 марта 2008 в 18:01
Что значит множественное обращение к файлу? Что за странные олимпиады, открыл, пробежался раз, потом второй раз, потом закрыл.
я из своего небогатого опыта знаю только про ограничение на память..
2 марта 2008 в 14:03
А если не из реального времени, а с олимпиады то ваш способ не подходит. тк на олимпиадах чаще всего не разрешено множественное обращение к файлу
2 марта 2008 в 14:00
Эффективный алгоритм иногда с ходу не придумать, как например сейчас…а олимпиадное время то течет…я не говорю конечно, что стоит втупую сразу использовать первые пришедшие на ум схемы…иначе получится забивание гвоздей микроскопом…
Просто подумать и использовать то что считаешь наиболее подходящим-вот и все что нужно:) У меня опыт олимпиад большой, нравятся мне такие заморочные задачки…
2 марта 2008 в 10:04
Спасибо большое за помощь
2 марта 2008 в 2:02
Так любая олимпиада – это и есть изуверство
2 марта 2008 в 1:04
за это я и любил олимпиады!
2 марта 2008 в 1:03
Это уже не хитрость, а изуверство – задача состоит в том, чтобы придумать эффективный алгоритм, а не в том, чтобы использовать memory-mapped файлы и т.п.
2 марта 2008 в 1:01
В данном случаем Станислав прав…
здесь надо обрабатывать строки по одной… в этом то и изюминка задачи, что все что есть ты не загонишь в оперативу как переменную…тут либо динамическая память, либо хитрость…
А хитрость тут можно такую применить-зачем все гнать в оперативу, если файл-это тоже память?М? только хранится на жестком, и доступ к ней чуть сложнее… Нужен указатель – не вопрос, создай переменную, которая хранит положение местоположение указателя в файле, нужно считать значение-позиционируйся в файле и считывай;) и ты ды…тут фантазия нужна;) Так как твоя задача наверняка не относится к задачам реального времени, то на скорость обработки никто внимания не обратит…удачи;)
1 марта 2008 в 21:00
Даже вашим методом, зачем вам массив для слов?
Проще же читать строку: сравнил слово, если подходит -> записал номер строки + число занести в упорядоченный массив. При обработке следующей строки, которая подходит, проверить к>2000 и если да, то текущее число больше или меньше самого меньшего. Больше – вставить и выкинуть самое меньшее, меньше – откинуть строку. Потом строки просто скопировать из исходного файла на вывод.
А вообще можно даже еще проще..
1 марта 2008 в 20:04
Нет, там не 200000 строк из чисел, а 200000 строк, где кождая строка включает в себя строку и число. Вообще, мне в начале дано начало слова, а надо из этих 200000 выбратьK<=2000 слов, начинающихся также. А если их больше К, то те у которых самые большие числа.
1 марта 2008 в 20:00
В таких задачах обычно решение подразумевает, что ты НЕ сохраняешь все данные в массив, а считаешь решение прямо по ходу чтения из файла.
1 марта 2008 в 19:04
дык ты дай условие полное, че с данными делать-то надо?
1 марта 2008 в 19:00
Хочется не хочется, а без указателей ни туды и ни сюды. Либо преобразовуй алгоритм так, чтобы не было таких массивов
1 марта 2008 в 18:04
это с олимпиад, да? интересные, конечно, задания с файлами на 200000 строк по одному числу %)
а разве нельзя загнать не строки, а числа сразу?
1 марта 2008 в 18:04
кстати, а почему нельзя на входе преобразовывать строку в число и не засовывать в массив?
1 марта 2008 в 18:03
Выдаёт две ошибки:
1) Error 29: Ordinaltype exepted—- когда создаю массив из 200000 эл.
2) Еrror 22: Structure too large—-когда уменьшаю число эл. до 20000
1 марта 2008 в 18:03
А задача сводится к следующему:
Мне дан файл где N<=200000 строк следующего вида: <строка-число>,
где строка по длине <=10 символов, а число<=10^9
Как решать я знаю, проблема в том, чтобы всё это загнать в паскаль
1 марта 2008 в 18:03
Ну по моему в таких случаях используют указатели (динамические массивы).
1 марта 2008 в 18:03
Чё-то мне с длинной арифметикой париться не хочется.
1 марта 2008 в 17:04
если это действительно паскаль под дос, то больше 64к в одной переменной не получится – ограничение размером сегмента
интересно, зачем может понадобиться 2е5 строк? может быть их стоит хранить в файле?
1 марта 2008 в 16:03
есть вариант попроще выделения памяти. можно просто восьпользоваться Делфи, если писать в консольном для консоли, все тоже самое что и на паскале, только первую строчку дописать {$apptype console} и расширение файла не пас а .dpr
1 марта 2008 в 16:02
Если из под голого ДОС без менеджера памяти, то структуру в 2Мб не создать – памяти не хватит. Хотя сомневаюсь, что тут такой случай – времена дос и машин с 640кб памяти кончились вроде как давно =)
Думаю все же косяк в коде – скинь сюда ошибку дословно с ее числовым кодом. Чтобы создать такую структуру есть 2 варианта:
вариант №1
var
myarr: array[1..200000] of string[10];
вариант №2
type
Tmyarr=array[1..200000] of string[10];
Pmyarr=^Tmyarr;
var
myarr:Pmyarr;
затем в коде
new(myarr);
1 марта 2008 в 16:02
Блин, тут уже как на voffka.com… пока пишешь коммент уже 10 появится =)))
1 марта 2008 в 16:01
импасибыл
но попробуй выделить память
1 марта 2008 в 16:01
ченить типо
type
TStr = string[10];
TArr = array [1..200000] of TStr;
PArr = ^Tarr;
var
arr: PArr;
begin
if (MaxAvail < sizeof (arr)) then
begin
writeln ('not enough memory');
halt;
end;
new (PArr);
end.
не проверял, может чето немного не так
а вообще, зачем такой массив? дай задачу – 100% можно обойтись без таких геморроев
1 марта 2008 в 16:00
В паскале нужно обьявить массив(одномерный) из 200000 элементов, каждый – это строка длинной в 10 символов. Он ругается, что слишком большая переменная. Что делать не знаю.Please help me.