2288A. Youmu Konpaku and the Duel, O(1) Solution

Правка en19, от koifishify, 2026-11-22 05:41:04

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:

$$$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 + A(C) - \frac{\left(A-1\right)\left(A\right)}{2} \ge x$$$
$$$C\ \ge\ \frac{1}{A}\left(x+\frac{\left(A-2\right)\left(A-1\right)}{2}\right)-1$$$

Substitute back into original:

$$$M = C + A$$$
$$$M=\frac{1}{A}\left(x+\frac{\left(A-2\right)\left(A-1\right)}{2}\right)-1+A$$$

Differentiate with respect to $$$A$$$ using product rule, then rearrange:

$$$\frac{dM}{dA}=\frac{3}{2}-\frac{x+1}{a^{2}}$$$
$$$\frac{dM}{dA}=0\ \ \to\ 3A^{2}+6A-2x+1=0\ $$$
$$$A=\pm\sqrt{\frac{2}{3}\left(x+1\right)}$$$

By inspection M(A) is a positive hyperbola, so the minimum always occur on the right point. Hence:

$$$A=\sqrt{\frac{2}{3}\left(x+1\right)}$$$

For this value of $$$A$$$, $$$M$$$ is at its minimum. Therefore we only need to calculate $$$A$$$, then find $$$M$$$.

Теги c++, maths, contest

История

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