[problem:2288A]↵
↵
This solution involves the use of calculus to find the minimum in $O(1)$.↵
↵
Implementation↵
--------------↵
↵
We start by recognising that charges must occur before attacks. Let $M$ be the total amount of moves:↵
↵
$$M=C+A$$↵
↵
After $C$ moves to charge, we reach the maximum attack power of $1+C$ (since we perform $+1\+1\+1\+\ \dots,\ C$ times). Then, we must make the minimum amount of attacking moves $A$ such that the total damage $ATK_{tot}$ is greater than or equal to the yokai's health $x$. Since max attack power is $1+C$:↵
↵
$$\underbrace{C+1,\ C,\ C-1,\ C-2,\ \dots,\ C-\left(A-2\right)}_{A\ \text{times}}$$↵
↵
$$(C+1) + (C) + (C - 1) + ... + (C - (A - 1)) \ge x$$↵
Using Gauss' formula:↵
$$C+1\ +\ C\ +\left(A-2\right)C\+-\ \frac{\left(A-2\right)\left(A-1\right)}{2} \ge x$$↵
$$C\ \ge\ \frac{x+\frac{\left(A-1\right)\left(A-2\right)}{2}-1}{A}$$↵
↵
Substitute back into original:↵
↵
$$M = C + A$$↵
$$M=\frac{1}{A}\left(x+\frac{\left(A-1\right)\left(A-2\right)}{2}-1\right)+A$$↵
Differentiate with respect to $A$ using product rule, then rearrange:↵
$$\frac{dM}{dA}=\frac{2}{3}-\frac{x}{A^{2}}$$↵
$$\frac{dM}{dA}=0$$↵
$$A=\pm\sqrt{\frac{2}{3}x}$$↵
↵
By inspection $M(A)$ is a positive hyperbola, so the minimum always occur on the right point. Hence:↵
$$A=\sqrt{\frac{2}{3}x}$$↵
↵
For this value of $A$, $M$ is at its minimum. Therefore we only need to calculate $A$, then find $M$.↵
↵
Code↵
----↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
int M(double A, double x) {↵
double totSub = (A-1)*(A-2)/2;↵
double C = ((x + totSub - 1)/((A)));↵
return ceil(C + A);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0);↵
int _; cin >> _;↵
↵
for(int t = 0; t < _; t++) {↵
double x;↵
cin >> x;↵
↵
double A = sqrt(2 * (x) / 3);↵
cout << M(A,x);↵
↵
if (t != _-1) {↵
cout << "\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~
↵
This solution involves the use of calculus to find the minimum in $O(1)$.↵
↵
Implementation↵
--------------↵
↵
We start by recognising that charges must occur before attacks. Let $M$ be the total amount of moves:↵
↵
$$M=C+A$$↵
↵
After $C$ moves to charge, we reach the maximum attack power of $1+C$ (since we perform $+1\+1\+1\+\ \dots,\ C$ times). Then, we must make the minimum amount of attacking moves $A$ such that the total damage $ATK_{tot}$ is greater than or equal to the yokai's health $x$. Since max attack power is $1+C$:↵
↵
$$\underbrace{C+1,\ C,\ C-1,\ C-2,\ \dots,\ C-\left(A-2\right)}_{A\ \text{times}}$$↵
↵
$$(C+1) + (C) + (C - 1) + ... + (C - (A - 1)) \ge x$$↵
Using Gauss' formula:↵
$$C+1\ +\ C\ +\left(A-2\right)C\
$$C\ \ge\ \frac{x+\frac{\left(A-1\right)\left(A-2\right)}{2}-1}{A}$$↵
↵
Substitute back into original:↵
↵
$$M = C + A$$↵
$$M=\frac{1}{A}\left(x+\frac{\left(A-1\right)\left(A-2\right)}{2}-1\right)+A$$↵
Differentiate with respect to $A$ using product rule, then rearrange:↵
$$\frac{dM}{dA}=\frac{2}{3}-\frac{x}{A^{2}}$$↵
$$\frac{dM}{dA}=0$$↵
$$A=\pm\sqrt{\frac{2}{3}x}$$↵
↵
By inspection $M(A)$ is a positive hyperbola, so the minimum always occur on the right point. Hence:↵
$$A=\sqrt{\frac{2}{3}x}$$↵
↵
For this value of $A$, $M$ is at its minimum. Therefore we only need to calculate $A$, then find $M$.↵
↵
Code↵
----↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
int M(double A, double x) {↵
double totSub = (A-1)*(A-2)/2;↵
double C = ((x + totSub - 1)/((A)));↵
return ceil(C + A);↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0); cin.tie(0);↵
int _; cin >> _;↵
↵
for(int t = 0; t < _; t++) {↵
double x;↵
cin >> x;↵
↵
double A = sqrt(2 * (x) / 3);↵
cout << M(A,x);↵
↵
if (t != _-1) {↵
cout << "\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~



