Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Задание Otherworld на с++.

Ирина Ученик (190), закрыт 1 год назад
Otherworld
Однажды Петя решил поиграть в игру Otherworld. В ней мальчика встретил волшебник, познакомивший его с правилами игры. Игра состоит из n измерений, в каждом из которых находится m шахт гоблинов. Изначально Петя находится в измерении с номером 1 . Игра заканчивается в измерении с номером n . Проходя каждое измерение, Петя обязан выполнить следующие действия: Выбрать любую шахту i -го измерения и забрать из нее все самоцветы Переместиться в измерение i+1 (если Петя сейчас находится в измерении с номером n , перемещение не происходит, и игра заканчивается) Задача Пети —собрать как можно больше самоцветов в процессе игры. Однако волшебник не любит жадных людей, поэтому если в i -м (i>1 ) измерении Петя захочет взять больше кристаллов, чем он взял в (i−1) -м измерении, волшебник завалит камнями дорогу к выходу. Петя плохо играет в стратегии, поэтому просит вас помочь ему пройти эту игру, либо сказать, что это невозможно.
Дополнен 1 год назад
Ввод
4 3
1 5 2
6 4 3
7 9 4
1 2 5
Вывод
15
2 2 3 2
Лучший ответ
Папа Высший разум (131252) 1 год назад
Не знаю, кого там не любит волшебник, но точно знаю, что тут не любят мутной постановки задач. На входе понадобятся данные: n, m, и n × m чисел, определяющих количество самоцветов. Например, в таком формате (сначала n и m, затем - по каждому i от 1 до n - по m чисел на строке):
 5 3
1 2 3
3 4 5
6 7 8
1 6 9
4 5 2
Это должно было быть описано в постановке задаче, а не нам самим гадать.
И что выводить в случае успеха, и что - в случае неудачи? Кто это будет проверять, автомат или человек? Если автомат, то он ожидает конкретных цифр и букв на входе и выходе, одна буква не там стоит - и зачтёт ошибку.

Каковы диапазоны значений? Сишного типа int хватит на них или нет?

Так-то алгоритм продумать - пять минут, и код написать - столько же, но если ввод или вывод не в том формате, то я уже написал, что будет.
 #include 
#include

using namespace std;

int main() {
size_t m, n;
cin >> n >> m;
size_t *s = new size_t[n];
unsigned total = 0, prev = UINT_MAX;
for (size_t i = 0; i < n && prev; i++) {
unsigned mx = 0;
for (size_t j = 0; j < m; j++) {
unsigned x;
cin >> x;
if (x > mx && x <= prev) {
mx = x;
s[i] = j + 1;
}
}
prev = mx;
total += mx;
}
if (prev) {
cout << total << endl;
const char *sep = "";
for (size_t i = 0; i < n; i++) {
cout << sep << s[i];
sep = " ";
}
cout << endl;
}
else cout << -1 << endl;
return 0;
}
Принцип прост: с первого уровня берём максимальное количество самоцветов, с каждого следующего - максимальное, но не превышающее то, что взяли на предыдущем уровне. Если такого не нашлось, то game over досрочно и с поражением.

Для приведённых в начале данных игру пройти не удастся. "Петя" заберёт с первых двух уровней по 3 самоцвета, а на третьем его забанит волшебник.

А вот с такими данными уже что-то получится:
 4 4
1 2 3 8
7 9 15 2
6 8 4 1
1 7 1 1
Результат:
 22
4 1 1 1
На первом уровне будет взято 8 самоцветов, на втором - 7, на третьем - 6, на четвёртом - 1, итого 8+7+6+1=22.

P.S. Я смотрю, с форматом входных данных я угадал. :-)
ИринаУченик (190) 1 год назад
Ввод
4 3
1 5 2
6 4 3
7 9 4
1 2 5
Вывод
15
2 2 3 2
вот пример
Папа Высший разум (131252) Ирина, а что такое 2 2 3 2 в конце?
ИринаУченик (190) 1 год назад
не знаю, просто вот это и 0 баллов
Папа Высший разум (131252) Ирина, а почему три числа? 5 тестов прошло, 1 не прошёл, а 33 - это что?
ТрифонЗнаток (418) 1 год назад
теперь это
Папа Высший разум (131252) Трифон Саламаха, наверное, тебе надо научиться копировать текст программы без ошибок.
Остальные ответы
Похожие вопросы