Условие задачи:
сайт1 ,
сайт2
| Код программы |
| /*
алг Перебор (Ситуация)
нач
если Ситуация конечная
то Завершающая обработка
иначе
нц для любого возможного действия
Применить действие к Ситуация
Вызвать алгоритм Перебор(Ситуация)
откатить действие назад
кц
все
кон
*/
#include <stdio.h>
#include <vector>
#include <cmath>
using namespace std;
vector<int> a(8,0);//вектор чисел
bool numb3(int i, int n);
//-----------------------------------------------------
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
scanf("%d", &n);
if(numb3(-1, n)==false) //алгоритм перебора с возвратом
printf("IMPOSSIBLE\n");
return 0;
}
//-----------------------------------------------------
bool numb3( int i, int n )
{
if(n==0){//вывести ответ
for(int z=0; z<i; ++z)
printf("%d ", a[z]);
printf("%d\n", a[i]);
return true;
}
if(i==7)return false;//если индекс уже больше, а ответа нет
i++;//следующее место для числа в массиве
int j=pow(n*1.0, 1.0/3.0);//начать поиск с чила, куб которого меньше либо равно n
while(j>0){
int x = j*j*j;
if(n - x < 0) continue;
a[i]=j;
if(numb3(i, n - x)) return true; //возвращаем ответ
a[i]=0;
j--;
}
i--; //переходим к предыдущему месту в массиве
return false;
}
|
| |
Проблема: на первом сайте пройдены все тесты, на втором — лишь 14, после чего "Time limit exceeded".
Вопрос: какие еще можно применить оптимизации? Как еще изменить алгоритм для полного прохождения тестов?