【AOJ 2012】Space Coconut Grab
問題概要
Space Coconut Grab | Aizu Online Judge
エネルギーeが与えられるので、以下の条件を満たす最小のx+y+zを求めて下さい。
- x, y, z はいずれも非負の整数である.
- である.
ソースコード
#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が求まれば導き出せることに気づいてなんとか通せた. それにしても発想力が足りない.