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

C++

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

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

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

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

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

http://********/?main=task&id_task=29
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 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
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:40     Задача Компьютерная игра C++ #14
Я тут думал как написать программу которая выуживает от них все тесты
Похоже у них задачи компилируются Visual Studio, а не gcc.
Можно написать сетевую программу, которая посылает все файлы INPUT.TXT по сети.
Правда для этого придется решить все задачи

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

Добавлено через 3 минуты
Кстати ты сам откуда, сколько тебе лет, где учился?
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 17:21     Задача Компьютерная игра C++ #16
Исправил ошибки.
Там крайние значения нужно отдельно проверять - нельзя заменять 0-ем !
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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];
 
 
if ( n<=2 ) {
    if ( n <= 0 ) {
        return 0;
    } else if ( n == 1 ) {
        /* MUST BE 0, BUT !!! */
        return energy[1];
    } else { /* n == 2 */
        energy[2]= 0;
 
        i= n-1;
        var0= abs( height[i]-height[i+1] );
        energy[i]= var0;
        goto ret_all;
    }
} 
 
/* n-1 */
i= n-1;
var0= abs( height[i]-height[i+1] );
energy[i]= var0;
 
for ( i= n-2; i>=1; i-- ) {
        var0= abs( height[i]-height[i+1] )+energy[i+1];
        var1= 3*abs( height[i]-height[i+2] )+energy[i+2];
        if ( var0<=var1 ) {
            energy[i]= var0;
            fprintf( stderr, "energy[%d]=%d, jump to %d\n", i, energy[i], i+1 );
        } else {
            energy[i]= var1;
            fprintf( stderr, "energy[%d]=%d, long jump to %d\n", i, energy[i], i+2 );
        }
}
 
ret_all:
return energy[1];
 
} // calc_min_energy()
Добавлено через 3 минуты
Ну решаю пока задачи для нубов - то есть для начинающих.

Добавлено через 34 секунды
Потом отсюда код возъму для 29-ой задачи

Добавлено через 21 минуту
Ну что - сдал 29-ую задачу ?
jds_07
27 / 26 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 17:23  [ТС]     Задача Компьютерная игра C++ #17
Нет не принимает. Пишет TLE. Дома посмотрю может там что-то не так.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 19:53     Задача Компьютерная игра C++ #18
Ну правильно - я там отладочный код оставил.
И с границами накосячил.
Вот вроде все тесты проходит.
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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+1];
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];
 
 
if ( n<=1 ) {
        if ( n <= 0 ) {
                return 0;
        } else { /* n == 1 */
                /* MUST BE 0, BUT !!! */
                return height[1];
        }
}
 
/* n */
energy[n]= 0;
 
/* n-1 */
i= n-1;
var0= abs( height[i]-height[i+1] );
energy[i]= var0;
 
for ( i= n-2; 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()
Добавлено через 3 минуты
Все - сдал я эту задачу с 1-го раза.
Но не этот код кстати
Спасибо за два теста.
Догадаться что при n==1 нужно возвращать высоту 1-ой платформы невозможно - это ошибка их теста.
И догадаться что 0 может быть высотой тоже нельзя - это ошибка в условии.
Karina
Сообщений: n/a
13.09.2009, 23:00     Задача Компьютерная игра C++ #19
Ага, привет всем) Как вы уже поняли, я девушка, а также я далека от программирования, но...на ум пришла идея..хотелось бы попробовать реализовать ее самостоятельно...так вот, не подскажите ли, на каком языке программирования написана программа вконтакте, хм...кажется, как-то так это должно звучать)

Добавлено через 2 минуты
и не называйте меня нубом, пожалуйста, как-то неочень звучит...)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.09.2009, 19:51     Задача Компьютерная игра C++
Еще ссылки по теме:

C++ Компьютерная игра (платформы)
C++ Компьютерная графика
Компьютерная графика C++
C++ Игра в крестики нолики, задача почти решена но результат не выводится на экран

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

Или воспользуйтесь поиском по форуму:
fantaz1
33 / 25 / 1
Регистрация: 08.11.2008
Сообщений: 107
14.09.2009, 19:51     Задача Компьютерная игра C++ #20
Цитата Сообщение от Karina Посмотреть сообщение
Ага, привет всем) Как вы уже поняли, я девушка, а также я далека от программирования, но...на ум пришла идея..хотелось бы попробовать реализовать ее самостоятельно...так вот, не подскажите ли, на каком языке программирования написана программа вконтакте, хм...кажется, как-то так это должно звучать)
хм... На сколько я знаю Вконтакте это ваще то не программа, а сайт...
Yandex
Объявления
14.09.2009, 19:51     Задача Компьютерная игра C++
Ответ Создать тему
Опции темы

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