2288A - Youmu Konpaku and the Duel
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:
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$$$.
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;
}








Auto comment: topic has been updated by koifishify (previous revision, new revision, compare).
Auto comment: topic has been updated by koifishify (previous revision, new revision, compare).