Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.90
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
#1

Задача Компьютерная игра C++ - C++

08.09.2009, 14:49. Просмотров 3696. Ответов 20
Метки нет (Все метки)

Здравствуйте!

Помогите решить задачку на тему Динамическое программирование.
У меня проходит только 5-тестов.
Задача находится здесь:

http://********/?main=task&id_task=29
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2009, 14:49     Задача Компьютерная игра C++
Посмотрите здесь:

Компьютерная игра (платформы) - C++
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или...

Задача.Игра в числа - C++
Вася очень любит играть в числа. Для этой игры нужна колода из N различных целых чисел от 1 до N. Эдик(который тоже очень любит эту игру)...

Игра в крестики нолики, задача почти решена но результат не выводится на экран - C++
Извиняюсь заранее, в этом деле я очень зеленый. Прошу отнестись с пониманием )) #include<iostream> #include<iomanip> using...

Задача: игра "Поймать парасёнка" - C++
Описание "Поймать парасёнка" - один из видов игры в карты. Допустим за игральным столом 4 игрока. Ваша задача посчитать итоговый...

Компьютерная графика в c++ - C++
Помогите пожалуйста написать в с++ такой алгаритм, чтобы рисовать различные фигуры, к примеру прямоугольник.

Компьютерная графика - C++
Есть две функцииvoid my_Line(int x1,int y1, int x2, int y2, int color)// Линия { int deltaX=abs(x2-x1); int deltaY=abs(y2-y1); ...

компьютерная графика - C++ Builder
нужно реализовать вот такое задание: Выдача на экран изображения с эффектами. В качестве изображения берется файл в графическом формате...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 15:34     Задача Компьютерная игра C++ #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].

А по тексту самой задачи - чего-то бредят они - с чего это вдруг переход на платформу ниже требует затрат энергии ? На платформу выше нужно прыгать, а на платформу ниже нужно падать - затрат либо нет вообще, либо энергия только прибавляется.
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 15:40  [ТС]     Задача Компьютерная игра C++ #3
Я так и решал. Но 5-й тест не проходит.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <fstream>
#include <math.h>
#include <assert.h>
using namespace std;
 
const int MaxN = 30000;
 
int a[MaxN];
int n, s, t;
 
ifstream fin("input.txt");
ofstream fout("output.txt");
 
int main()
{
    fin >> n;
    assert(1 <= n && n <= MaxN);
    a[0] = MaxN;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
 
    s = MaxN;
    for (int i = n - 1; i > 1; --i)
    {
        if (abs(a[i] - a[i - 1]) <= abs(a[i] - a[i - 2]) * 3))
        {
            s += abs(a[i] - a[i - 1]);
        }
        else
        {
                                      s += abs(a[i] - a[i - 2]) * 3);
        }
    }
 
    fout << s << endl;
    return 0;
}
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:01     Задача Компьютерная игра C++ #4
Потому что неправильно решил.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <fstream>
#include <assert.h>
 
using namespace std;
 
const int MAX_N= 30000;
 
int calc_min_energy( int n, int *height );
 
int main( void ) {
 
int i, n, min_energy;
int height[MAX_N];
ifstream fin;
ofstream fout;
 
 
fin.open( "INPUT.TXT" );
fin >>n;
assert( 1<=n && n<=MAX_N );
for ( i= 1; i<=n; i++ ) { fin >>height[i]; }
fin.close();
 
min_energy= calc_min_energy( n, height );
 
fout.open( "OUTPUT.TXT" );
fout <<min_energy <<endl;
fout.close();
 
return 0;
 
} // main()
 
 
int calc_min_energy( int n, int *height ) {
 
int i, var0, var1;
int energy[MAX_N+1];
 
 
energy[n]= 0; energy[n+1]= 0;
for ( i= n-1; i>=1; i-- ) {
    var0= abs( height[i]-height[i+1] )+energy[i+1];
    var1= 3*abs( height[i]-height[i+2] )+energy[i+2];
    energy[i]= (var0<var1) ? var0 : var1;
}
 
return energy[1];
 
} // calc_min_energy()
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 16:11  [ТС]     Задача Компьютерная игра C++ #5
Цитата Сообщение от odip Посмотреть сообщение
Потому что неправильно решил.
Сам хотя бы тестировал?
Протестируй на это:
3
1 5 10
Ответ 9;
10
3 4 8 10 1 7 1 10 12 15
Ответ 30;
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:22     Задача Компьютерная игра C++ #6
Сам хотя бы тестировал?
Да

Правильно работает

Добавлено через 1 минуту
На этом сайте http://********/ 500 задач !
И есть целых три человека, которые решили все 500 задач

