IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Сумма, драгоценные камни, Олимпиадная задача с ВКОШП 2008
сообщение
Сообщение #1


///
**

Группа: Пользователи
Сообщений: 78
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

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


Прикрепленные файлы
Прикрепленный файл  problems.pdf ( 270.35 килобайт ) Кол-во скачиваний: 743
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


///
**

Группа: Пользователи
Сообщений: 78
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

 
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.



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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;

Вот, примерно так..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

Типа так, думаю smile.gif

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


///
**

Группа: Пользователи
Сообщений: 78
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


Lapp

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

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


///
**

Группа: Пользователи
Сообщений: 78
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ну как ты говоришь, что тебе надо начинать с i, если ты в цикле эту i собственноручно выкидываешь?..
Цитата
for x:=i to n do
begin
if (b[j]=s[x]) and (x<>j) and (x<>i) then
Что за мистика тут предполагается?.. blink.gif Уж если выключил 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
С ним и работай дальше по описанной мной схеме, ищи пары.

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.10.2021 8:11
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name