As the title says, I am trying to solve this problem which I couldn't find a solution on Youtube or somewhere else...

So here is the problem statement:

Eonathan Eostar decided to learn the magic of multiprocessor systems. He has a full binary tree of tasks with height h. In the beginning, there is only one ready task in the tree — the task in the root. At each moment of time, p processes choose at most p ready tasks and perform them. After that, tasks whose parents were performed become ready for the next moment of time. Once the task becomes ready, it stays ready until it is performed.
You shall calculate the smallest number of time moments the system needs to perform all the tasks.
Input:
The first line of the input contains the number of tests t (1≤t≤5⋅105). Each of the next t lines contains the description of a test. A test is described by two integers h (1≤h≤50) and p (1≤p≤104) — the height of the full binary tree and the number of processes. It is guaranteed that all the tests are different.
Output:
For each test output one integer on a separate line — the smallest number of time moments the system needs to perform all the tasks
Example:
input:
3
3 1
3 2
10 6
output:
7
4
173

I am a new C learner, so I thought of this way to solve this question:

1. I count all the nodes (pow(2,height)-1)
2. For each row I count the available nodes and put an if statement which says: If the available nodes at this row are smaller than the processors number then count , else while the available nodes are bigger than zero (node_at_m -= m[i])
   [node_at_m = Nodes available at this row; m[i] = processors number given in the question]

It gives correct answer for the first 2 cases which is (3 1) and (3 2) but it gives me wrong answer on the third case (10 6), so here is my code:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
int t, node,nodeatm, count;
cin >> t;
int n[t], m[t];

for (int i = 0; i < t; i  )
{
  cin >> n[i];
  cin >> m[i];
  node = pow(2,n[i])-1;
  count = 0;
  for(int q = 0; q < n[i]; q  )
  {
    nodeatm = pow(2,q);
    if(nodeatm <= m[i])
    {
      count  ;
    }
    else
    while(nodeatm > 0)
    {
      nodeatm -= m[i];
      count  ;
    }

  }
  cout << count << endl;
}

  return 0;
}

I am really not a big fan of posting Codeforces questions on here, but I couldn't find any resource for this question on the Internet...

Waiting your answers, thanks.

CodePudding user response：

The problem with above code is that you are incorrectly handeling the case when some of the tasks are remaining from previous level. You are assuming that all tasks must finished from one level before we move to another level.

Following is corrected code. You can see it working here:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t, node,nodeatm, count;
    cin >> t;
    int n[t], m[t];

    for (int i = 0; i < t; i  )
    {
      cin >> n[i];
      cin >> m[i];
      node = pow(2,n[i])-1;
      count = 0;
      int rem = 0;
      for(int q = 0; q < n[i]; q  )
      {
        nodeatm = pow(2,q)   rem ;
        if(nodeatm <= m[i])
        {
          count  ;
          rem = 0;
        }
        else
        {
            while(nodeatm >= m[i])
            {
                nodeatm -= m[i];
                count  ;
            }
            rem = nodeatm;
        }

      }
      
      if( rem )
      {
        count  ;
      }
      cout << count << endl;
    }

  return 0;
}

Following is a bit simplified code. You can see it working here:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i  )
    {
      int rem = 0, n, m, count = 0;
      cin >> n;
      cin >> m;
      for(int q = 0; q < n; q  )
      {
        int nodeatm = pow(2,q)   rem;
        if( nodeatm < m)
        {
            count  ;
            rem = 0;
        }
        else
        {
            count  = ( nodeatm/ m );
            rem = ( nodeatm % m );
        }

      }
      if( rem )
      {
        count  ;
      }
      cout << count << endl;
    }

  return 0;
}