Сумма, драгоценные камни, Олимпиадная задача с ВКОШП 2008 Опции

[Zzzz...]

Добрый день!
Кто-либо может объяснить задачу Е и задачу J. Буду очень признателен...

В прикрепленном файле находятся все задачи с ВКОШП'а.

[Zzzz...]

вот вроде бы решил но не знаю правильно ли :

 
VAR

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]

вот вроде бы решил но не знаю правильно ли :

Нет.

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]

В задаче Сумма (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...]

Lapp

компилятор фри паскаль он 64к

со стрингом согласен, только потом понял

Остальное как только приду со школы

[Zzzz...]

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]

Ну как ты говоришь, что тебе надо начинать с i, если ты в цикле эту i собственноручно выкидываешь?..

for x:=i to n do
begin
if (b[j]=s[x]) and (x<>j) and (x<>i) then

Что за мистика тут предполагается?.. Уж если выключил i, то мог выключить и раньше

Сама по себе входная последовательность камней не нужна. Никому не интересно, на каких местах стоят камни. Важно кол-во каждого камня. Проходим по ней (например, при считывании) и забываем про нее. Из твоего примера:

7 1
abacaba
ab

- получается такой массив:
gems[a]=4
gems[b]=2
gems[c]=1
gems[d]=0
gems[e]=0
...
gems[z]=0
С ним и работай дальше по описанной мной схеме, ищи пары.

Что касается времени подсчета суммы - да, долго. У тебя есть более быстрый способ? Я с удовольствием послушаю. Я же спросил это у всех еще в первом посте.