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

[Zzzz...]

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

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

[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 я пока еще не думал, как ее можно решить, но пройдет ли твое решение по времени?