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 1658. Sum of Digits

Raman Gupta WA 1 [3] // Problem 1658. Sum of Digits 3 Dec 2012 19:49
All the test cases given in this forum are working.But giving WA 1

my code is:
#include <stdio.h>
#include <string.h>
 int len[910][8110];
 int dig[910][8110];
 int num[110];

 int main(){
  int t,s1,s2,k,pt,i,j,l,temp;
  memset(len,0,sizeof(len));
  for(i=1;i<=900;i++){
      for(j=1;j<=8100;j++){
          for(k=1;k<=9;k++){
              if((i-k)<0||(j-k*k)<0)
                  break;
              else if((i-k)==0&&(j-k*k)==0){
                  len[i][j] = 1;
                  dig[i][j] = k;
              }
              else if(len[i-k][j-k*k]>0){
                  if(len[i-k][j-k*k]+1<len[i][j]||len[i][j]==0){
                      len[i][j] = len[i-k][j-k*k]+1;
                      dig[i][j] = k;
                  }
              }
              else
                  continue;
          }
      }
  }
  scanf("%d",&t);
  while(t--){
  scanf("%d %d",&s1,&s2);
  pt = 0;
  if(len[s1][s2]==0||len[s1][s2]>100)
      printf("No Solution");
  else{
        i=s1;
        j=s2;
      while((len[i][j]>=1)&&i>=1&&j>=1){
          l = dig[i][j];
          num[pt++] = l;
          i = i-l;
          l = l*l;
          j-=l;
      }
      for(i=0;i<pt;i++){
        for(j=i+1;j<pt;j++){
            if(num[i]>num[j]){
             temp=num[i];
             num[i]=num[j];
             num[j] = temp;
            }
        }
      }
      for(i=0;i<pt;i++)
          printf("%d",num[i]);
  }
  printf("\n");
  }
  return 0;
 }
esger Re: WA 1 [1] // Problem 1658. Sum of Digits 9 Apr 2013 13:40
Your mistake is here:

      if(len[i-k][j-k*k]+1<len[i][j]||len[i][j]==0){
          len[i][j] = len[i-k][j-k*k]+1;
          dig[i][j] = k;
          }
length might be the same but the value might be smaller. You just check the length.
Mahilewets Re: WA 1 // Problem 1658. Sum of Digits 18 Jul 2017 18:40
I am able to see experimentally that length really might be the same while the values differ

I can't understand why it so

I feel that it can't be truth
HellKitsune Re: WA 1 // Problem 1658. Sum of Digits 9 Apr 2014 02:24
"S" in "Solution" shouldn't be capital :P