/*
алг Перебор (Ситуация)
нач
если Ситуация конечная
то Завершающая обработка
иначе
нц для любого возможного действия
Применить действие к Ситуация
Вызвать алгоритм Перебор(Ситуация)
откатить действие назад
кц
все
кон
*/#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);//начать поиск с чила, куб которого меньше либо равно nwhile(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".
Вопрос: какие еще можно применить оптимизации? Как еще изменить алгоритм для полного прохождения тестов?
_> while(j>0){
_> int x = j*j*j;
_> if(n - x < 0) continue;
Странный оператор continue. Если он реализуется хоть раз, то никакие переменные не изменят свои значения, а цикл будет вечным.
_> int j=pow(n*1.0, 1.0/3.0);//начать поиск с чила, куб которого меньше либо равно n
Слишком большая верхняя граница перебора. И нет нужды рассматривать перестановки слагаемых. Куда лучше будет, если по-прежнему сохранить требование j³ ≤ n, но при этом потребовать чтобы одновременно j не превосходило предыдущего взятого значения (a[i-1], если оно определено, конечно).
Ну и округление вещественного числа в этой строке сделано плохо. Так, например, в некоторых очень популярных реализациях (int)pow(125*1.0, 1.0/3.0) == 4, хотя кубический корень из 125 равен 5.
_> while(j>0){
Нижняя граница слишком низка — незачем перебирать все малые x, если их суммы заведомо не хватит для достижения n.
W>Нижняя граница слишком низка — незачем перебирать все малые x, если их суммы заведомо не хватит для достижения n.
Большое спасибо, изменил
вот так
i++;
int j=(i>0 && pow(n*1.0, 1.0/3.0)<a[i-1])? a[i-1] : pow(n*1.0, 1.0/3.0);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--;
}
и всё получилось.
Для себя: остался вопрос:
Нижняя граница слишком низка — незачем перебирать все малые x, если их суммы заведомо не хватит для достижения n
Как определять нижнюю границу? Ведь, например правильным ответом на тест 776 будет последовательность 9 3 2 21 1 1 1. То есть "1" повторяются и их трудно "различать": надо ли им входить в ответ или нет.
_> и всё получилось.
Воистину верно говорят, что если программа не работает, то в ней есть как минимум одна ошибка, а если работает, то как минимум две ошибки :)
Ты своей заменой не уменьшил, а увеличил верхнюю границу. Не ускорил, а замедлил перебор. Примечательно если это скомпенсировало ошибку в условиях и позволило даже более медленной программе найти решение.
Хотя, конечно, лучше было бы сделать наоборот: исправить и ускорить.
_>
_>Нижняя граница слишком низка — незачем перебирать все малые x, если их суммы заведомо не хватит для достижения n
_>Как определять нижнюю границу?
Если число n можно разложить на сумму i кубов, то как минимум одно слагаемое будет не меньше n/i. В текущем же варианте (j > 0) проверяется условие, что слагаемое не меньше 1. Сравнение с n/i отсечёт больше вариантов чем сравнение с 1, и, конечно, при этом не потеряет решений.
Здравствуйте, watchmaker, Вы писали:
W>Хотя, конечно, лучше было бы сделать наоборот: исправить и ускорить.
Согласен с Вами, иправил и получил увеличение скорости почти в 3.5 раза если:
int j=(i>0 && pow(n*1.0, 1.0/3.0)>a[i-1])? a[i-1] : pow(n*1.0, 1.0/3.0);
и почти в 7 раз (правда увеличивается используемая память) если:
int j=(i>0 && pow(n*1.0, 1.0/3.0)+1>a[i-1])? a[i-1] : pow(n*1.0, 1.0/3.0)+1;
_>>
_>>Нижняя граница слишком низка — незачем перебирать все малые x, если их суммы заведомо не хватит для достижения n
_>>Как определять нижнюю границу? W>Если число n можно разложить на сумму i кубов, то как минимум одно слагаемое будет не меньше n/i. В текущем же варианте (j > 0) проверяется условие, что слагаемое не меньше 1. Сравнение с n/i отсечёт больше вариантов чем сравнение с 1, и, конечно, при этом не потеряет решений.
Что касается условия j >= n/i , то оно, как мне видится, потребует дополнительных проверок для случаев, когда, например, n=64. Тесты же допускают ответы типа 3 3 2 1 1, поэтому для данной задачи достаточно условия j > 0.
Спасибо за помощь
Здравствуйте, olimp_20, Вы писали:
W>>Если число n можно разложить на сумму i кубов, то как минимум одно слагаемое будет не меньше n/i. В текущем же варианте (j > 0) проверяется условие, что слагаемое не меньше 1. Сравнение с n/i отсечёт больше вариантов чем сравнение с 1, и, конечно, при этом не потеряет решений.
_>Что касается условия j >= n/i , то оно, как мне видится, потребует дополнительных проверок