C++

Forum

 
one problem of minimizing the digit's sum

cEEaser (4)
You are given positive integers N and D. You may perform operations of the following two types:

add D to N, i.e. change N to N+D
change N to digitsum(N)
Here, digitsum(x) is the sum of decimal digits of x. For example, digitsum(123)=1+2+3=6, digitsum(100)=1+0+0=1, digitsum(365)=3+6+5=14.

You may perform any number of operations (including zero) in any order. Please find the minimum obtainable value of N and the minimum number of operations required to obtain this value.


I am getting the wrong answer for some test cases please let me know where I am wrong

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
    #include<iostream>
    #include<queue>  
    using namespace std;
    void check(long long int a, long long int &b, long long int &c, long long 
    int d)
    {
      if(a<b)
      {
        b = a;
        c = d;
      }
    }
    int digitSum(long long int a)
    {
      int num = 0;
      while(a>0)
      {
        num += a%10;
        a = a/10;
      }
      return num;
    }
    void func(int N, int D, long long int &minElement, long long int 
    &minTrial)
    {
       queue<long long int> q;
       q.push(N);
       if(N==1)
       {
          minElement = 1;
          minTrial = 0;
       }
       long long int countNodes = q.size();
       long long int level = 1;
       int cnt = 1;
       while(!q.empty())
       {
          countNodes = q.size();
          while(countNodes>0)
          {
            long long int temp = q.front();
            q.pop();
            long long int first = temp+D;
            check(first,minElement,minTrial,level);
            if(minElement == 1)
            {
                return;
            }
            q.push(first);
            long long second = digitSum(temp);
            check(second,minElement,minTrial,level);

            if(minElement == 1)
            {
                return;
            }
            q.push(second);
            countNodes--;
            cnt++;
            if(cnt>1000000)
            {
                break;
            }
          }
        if(cnt>1000000)
        {
            break;
        }
        level++;
      }
    }
    int main()
    {
      long long int t = 1;
      cin>>t;
      while(t--)
      {
        long long int N, D;
        cin>>N>>D;
        long long int minElement = 1e18, minTrial = 1e18;
        func(N,D,minElement, minTrial);
        cout<<minElement<<" "<<minTrial<<endl;
      }
      return 0;
    }



Example Input
3
2 1
9 3
11 13
Example Output
1 9
3 2
1 4
Explanation
Example case 1: The value N=1 can be achieved by 8 successive "add" operations (changing N to 10) and one "digit-sum" operation.

Example case 2: You can prove that you cannot obtain N=1 and N=2, and you can obtain N=3. The value N=3 can be achieved by one "add" and one "digitsum" operation, changing 9 to 12 and 12 to 3.

Example case 3: N=1 can be achieved by operations "add", "add", "digitsum", "digitsum": 11→24→37→10→1.
Last edited on
saeidsj (23)
what you want to do?

can you explain alittel....
saeidsj (23)
it is not complicated you have to just use a loop for that
for example:

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <iostream>
 int main(){
     int x;
     int sum=0;
     std::cin>>x;
     while(x>10){
         sum=sum+(x%10);
         x=x/10;
     }
     sum+=x;
     std::cout<<sum;
 }

but for the rest you made it very compilicated
put some comments in code
Last edited on
saeidsj (23)
why you used an infinite loop in your main?
tpb (1495)
It's a pretty brute-force approach.
Is the "cnt break" the only reason you're not timing out?
Maybe a million is not enough iterations.
cEEaser (4)
@tpb i am not getting tle i am getting wrong answer in some test cases
Last edited on
cEEaser (4)
@saeidsjI updated the question see the last line.
tpb (1495)
I asked if the "cnt break" is the only thing stopping you from getting TLE?
Have you tried it with a limit of TWO million?

Do you have an example of a problem that your program gets wrong?
saeidsj (23)
give us a wrong case!!!
cEEaser (4)
@saiedsj i don't know where the program is failing
lazybot (8)
@cEEaser try out these test cases(dry run as you are getting WA on some test cases)- 525 496 ans-1 9, 511 487 ans-1 5 and 755 979 ans-1 10
Topic archived. No new replies allowed.