28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
1 | |
Задача Компьютерная игра C++08.09.2009, 14:49. Показов 11949. Ответов 20
Метки нет (Все метки)
Здравствуйте!
Помогите решить задачку на тему Динамическое программирование. У меня проходит только 5-тестов. Задача находится здесь: http://acmp.ru/?main=task&id_task=29
0
|
08.09.2009, 14:49 | |
Ответы с готовыми решениями:
20
Задача Компьютерная Игра Компьютерная игра (платформы) Структура "Компьютерная игра": реализовать поиск в массиве объектов пользовательского типа по заданному полю Компьютерная игра Sky Hunter |
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.09.2009, 15:34 | 2 |
А где там 5 тестов ?
Там только два теста. Задача решается тривиально. Нужно начать вычислять минимальное кол-во энергии справа налево. Пусть высота платформы задается в массиве height[]. Сначала массив energy[] на N значений пустой. Потом заполняем N-тое значение, потом N-1, потом N-2. И когда дойдем до 1-ого значения - это и будет искомый результат. Пусть мы находимся на I-ом шаге - то есть нам нужно заполнить ячейку I. Все ячейки справа - от I+1 до N уже заполнены. Все ячейки слева - от 1 до I-1 незаполнены. С нашего места у нас есть два варианта действий. 1) Сделать прыжок на I+1 ячейку. В этом случае мы потратим энергию на прыжок, а для I+1 платформы у нас уже есть минимальный ответ - он записан в ячейке I+1. 2) Сделать суперпрыжок на I+2 ячейку. Тут опять же прыжок, а для I+2 ячейки есть ответ. Нужно вычислать какой из этих двух вариантов эффективнее и именно это значение записать в ячейку I. Далее I-- и опять переходим на начало алгоритма. Ответ будет в energy[1]. А по тексту самой задачи - чего-то бредят они - с чего это вдруг переход на платформу ниже требует затрат энергии ? На платформу выше нужно прыгать, а на платформу ниже нужно падать - затрат либо нет вообще, либо энергия только прибавляется.
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
||||||
08.09.2009, 15:40 [ТС] | 3 | |||||
Я так и решал. Но 5-й тест не проходит.
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
08.09.2009, 16:01 | 4 | |||||
Потому что неправильно решил.
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
08.09.2009, 16:11 [ТС] | 5 |
Сам хотя бы тестировал?
Протестируй на это: 3 1 5 10 Ответ 9; 10 3 4 8 10 1 7 1 10 12 15 Ответ 30;
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.09.2009, 16:22 | 6 |
Правильно работает Добавлено через 1 минуту На этом сайте http://acmp.ru/ 500 задач ! И есть целых три человека, которые решили все 500 задач Добавлено через 3 минуты А ты там сколько уже задач решил и какой рейтинг набрал ? Добавлено через 1 минуту А все - нашел: http://acmp.ru/?main=user&id=9757 Добавлено через 1 минуту Пойти зарегистрироваться что-ли и сдать 29-ую задачу Добавлено через 3 минуты Главная ошибка у тебя - нужно завести второй массив для найденного уровня минимальной энергии. Заметил еще несколько мелких, из-за которых тоже считать не будет
1
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
08.09.2009, 16:27 [ТС] | 7 |
Рейтинг 1047. 42 задач решил. С динамикой проблема. В acmp.ru я JDS.
Давай заходи решай под каким именем будешь заходить? Если что давай вместе обсуждать задачки. Кстати твоя прога не проходит 7-й тест. Сам проверь если не веришь. Я там еще условие добавил при n = 1. Ответ 1-ый элемент.
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.09.2009, 16:40 | 8 |
Программа выводит 0. Добавлено через 4 минуты Если ответ - первый элемент, тогда организаторы задач мягко говоря неумные люди. Условие задачи: "Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней? " Если платформа одна, то первая платформа и есть последняя. Прыгать никуда не нужно. Ответ - 0. Если же они считают что нужно прыгать на первую платформу снизу или c последней платформы вниз, тогда приведенные в качестве теста варианты потому что они там не прыгают ! Добавлено через 2 минуты Я к ним на форум зашел по 29-ой задаче. Там все ругаются на этот 7-ой тест. Вообщем коряво они его составили
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
11.09.2009, 14:53 [ТС] | 9 |
Нашел контрпример на 7-й тест
5 1 0 1 0 5 ответ: 6
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
11.09.2009, 16:20 | 10 |
Какой еще контр-пример ?
Условие задачи прочитай: В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы. Высота платформы - НАТУРАЛЬНОЕ ЧИСЛО, то есть от 1 и выше.
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
11.09.2009, 16:22 [ТС] | 11 |
Ты сперва запусти под этот тест свою прогу. Если выведет 6 то твоя прога пройдет все тесты.
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
11.09.2009, 16:31 | 12 |
Не проходит.
Добавлено через 1 минуту Но и тест условию задачи не соответствует. Я там порешал задачи - у них там такие косяки очень редко, но есть. Хотя конечно в программе тоже ошибка есть
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
11.09.2009, 16:33 [ТС] | 13 |
Народ решил значит и мы должны решить!
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
11.09.2009, 16:40 | 14 |
Я тут думал как написать программу которая выуживает от них все тесты
Похоже у них задачи компилируются Visual Studio, а не gcc. Можно написать сетевую программу, которая посылает все файлы INPUT.TXT по сети. Правда для этого придется решить все задачи Добавлено через 30 секунд Я там уже штук 30 задач решил.
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
11.09.2009, 16:53 [ТС] | 15 |
а остальные когда будешь решать?
Добавлено через 3 минуты Кстати ты сам откуда, сколько тебе лет, где учился?
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
11.09.2009, 17:21 | 16 | |||||
Исправил ошибки.
Там крайние значения нужно отдельно проверять - нельзя заменять 0-ем !
Ну решаю пока задачи для нубов - то есть для начинающих. Добавлено через 34 секунды Потом отсюда код возъму для 29-ой задачи Добавлено через 21 минуту Ну что - сдал 29-ую задачу ?
0
|
28 / 27 / 11
Регистрация: 12.03.2009
Сообщений: 85
|
|
11.09.2009, 17:23 [ТС] | 17 |
Нет не принимает. Пишет TLE. Дома посмотрю может там что-то не так.
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
11.09.2009, 19:53 | 18 | |||||
Ну правильно - я там отладочный код оставил.
И с границами накосячил. Вот вроде все тесты проходит.
Все - сдал я эту задачу с 1-го раза. Но не этот код кстати Спасибо за два теста. Догадаться что при n==1 нужно возвращать высоту 1-ой платформы невозможно - это ошибка их теста. И догадаться что 0 может быть высотой тоже нельзя - это ошибка в условии.
1
|
0 / 0 / 0
Регистрация: 29.07.2015
Сообщений: 1
|
|
13.09.2009, 23:00 | 19 |
Ага, привет всем) Как вы уже поняли, я девушка, а также я далека от программирования, но...на ум пришла идея..хотелось бы попробовать реализовать ее самостоятельно...так вот, не подскажите ли, на каком языке программирования написана программа вконтакте, хм...кажется, как-то так это должно звучать)
Добавлено через 2 минуты и не называйте меня нубом, пожалуйста, как-то неочень звучит...)
0
|
33 / 25 / 7
Регистрация: 08.11.2008
Сообщений: 107
|
|
14.09.2009, 19:51 | 20 |
0
|
14.09.2009, 19:51 | |
14.09.2009, 19:51 | |
Помогаю со студенческими работами здесь
20
Компьютерная игра NEKRUM на движке UNITY Какая ваша любимая компьютерная игра? Компьютерная игра "Семь лунок": Сделать массив, который бы реагировал на перестановку шаров в лунках Задача по теме "Компьютерная графика" Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |