Сумма, драгоценные камни, Олимпиадная задача с ВКОШП 2008 |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Сумма, драгоценные камни, Олимпиадная задача с ВКОШП 2008 |
Zzzz... |
Сообщение
#1
|
/// Группа: Пользователи Сообщений: 78 Пол: Мужской Реальное имя: Илья Репутация: 0 |
Добрый день!
Кто-либо может объяснить задачу Е и задачу J. Буду очень признателен... В прикрепленном файле находятся все задачи с ВКОШП'а. Прикрепленные файлы problems.pdf ( 270.35 килобайт ) Кол-во скачиваний: 1065 |
Zzzz... |
Сообщение
#2
|
/// Группа: Пользователи Сообщений: 78 Пол: Мужской Реальное имя: Илья Репутация: 0 |
вот вроде бы решил но не знаю правильно ли :
|
Lapp |
Сообщение
#3
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
вот вроде бы решил но не знаю правильно ли : Нет.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 Вот, примерно так.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#4
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
В задаче Сумма (J) многое зависит от того, какой компилятор. В условиях 16-ричтности тут задолбаешься даже делать просто хранилище для стотысячезначных чисел.. Если массивы больше 64К разрешены, то делаем тип:
tNumber = array[1..200000]of byte; - и заводим три таких числа. Затем делаем процедуры сложения и сдвига влево (умножения на 10). Дальше просто тройной вложенный цикл: for i:=0 to 100000 do begin Типа так, думаю Мне долго казалось, что перебор можно оптимизировать. Потом, вроде, пришел к выводу, что нельзя. У кого есть соображения? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Zzzz... |
Сообщение
#5
|
/// Группа: Пользователи Сообщений: 78 Пол: Мужской Реальное имя: Илья Репутация: 0 |
Lapp
компилятор фри паскаль он 64к со стрингом согласен, только потом понял Остальное как только приду со школы |
Zzzz... |
Сообщение
#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 количествами каждого камня. Потом иди по парам, и
Вот, примерно так.. Хм... а сколько будет, например 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 |
Сообщение
#7
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ну как ты говоришь, что тебе надо начинать с i, если ты в цикле эту i собственноручно выкидываешь?..
Цитата for x:=i to n do Что за мистика тут предполагается?.. Уж если выключил i, то мог выключить и раньшеbegin if (b[j]=s[x]) and (x<>j) and (x<>i) then Сама по себе входная последовательность камней не нужна. Никому не интересно, на каких местах стоят камни. Важно кол-во каждого камня. Проходим по ней (например, при считывании) и забываем про нее. Из твоего примера: 7 1 - получается такой массив:abacaba ab gems[a]=4 gems[b]=2 gems[c]=1 gems[d]=0 gems[e]=0 ... gems[z]=0 С ним и работай дальше по описанной мной схеме, ищи пары. Что касается времени подсчета суммы - да, долго. У тебя есть более быстрый способ? Я с удовольствием послушаю. Я же спросил это у всех еще в первом посте. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 4.05.2024 22:25 |