日々精進

aikoと旅行とプログラミング

【AOJ 2012】Space Coconut Grab

問題概要

Space Coconut Grab | Aizu Online Judge

エネルギーeが与えられるので、以下の条件を満たす最小のx+y+zを求めて下さい。

  • x, y, z はいずれも非負の整数である.
  •  {x + y^2 + z^3 = e } である.

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define N 1000000

int solve(int in){
  int ans=N;
  for(int z = 0 ; z*z*z <= in ; z++){
    for(int y = 0 ; y*y <= in-z*z*z ; y++){
      int x = in - y*y - z*z*z;
      ans = min(x+y+z,ans);
    }
  }
  return ans;
}

int main(){
  int n;
  while(cin >> n,n){
    cout << solve(n) << '\n';
  }
}

最初x,y,zそれぞれをループさせていてTLE. ループが悪いのは自明なので減らせないか考えると, xはzとyが求まれば導き出せることに気づいてなんとか通せた. それにしても発想力が足りない.