ЗДравствуйте ребята программеры! Вот на днях мне препод дал задачу (сказал, что с какой то олимпиады). Условие таково:
Вводится строка из 0 и 1 (причем строка должна быть не более 1000 000 символов). Затем вводится начальная позиция (min) и конечная позиция(max). Вот и требуется узнать есть ли между заданными позициями (включая их самих) одинаковые числа, т.е. только 0 или только 1. С первого взгляда задача очень проста, но там есть одно условие: нужно, чтобы программа выполнялась не более двух секунд. Т.е. нужно придумать очень быстрый алгоритм проверки в заданном интервале. У меня же пока что получается 10 секундная прога, помогите сделать 2 секундную. Заранее благодарен.
P.S.: я сделал прогу проверкой в лоб, т.е. берется начальный элемент (т.е. st[min], где st - это мой массив из 0 и1) строки и затем проверяется с каждым элементом до конечного (т.е. до st[max])
Полная версия: 0 и 1
Я бы посоветовал удваивать интервал. Т. е. сначала сравнить первые 2 байта, затем первые две пары байт затем по 4 и т. д. При грамотной реализации может дать ускорение... Но это оптимизация скорее на уровне асма...
Все зависит от вида хранения данных (побитово или нет).
От прохода от min до max никуда не деться.
Не хочется никого обижать, но может быть цикл прохода не оптимизирован ИМЕННО по времени.
От прохода от min до max никуда не деться.
Не хочется никого обижать, но может быть цикл прохода не оптимизирован ИМЕННО по времени.
Я попробовал такой "предельно тупой" код:
Будучи откомпилирован на BP 7.0 и запущен на AMD K6-2 300 MHz он справляется с самым сложным случаем (1000000 проверок) за ~0.5 с. Компиляция с помощью FP дает примерно такой же результат.
А может предельно тупой я сам: не смог разобраться в условии задачи...
Код
program _0or1;
var
f: Text;
c, c0: Char;
Min, Max, i: LongInt;
begin
Assign(f, 'input.txt');
Reset(f);
Readln(f, Min, Max);
for i := 1 to Min do Read(f, c0);
for i := 1 to Max - Min do
begin
Read(f, c);
if c <> c0 then
begin
Writeln('Нет');
Close(f);
Exit;
end;
end;
Close(f);
Writeln('Да');
end.
var
f: Text;
c, c0: Char;
Min, Max, i: LongInt;
begin
Assign(f, 'input.txt');
Reset(f);
Readln(f, Min, Max);
for i := 1 to Min do Read(f, c0);
for i := 1 to Max - Min do
begin
Read(f, c);
if c <> c0 then
begin
Writeln('Нет');
Close(f);
Exit;
end;
end;
Close(f);
Writeln('Да');
end.
Будучи откомпилирован на BP 7.0 и запущен на AMD K6-2 300 MHz он справляется с самым сложным случаем (1000000 проверок) за ~0.5 с. Компиляция с помощью FP дает примерно такой же результат.
А может предельно тупой я сам: не смог разобраться в условии задачи...
Я бы посоветовал открывать файл не как текстовой, а как нетипизированный с длиной записи 1, а потом реализовать идею BlackShadow. Тогда существенное ускорение для больших строк даст BlockRead.
Кстати, Text использует буферизацию по умолчанию, правда размер буфера небольшой (128 байт). Несомненно, BlockRead с буфером разумного размера (4-16 Кб) даст некоторый прирост скорости чтения. Тем не менее, приведенный выше пример кода наводит на мысли, что программа легко укладывается в поставленные временные рамки даже при чуть менее чем "неразумной" реализации (под "неразумными" способами я подразумеваю что-то вроде "var f: File of Char", "BlockRead(f, c, 1)" 
)
)
Я уже где-то кому-то говорил, что оптимальный размер буфера совпадает с размером кластера диска, с которым происходит работа...
А если хранить каждый 0 или 1 в массиве, пофигу каком.
Для заданного диапазона сосчитать сумму элементов массива.
Если будет 0 тогда только 0 записаны,
Если сумма равна числу элементов тогда только 1.
Для заданного диапазона сосчитать сумму элементов массива.
Если будет 0 тогда только 0 записаны,
Если сумма равна числу элементов тогда только 1.
Вот только счётчик в таком случае надо 4-ёх байтный брать. А то вдруг там сумма ровно в 256 или 65536 выйдет...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.