WA at test#5
I am getting a WA at test #5
Here's my code :
#include <iostream>
using namespace std;
int main(){
int n,i=1,count=0;
cin>>n;
while(n>0){
if(i*i<=n)
i++;
else{
n-=(i-1)*(i-1);
i=1;
count++;
}
}
cout<<count<<endl;
return 0
}
Re: WA at test#5
Imagine you are given the following input: n=72. Given that 72 = 6*6 + 6*6 the answer should be 2, but your output is 3. This is happening because you are solving the problem using a greedy strategy. Here a greedy strategy does not work. If you want more information on why this technique does not work read chapter 15 and 16 of "Introduction to algorithms" by Cormen,Leiserson,Rivest and Stein.
Re: WA at test#5
Thanks for the explanation...
^_^
Re: WA at test#5
Posted by
V.Leo 29 Sep 2016 19:25
Thanks a lot~
Re: WA at test#5
60000
Edited by author 05.10.2016 10:30