koifishify's blog

By koifishify, history, 2 hours ago, In English

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:

$$$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; }
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
41 minute(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
31 minute(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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