2288A - Youmu Konpaku and the Duel This solution involves the use of calculus to find the minimum in $$$O(1)$$$.
We start by recognising that charges must occur before attacks. Let $$$M$$$ be the total amount of moves:
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$$$:
Using Gauss' formula:
Substitute back into original:
Differentiate with respect to $$$A$$$ using product rule, then rearrange:
By inspection $$$M(A)$$$ is a positive hyperbola, so the minimum always occur on the right point. Hence:
For this value of $$$A$$$, $$$M$$$ is at its minimum. Therefore we only need to calculate $$$A$$$, then find $$$M$$$.
#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; }




