DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

One Two Three 2

Back to problem

Editorial

Subtract 111 from every value, so the initial values are 0,1,20,1,20,1,2. If A<CA<CA<C, apply the reflection x↦2−xx\mapsto 2-xx↦2−x; hence assume A≥CA\ge CA≥C.

Let N=A+B+CN=A+B+CN=A+B+C, S=B+2CS=B+2CS=B+2C, g=gcd⁡(N,S, , and . The final value must be the global average . After any number of operations, every reduced denominator is a power of two, so the task is impossible if is not a power of two.

Assume that ppp is a power of two. Since A≥CA\ge CA≥C, we have q≤pq\le pq≤p. Let λ=max⁡(0,C−g⌊q2⌋)\lambda=\max\left(0,C-g\left\lfloor\dfrac q2\right\rfloor\right)λ. The minimum number of operations is .

Construction

If p>1p>1p>1, then qqq is odd. Make λ\lambdaλ groups of size 2p2p2p, each containing 2p−q,0,q2p-q,0,q copies of , respectively. Split the remaining elements into groups of size .

Bound

Build a graph GGG by joining two indices if they are ever used together, and let kkk be its number of connected components. If a component has size sss, its final sum sq/psq/psq/p must be an integer, so sss is divisible by . Write the component sizes as ; then .

The total time complexity is O(N)O(N)O(N).

Solution written by GPT5.6

)g=\gcd(N,S)
g=gcd(N,S)
p=Ngp=\dfrac Ngp=gN​
q=Sgq=\dfrac Sgq=gS​
q/pq/pq/p
ppp
=
max(0,C−g⌊2q​⌋)
N−g+λN-g+\lambdaN−g+λ
2
p
−
q,0,q
0,1,20,1,20,1,2
g−2λg-2\lambdag−2λ
ppp

If a size-ppp group contains ccc copies of 222, then its numbers of 0,1,20,1,20,1,2 must be p−q+cp-q+cp−q+c, q−2cq-2cq−2c, ccc. Thus 0≤c≤⌊q/2⌋0\le c\le\lfloor q/2\rfloor0≤c≤⌊q/2⌋, and the sum of ccc over all size-ppp groups must be C−λqC-\lambda qC−λq. The definition of λ\lambdaλ guarantees that this is possible.

Every group can be averaged in exactly its size minus one operations. A size-ppp group consists of 0,1,20,1,20,1,2 and has odd sum. Dividing every value of a size-2p2p2p group by 222 gives a 0,10,10,1 group with odd sum.

Consider a group of size D=2kD=2^kD=2k with values in {0,1,2}\{0,1,2\}{0,1,2} and odd sum qqq. Construct the operations backwards. Initially imagine DDD copies of the final average q/Dq/Dq/D. From two equal current values xxx, fix one position to an original integer a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2} and change the other backwards to 2x−a2x-a2x−a. This reverses one averaging operation.

When there are DDD active positions, let r=q mod Dr=q\bmod Dr=qmodD. Every active value has fractional part r/Dr/Dr/D, so only r/Dr/Dr/D and 1+r/D1+r/D1+r/D can occur. Let HHH be the number of high values and pair equal values.

  • If r<D/2r<D/2r<D/2, a low pair restores a 000 and leaves one low value. A high pair may restore a 111 and stay high, or restore a 222 and become low.
  • If r>D/2r>D/2r>D/2, a high pair restores a 222 and leaves one high value. A low pair may restore a 111 and stay low, or restore a 000 and become high.

The next level has D/2D/2D/2 active positions. For each state (D,H)(D,H)(D,H), the possible numbers of still-unrestored 222's form one integer interval. At D=2D=2D=2, the states are (H,c)=(0,0)(H,c)=(0,0)(H,c)=(0,0) and (2,1)(2,1)(2,1). The transitions above compute the intervals from small DDD upward. Prefix and suffix minima and maxima process one level in O(D)O(D)O(D) time, and the sum of all level sizes is O(D)O(D)O(D). During reconstruction, choose any transition whose next state remains feasible. Reversing the recorded backward operations gives exactly D−1D-1D−1 forward operations.

pp
p
ps1,ps2,…,pskps_1,ps_2,\ldots,ps_kps1​,ps2​,…,psk​
s1+s2+⋯+sk=gs_1+s_2+\cdots+s_k=gs1​+s2​+⋯+sk​=g

Let cic_ici​ be the initial number of 222's in component iii. Its sum is qsiqs_iqsi​, so ci≤⌊qsi2⌋c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloorci​≤⌊2qsi​. Since qqq is odd,

C≤∑i=1k⌊qsi2⌋=∑i=1k(si⌊q2⌋+⌊si2⌋)≤g⌊q2⌋+∑i=1k(si−1)=g⌊q2⌋+g−k.\begin{align*} C &\le \sum_{i=1}^k \left\lfloor \frac{qs_i}{2}\right\rfloor \\ &= \sum_{i=1}^k \left(s_i\left\lfloor\frac q2\right\rfloor+\left\lfloor\frac{s_i}{2}\right\rfloor\right) \\ &\le g\left\lfloor\frac q2\right\rfloor+\sum_{i=1}^k(s_i-1) \\ &= g\left\lfloor\frac q2\right\rfloor+g-k. \end{align*}C​≤i=1∑k​⌊

Hence k≤g−λk\le g-\lambdak≤g−λ. A connected component of size sss requires at least s−1s-1s−1 operations, so the total number of operations is at least

N−k≥N−g+λ.N-k\ge N-g+\lambda.N−k≥N−g+λ.
​
⌋
2
qsi​
​
⌋
=i=1∑k​(si​⌊2q​⌋+⌊2si​​⌋)
≤g⌊2q​⌋+i=1∑k​(si​−1)
=g⌊2q​⌋+g−k.
​