O(1) Solution: 2288A. Youmu Konpaku and the Duel
Difference between en28 and en29, changed 2 character(s)
[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;↵
}↵
~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en29 English koifishify 2026-11-22 06:54:49 2 Tiny change: '\right)C\ +\ \frac{\l' -> '\right)C\ -\ \frac{\l'
en28 English koifishify 2026-11-22 06:13:08 0 (published)
en27 English koifishify 2026-11-22 06:03:14 36
en26 English koifishify 2026-11-22 05:56:03 42
en25 English koifishify 2026-11-22 05:54:51 114
en24 English koifishify 2026-11-22 05:53:43 575
en23 English koifishify 2026-11-22 05:49:54 1 Tiny change: 'range:\n$$frac{dM}{d' -> 'range:\n$$\frac{dM}{d'
en22 English koifishify 2026-11-22 05:49:23 13
en21 English koifishify 2026-11-22 05:48:09 41
en20 English koifishify 2026-11-22 05:45:37 59
en19 English koifishify 2026-11-22 05:41:04 69
en18 English koifishify 2026-11-22 05:39:48 1 Tiny change: 'C-2,\ \dot,\ C-\left' -> 'C-2,\ \dots,\ C-\left'
en17 English koifishify 2026-11-22 05:39:35 37
en16 English koifishify 2026-11-22 05:37:51 95
en15 English koifishify 2026-11-22 05:17:38 102
en14 English koifishify 2026-11-22 05:13:34 44
en13 English koifishify 2026-11-22 05:12:41 82
en12 English koifishify 2026-11-22 05:08:07 2 Tiny change: '}{2}}{A+1}+A$$\nProd' -> '}{2}}{A+1}-1+A$$\nProd'
en11 English koifishify 2026-11-22 05:06:08 294
en10 English koifishify 2026-11-22 05:00:00 161
en9 English koifishify 2026-11-22 04:56:30 19
en8 English koifishify 2026-11-22 04:52:52 51
en7 English koifishify 2026-11-22 04:51:40 173
en6 English koifishify 2026-11-22 04:46:50 106
en5 English koifishify 2026-11-22 04:45:01 126
en4 English koifishify 2026-11-22 04:43:01 12 Tiny change: ' is:\n\n$$(ATK) + (A' -> ' is:\n\n$$ATK_{tot} = (ATK) + (A'
en3 English koifishify 2026-11-22 04:41:43 242
en2 English koifishify 2026-11-22 04:36:46 309
en1 English koifishify 2026-11-22 04:30:58 292 Initial revision (saved to drafts)