Добавлено через 3 минуты
А ты там сколько уже задач решил и какой рейтинг набрал ?

Добавлено через 1 минуту
А все - нашел: http://********/?main=user&id=9757

Добавлено через 1 минуту
Пойти зарегистрироваться что-ли и сдать 29-ую задачу

Добавлено через 3 минуты
Главная ошибка у тебя - нужно завести второй массив для найденного уровня минимальной энергии.
Заметил еще несколько мелких, из-за которых тоже считать не будет
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 16:27  [ТС]     Задача Компьютерная игра C++ #7
Рейтинг 1047. 42 задач решил. С динамикой проблема. В ******** я JDS.
Давай заходи решай под каким именем будешь заходить?
Если что давай вместе обсуждать задачки. Кстати твоя прога не проходит 7-й тест. Сам проверь если не веришь. Я там еще условие добавил при n = 1. Ответ 1-ый элемент.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:40     Задача Компьютерная игра C++ #8
Если что давай вместе обсуждать задачки.
Тут на форуме ?
Кстати твоя прога не проходит 7-й тест.
А какую ошибку пишет ?
Я там еще условие добавил при n = 1. Ответ 1-ый элемент.
При n=1 никуда прыгать не нужно. Ответ 0.
Программа выводит 0.

Добавлено через 4 минуты
Если ответ - первый элемент, тогда организаторы задач мягко говоря неумные люди.
Условие задачи: "Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней? "
Если платформа одна, то первая платформа и есть последняя. Прыгать никуда не нужно.
Ответ - 0.
Если же они считают что нужно прыгать на первую платформу снизу или c последней платформы вниз, тогда приведенные в качестве теста варианты потому что они там не прыгают !

Добавлено через 2 минуты
Я к ним на форум зашел по 29-ой задаче.
Там все ругаются на этот 7-ой тест.
Вообщем коряво они его составили
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 14:53  [ТС]     Задача Компьютерная игра C++ #9
Нашел контрпример на 7-й тест

5
1 0 1 0 5

ответ: 6
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:20     Задача Компьютерная игра C++ #10
Какой еще контр-пример ?
Условие задачи прочитай:
В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.

Высота платформы - НАТУРАЛЬНОЕ ЧИСЛО, то есть от 1 и выше.
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:22  [ТС]     Задача Компьютерная игра C++ #11
Ты сперва запусти под этот тест свою прогу. Если выведет 6 то твоя прога пройдет все тесты.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:31     Задача Компьютерная игра C++ #12
Не проходит.

Добавлено через 1 минуту
Но и тест условию задачи не соответствует.
Я там порешал задачи - у них там такие косяки очень редко, но есть.
Хотя конечно в программе тоже ошибка есть
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:33  [ТС]     Задача Компьютерная игра C++ #13
Народ решил значит и мы должны решить!
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:40     Задача Компьютерная игра C++ #14
Я тут думал как написать программу которая выуживает от них все тесты
Похоже у них задачи компилируются Visual Studio, а не gcc.
Можно написать сетевую программу, которая посылает все файлы INPUT.TXT по сети.
Правда для этого придется решить все задачи

Добавлено через 30 секунд
Я там уже штук 30 задач решил.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2009, 16:53     Задача Компьютерная игра C++
Еще ссылки по теме:

Компьютерная графика 3D. - C++
Потребовалось мне сделать проект с 3D графикой. Т.е. надо было нарисовать плоскость Безье. Все вроде бы получилось, но во первых, хреново...

Компьютерная графика - C++
Люди, прошу помощи. Мне нужно создать компьютерную 3D графику. Причем для меня это выглядело так: пришел препод, сказал всего 1 фразу, -...

Компьютерная графика - C++ Builder
Не могу реализовать задачу, в которой нужно изобразить движение солнца по схеме: утро-восход, день - в зените (максимальная яркость), вечер...

Компьютерная графика и анимация - C++
Изобразить на экране монитора прямоугольник с изменяемыми длиной и шириной(+/-), расположением (стрелками). Кто-нибудь может сказать,...

Компьютерная графика на C++ Builder - C++ Builder
Вот с этим нужно что бы получилось ниже указанное, что бы внутри буквы была закраска только#include &lt;stdio.h&gt; #include &lt;conio.h&gt; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:53  [ТС]     Задача Компьютерная игра C++ #15
а остальные когда будешь решать?

Добавлено через 3 минуты
Кстати ты сам откуда, сколько тебе лет, где учился?
Yandex
Объявления
11.09.2009, 16:53     Задача Компьютерная игра C++
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru