İşarəli permutasiya#12211

İşarəli permutasiya (Həll təhlili)

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

Unutmayın ki, permutasiyanın maksimum cəmi heç bir şey etmədən öz permutasiyasıdır ki, bu da

S = 1 + 2 + 3 + ... + n = \frac{n ( n + 1 )}{2}

\displaystyle S=1+2+3+...+n=\frac{n(n+1)}{2}

$b$ ədədini $p$ -dən mənfi etmək deməkdir ki, $S \to S - 2 x$ S \rightarrow S-2x , bu, istənilən uzunluqdakı $m$ alt dəstinin cəmi üçün də keçərlidir, beləliklə, bir permutasiyanın mövcud olması üçün kifayət qədər şərtimiz var:

[S mod 2 = k mod 2]

[S \bmod 2 = k \bmod 2]

Beləliklə, mənfi ədədlərin alt dəstəsinin cəmini $X = \frac{S - k}{2}$ X=\frac{S-k}{2} olaraq əldə edə bilərik. Alt dəstənin cəmini məhdudlaşdıra bilərik, bu da ən azı

1 + 2 + 3 + ... + m = \frac{m ( m + 1 )}{2}

1+2+3+...+m=\frac{m(m+1)}{2}

, və ən çox $m$ ədədini ən yüksəkdən

m + (n - 1) + (n - 2) + ... + (n - m + 1) = S - \frac{( n - m ) ( n - m + 1 )}{2}

m+(n-1)+(n-2)+...+(n-m+1)=S-\frac{(n-m)(n-m+1)}{2}

əldə edə bilərik. Əgər $X$ bu aralıqda məhdudlaşmırsa, onda belə bir permutasiyanın mövcud olmadığı açıqdır.

Nəhayət, ədədləri şirnikləndirərək seçə bilərik ki, həmişə növbəti hərəkətdə ədədlərlə oynamağa sahəmiz olsun.

Həll

for _ in range(int(input())):
    n,m,k=map(int,input().split())
    S=n*(n+1)//2
    if (S-k)&1 or k>S:
        print(-1); continue
    X=(S-k)//2
    lo=m*(m+1)//2
    hi=S-(n-m)*(n-m+1)//2
    if X<lo or X>hi:
        print(-1); continue
    neg=[False]*(n+1)
    rem=m; target=X
    for i in range(n,0,-1):
        if rem==0: break
        if target>=i and target-i>=(rem-1)*rem//2:
            neg[i]=True
            target-=i
            rem-=1
    if rem or target:
        print(-1); continue
    print(*(-i if neg[i] else i for i in range(1,n+1)))

Komplekslik $O (n)$