Problem 2012 : Space Coconut Crab

Space Coconut Crab

宇宙ヤシガニ
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2012

• 問題概要

x, y, z はいずれも非負の整数である．
x + y*y + z*z*z = e である．
上記の条件の下で x + y + z の値を最小にする．

• 解法

x, y, zのうち、二つをきめれば、eは固定なのでもうひとつが決まる。
なので、二重ループ。
オーダーを下げるため、zのループの中にyのループをいれてやり、xを確定させる。

• ソース

#include<iostream>

using namespace std;

main(){
  
  int n;

  while(cin >> n ){
    if(n==0)break;
    
    int ans = 10000000;

    for(int i=0; i*i*i<=n; i++){
      for(int j=0; i*i*i+j*j<=n; j++){
	ans = min(ans, i + j + (n - i*i*i - j*j));
      }
    }
    cout << ans << endl;
  }
}