Engineer bro!
Sun Oct 31 2021 (2 years ago)
Engineer by mistake!
I am a software engineer by passion
You are given two numbers, $$D\mathrm{\&}ND\; \backslash \&\; N$$. You have to find $$sum(N)sum(N)$$ applied $$DD$$ times.
(TOC generated by @dsabyte)
Yesterday, puppy Tuzik learned a magically efficient method to find the sum of the integers from $$11$$ to $$NN$$. He denotes it as $$sum(N)sum(N)$$. But today, like a true explorer, he defined his own new function: $$sum(D,N)sum(D,\; N)$$, which means the operation sum applied $$DD$$ times: the first time to $$NN$$ and each subsequent time to the result of the previous operation.
For example, if $$D=2D\; =\; 2$$ and $$N=3N\; =\; 3$$, then $$sum(2,3)sum(2,\; 3)$$ equals to $$sum(sum(3))=sum(1+2+3)=sum(6)=21sum(sum(3))\; =\; sum(1\; +\; 2\; +\; 3)\; =\; sum(6)\; =\; 21$$.
Tuzik wants to calculate some values of the $$sum(D,N)sum(D,\; N)$$ function. Will you help him with that?
The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing two integers D and N.
For each test case, output one integer on a separate line.
$$1\le T\le 161\; \le \; T\; \le \; 16$$
$$1\le D,N\le 41\; \le \; D,\; N\; \le \; 4$$
2
1 4
2 3
10
21
The problem will be simple if we just have to calculate $$sum(N)sum(N)$$ because from basic mathematics we already know the formula. The Sum of numbers from $$11$$ to $$NN$$ is $$\frac{n\ast (n+1)}{2}\backslash frac\{n*(n+1)\}\{2\}$$.
Using the above formula, we can find sum of the numbers from $$11$$ to $$NN$$ in just $$O(1)O(1)$$ time.
But, here we just don't have to calculate $$sum(n)sum(n)$$, we have to repeat it $$DD$$ times.
Let's dry run one of the above examples, $$D=2,N=3D=2,\; N=3$$.
Iteration | Function call | Numbers | Result |
---|---|---|---|
1 | $$sum(3)sum(3)$$ | $$1+2+31+2+3$$ | $$66$$ |
2 | $$sum(sum(3))=sum(6)sum(sum(3))\; =\; sum(6)$$ | $$1+2+3+4+5+61+2+3+4+5+6$$ | $$2121$$ |
Here, we can see that we just need to call native $$sum(n)sum(n)$$ function $$DD$$ times with the initial value of $$NN$$.
int main() {
int t;
cin >> t;
while (t--) {
int d, n;
cin >> d >> n;
int ans = n; // initialize and as n
for (int i = 0; i < d; i++) {
ans = (ans * (ans + 1)) / 2;
}
cout << ans << endl;
}
return 0;
}
Time - $$O(d\ast t)O(d*t)$$, $$O(d)O(d)$$ per test case
Space - $$O(1)O(1)$$
© 2021 dsabyte. All rights reserved