x,q,j,n,k,i:longint; s:string; a,b:array [1..10000] of char;
BEGIN assign(input,'gems.in'); reset(input); assign(output,'gems.out'); rewrite(output);
readln(n,k); readln(s); for i:=1 to k do begin read(a[i]); readln(b[i]); end;
for i:=1 to n do begin for j:=1 to k do begin if s[i]=a[j] then for x:=i to n do begin if (b[j]=s[x]) and (x<>j) and (x<>i) then inc(q) end; end; end; writeln(q); close(input); close(output); END.
Автор: Lapp 25.11.2008 3:57
Цитата(Zzzz... @ 24.11.2008 22:43)
вот вроде бы решил но не знаю правильно ли :
Нет.
1. Главная ошибка - ты не убираешь найденные камни из списка. Это нужно. Если не так - не было бы смысла в повторяющихся камнях в списке.
2. Тип string явно недостаточен для хранения списка из 100000 камней
3. Зачем ты сравниваешь x c j и x c i? Для второго достаточно начать цикл с i+1, а первое просто неверно (вредно).
4. Скорость. Все надо организовывать не так..
Сделай массив gems: array[a..z]of LongInt; Пройдись по входному списку и заполни gems количествами каждого камня. Потом иди по парам, и
if (gems[a[i]]>0)and(gems[b[i]]>0) then begin Inc(p); Dec(gems[a[i]]); Dec(gems[b[i]]) end;
Вот, примерно так..
Автор: Lapp 25.11.2008 6:41
В задаче Сумма (J) многое зависит от того, какой компилятор. В условиях 16-ричтности тут задолбаешься даже делать просто хранилище для стотысячезначных чисел.. Если массивы больше 64К разрешены, то делаем тип: tNumber = array[1..200000]of byte; - и заводим три таких числа. Затем делаем процедуры сложения и сдвига влево (умножения на 10). Дальше просто тройной вложенный цикл:
for i:=0 to 100000 do begin for j:=0 to 100000 do begin for k:=0 to 100000 do begin if <a+b=c> then <вывести результат и выйти> <сдвинуть a влево на 1> end; <сдвинуть b влево на 1> end; <сдвинуть c влево на 1> end;
Типа так, думаю
Мне долго казалось, что перебор можно оптимизировать. Потом, вроде, пришел к выводу, что нельзя. У кого есть соображения?
Автор: Zzzz... 25.11.2008 8:36
Lapp
компилятор фри паскаль он 64к
со стрингом согласен, только потом понял
Остальное как только приду со школы
Автор: Zzzz... 25.11.2008 23:08
Цитата
1. Главная ошибка - ты не убираешь найденные камни из списка. Это нужно. Если не так - не было бы смысла в повторяющихся камнях в списке.
Т.е. если такой прмер
7 1 abacaba ab
То когда я 1-ый раз нашел камни и увеличил q, то последовательность должна измениться и иметь вид acaba?
Цитата
2. Тип string явно недостаточен для хранения списка из 100000 камней
Можно взять массив char.
Цитата
3. Зачем ты сравниваешь x c j и x c i? Для второго достаточно начать цикл с i+1, а первое просто неверно (вредно).
В моём решении нужно начинать с i, т.к. если с i+1 не все камни учитываются. Сравниваю чтобы не было увеличения числа q. Например без этого условия:
7 1 abacaba
- мое решение выдаст ответ 10.
Цитата
4. Скорость. Все надо организовывать не так..
По скорости согласен очень долгое решение. Просто это первый вариант, который пришел в голову.
Цитата
Сделай массив gems: array[a..z]of LongInt; Пройдись по входному списку и заполни gems количествами каждого камня. Потом иди по парам, и
if (gems[a[i]]>0)and(gems[b[i]]>0) then begin Inc(p); Dec(gems[a[i]]); Dec(gems[b[i]]) end;
Вот, примерно так..
Хм... а сколько будет, например
7 1 abacaba ab
просто я не совсем понял твою идею.
У меня есть такой вариант:
7 2 abacaba ab ac
создать двумерный массив, который будет запоминать все позиции каждой буквы...т.е. a b c d...z 1 2 4 0 0 3 6 5 7
И смотрим ab 1<2 увеличиваем q, 1<6 увеличиваем q, 3<6 увеличиваем q, 5<6 увеличиваем q ac 1<4 увеличиваем q, 3<4 увеличиваем q
Про сумму J я пока еще не думал, как ее можно решить, но пройдет ли твое решение по времени?
Автор: Lapp 25.11.2008 23:27
Ну как ты говоришь, что тебе надо начинать с i, если ты в цикле эту i собственноручно выкидываешь?..
Цитата
for x:=i to n do begin if (b[j]=s[x]) and (x<>j) and (x<>i) then
Что за мистика тут предполагается?.. Уж если выключил i, то мог выключить и раньше
Сама по себе входная последовательность камней не нужна. Никому не интересно, на каких местах стоят камни. Важно кол-во каждого камня. Проходим по ней (например, при считывании) и забываем про нее. Из твоего примера:
Цитата(Zzzz... @ 25.11.2008 19:08)
7 1 abacaba ab
- получается такой массив: gems[a]=4 gems[b]=2 gems[c]=1 gems[d]=0 gems[e]=0 ... gems[z]=0 С ним и работай дальше по описанной мной схеме, ищи пары.
Что касается времени подсчета суммы - да, долго. У тебя есть более быстрый способ? Я с удовольствием послушаю. Я же спросил это у всех еще в первом посте.