Ceiling Sum#13038

Ceiling Sum (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Every pair contributes at least $1$ , so the all-ones array gives $(2 n)$ \binom{n}{2}. Let $M = 1 0^{9}$ M=10^9, $D = M - 1$ D=M-1 and

E = k - (2 n)

E=k-\binom{n}{2}

be the excess we must add.

Structure the array as a prefix of ones, then a block of $c$ large values, then exactly $q$ trailing ones. If the large values are non-decreasing, every pair inside the block costs $1$ ; a large value $v$ pays $v - 1$ v-1 against each of the $q$ trailing ones. Writing $E = q \cdot T + I$ E=q\cdot T+I with $I = E mod q$ I=E\bmod q, the block must supply a base contribution of $T$ and generate exactly $I$ extra from its internal pairs.

To reach $T$ greedily, set $c - 1$ c-1 values to $M$ and put the deficit in a single value $V = T - (c - 1) D + 1$ V=T-(c-1)D+1. The $I$ extra units come from shifting $V$ right by $I$ positions among the $M$ 's: each preceding $M$ then pays $⌈ M / V ⌉$ instead of $1$ . This is worth exactly $+ 1$ per position only when

\frac{M}{2} < V < M,

\tfrac{M}{2}<V<M,

so both bounds must be enforced. A single smaller element among $c - 1$ c-1 larger ones creates at most $c - 1$ c-1 such pairs, hence $I < c$ I<c is required, and the layout must fit, $c + q \leq n$ c+q\le n.

Taking $c = ⌈ T / D ⌉$ c=\lceil T/D\rceil breaks the upper bound: when $D ∣ T$ D\mid T the greedy fills every slot to capacity, $V = M$ V=M, and each intended pair degenerates to $⌈ M / M ⌉ = 1$ \lceil M/M\rceil=1, leaving the sum short by exactly $I$ . For $I > 0$ I>0 take instead

c = ⌊ \frac{T}{D} ⌋ + 1, V = (T mod D) + 1 \in [1, D],

c=\left\lfloor \frac{T}{D}\right\rfloor+1,\qquad V=(T\bmod D)+1\in[1,D],

which guarantees $V < M$ V<M and $T < cD$ T<cD.

If $V \leq M /2$ V\le M/2 the greedy placement is abandoned and the sum is spread evenly: with $S = T + c = c Q + r$ S=T+c=cQ+r, set $X = Q + 1$ X=Q+1 and $Y = S - (c - 1) X = Q + r - c + 1$ Y=S-(c-1)X=Q+r-c+1, so $(c - 1) (X - 1) + (Y - 1) = T$ (c-1)(X-1)+(Y-1)=T identically. Here $T < cD$ T<cD gives $X \leq M$ X\le M, and $Q > \frac{( c - 1 ) D}{c} \geq \frac{D}{2}$ Q>\frac{(c-1)D}{c}\ge\frac{D}{2} against $c \leq 1 0^{6}$ c\le 10^6 gives $2 Y - X = Q + 2 r - 2 c + 1 > 0$ 2Y-X=Q+2r-2c+1>0, so $Y < X \leq 2 Y$ Y<X\le 2Y and the $I$ shifted positions again pay exactly $+ 1$ each.

Since $k \leq 1 0^{12}$ k\le 10^{12}, the choice $q = 1$ q=1 already succeeds whenever $n - 1 \geq ⌈ E / D ⌉$ n-1\ge\lceil E/D\rceil, so the loop advances past $q = 1$ q=1 only for $n \leq 1002$ n\le 1002: the scan is $O (min (n, 1002))$ O(\min(n,1002)) and the construction is $O (n)$ per test, $O (\sum n)$ O(\sum n) overall.

def solve():
    n,k=map(int,input().split())
    E=k-n*(n-1)//2
    if E==0:
        print(*[1]*n)
        return
    for q in range(1,n):
        I,T=E%q,E//q
        c=(T+999999998)//999999999
        if I>0 and T%999999999==0: c+=1
        if c<=n-q and I<c:
            V=T-(c-1)*999999999+1
            X,Y=1000000000,V
            if I>0 and V<=500000000:
                X=(T+c)//c+1
                Y=T+c-(c-1)*X
            print(*([1]*(n-q-c)+[X]*I+[Y]+[X]*(c-I-1)+[1]*q))
            return
for _ in range(int(input())):
    solve()

Python