ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1073. Square Country

WA at test#5
Posted by Gopesh Tulsyan 21 Sep 2014 14:18
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
Posted by frantrucco 10 Feb 2015 12:43
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
Posted by Umarjon 5 Oct 2016 10:30
60000

Edited by author 05.10.2016 10:30