Minimum Cəmi Quruluşu#12262

Minimum Cəmi Quruluşu (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bizdən $1 \leq A_{i} \leq n$ 1 \le A_i \le n, $\sum_{i = 1}^{n} A_{i} = a$ \sum_{i=1}^n A_i = a və $\sum_{i = 1}^{n} min (A_{i}, b) = c$ \sum_{i=1}^n \min(A_i,b) = c olan $n$ uzunluğunda $A$ massivini qurmağı xahiş edirlər. Minimumla bağlı şərt məhdudlaşdırıcıdır, buna görə əvvəlcə bu cəmi düzgün edirik, sonra isə real cəmi düzəldirik.

Qeyd edin ki, biz heç vaxt $min (b, n)$ -dan böyük bir dəyərdən başlamalı deyilik, çünki dəyərlər hər halda $n$ ilə məhdudlaşır və $> b$ olan hər hansı bir dəyər məhdud cəminə $b$ eyni töhfəni verir. $B = min (b, n)$ B = \min(b,n) olsun. Əgər biz

A_{i} = B hər i = 1, \dots, n u ¨ c ¸ u ¨ n,

A_i = B \quad \text{hər } i=1,\dots,n \text{ üçün,}

o zaman hazırda

i = 1 \sum n min (A_{i}, b) = i = 1 \sum n B = n \cdot B,

\sum_{i=1}^n \min(A_i,b) = \sum_{i=1}^n B = n \cdot B,

və həmçinin

i = 1 \sum n A_{i} = n \cdot B .

\sum_{i=1}^n A_i = n \cdot B.

Bu cari məhdud cəmi $tot = n \cdot B$ \text{tot} = n \cdot B adlandıraq.

Biz məhdud cəmin tam olaraq $c$ olmasını istəyirik. Hazırda hər $A_{i} \leq B \leq b$ A_i \le B \le b olduğuna görə, $A_{i}$ A_i-ni $1$ azaldaraq $min (A_{i}, b)$ \min(A_i,b)-ni də $1$ azaldacağıq. Beləliklə, $i = 1$ i=1-dən $n$ -ə qədər irəliləyirik və $tot > c$ \text{tot} > c olduğu müddətdə $A_{i}$ A_i-ni azaltmağa çalışırıq. Müəyyən bir $i$ mövqeyi üçün daha çox azalda bilmirik, çünki hələ də artıqdır, və $1$ -dən aşağı düşə bilmərik, buna görə

v = min {tot - c, A_{i} - 1, B - 1}

v = \min\{\, \text{tot} - c,\; A_i - 1,\; B - 1 \,\}

alırıq və

A_{i} \leftarrow A_{i} - v, tot \leftarrow tot - v .

A_i \gets A_i - v,\quad \text{tot} \gets \text{tot} - v.

Bir keçiddən sonra bərabərlik

i = 1 \sum n min (A_{i}, b) = c

\sum_{i=1}^n \min(A_i,b) = c

yerinə yetirilir, çünki bəzi $A_{i} \leq b$ A_i \le b-dən çıxardığımız hər bir vahid məhdud cəmi dəqiq $1$ azaldır.

İndi real cəmi $\sum A_{i}$ \sum A_i-ni yoxlayırıq. Əgər $b \geq n$ b \ge n-dirsə, onda $B = n$ B = n və $min (A_{i}, b) = A_{i}$ \min(A_i,b) = A_i bütün $i$ üçün, beləliklə, məhdud cəm $c$ olduqda artıq $\sum A_{i} = c$ \sum A_i = c-dir, və bəyanatın garantiyası ilə bir həllin mövcud olduğunu bildiyimiz üçün $a = c$ a=c olmalıdır və işimiz bitdi.

Əgər $b \leq n$ b \le n-dirsə, onda azaldılma mərhələsindən sonra məhdud cəm düzgün, lakin bəlkə də

i = 1 \sum n A_{i} < a .

\sum_{i=1}^n A_i < a.

Realdan cəmi artırmaq üçün yalnız $A_{i} = b$ A_i = b olan mövqeləri dəyişdiririk. Belə bir $A_{i}$ A_i-ni $b + δ$ b + \delta-ya artırdıqda, burada $δ \leq n - b$ \delta \le n-b, onda

min (A_{i}, b) = b (dəyi s ¸ məz),

\min(A_i,b) = b \quad \text{(dəyişməz)},

amma real cəm $δ$ ilə artır. Beləliklə, yenidən skan edirik və hər dəfə $A_{i} = b$ A_i = b olduqda və cari cəm hələ də $< a$ olduqda, biz

δ = min (a - cəm, n - b)

\delta = \min(a - \text{cəm},\; n - b)

$A_{i}$ A_i-yə əlavə edirik. Problemin bir həllin mövcud olduğunu vəd etdiyi üçün, dəqiq cəm $a$ -ya çatmaq üçün kifayət qədər belə mövqeləri tapacağıq. $A_{i} \leq n$ A_i \le n şərtini heç vaxt pozmuruq, çünki yalnız $b$ -dən $n$ -ə qədər artırırıq.

Beləliklə, quruluş aşağıdakı kimidir:

hər şeyi $B = min (b, n)$ B = \min(b,n)-ya təyin edin;
ön tərəfdən azaldın ki, məhdud cəm $c$ -ya bərabər olsun;
əgər $b \leq n$ b \le n-dirsə, yalnız hazırda $b$ -ya bərabər olan mövqeləri artırın ki, real cəm $a$ -ya bərabər olsun.

Komplekslik $O (\sum n)$ \mathcal{O}(\sum n)-dir.

for _ in range(int(input())):
    n,a,b,c=map(int,input().split())
    base=min(b,n)
    res=[base]*n
    tot=n*base
    i=0
    while i<n and tot>c:
        v=min(tot-c,res[i]-1,base-1)
        if v>0:
            res[i]-=v
            tot-=v
        i+=1
    if b<=n:
        i=0
        while i<n and tot<a:
            if res[i]==b:
                v=min(a-tot,n-b)
                if v>0:
                    res[i]+=v
                    tot+=v
            i+=1
    print(*res)

Python