3747 - Bile 4

Enunț

Presupunem că avem două cutii notate A și B. Cutia A conține N bile numerotate cu numerele naturale distincte: 0, 1, 2, . . . , N − 1. Cutia B este goală.

Spunem că o bilă dintr-o cutie este bila specială a acestei cutii dacă numărul X cu care este numerotată această bilă este egal cu media aritmetică a numerelor celorlalte bile din cutie.

La un moment dat, cineva mută bila cu numărul K din cutia A în cutia B.

Vi se cere să alegeți alte K bile, din cutia A, pe care să le mutați în cutia B astfel încât cutia B să conțină K + 1 bile, iar bila cu numărul K să fie bila specială a cutiei B.

Cerința

Scrieți un program care citește numerele N și K, apoi determină:

1. dacă, înainte să fie mutate bile din cutia A în cutia B, există o bilă specială în cutia A; în caz afirmativ, programul determină numărul X cu care este numerotată această bilă specială;
2. cel mai mic (în sens lexicografic) șir strict crescător al numerelor celor K bile care pot fi mutate din cutia A în cutia B astfel încât bila cu numărul K să fie bila specială a cutiei B;
3. cel mai mare (în sens lexicografic) șir strict crescător al numerelor celor K bile care pot fi mutate din cutia A în cutia B astfel încât bila cu numărul K să fie bila specială a cutiei B.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie trei numere naturale C, N și K, separate prin câte un spațiu. C reprezintă cerința care trebuie rezolvată (1, 2 sau 3), iar N și K au semnificația din enunț.

Date de ieșire

Fișierul de ieșire output.txt va conține:

• dacă C = 1, pe prima linie, numărul natural X reprezentând numârul bilei speciale din cutia A sau valoarea −1 dacă cutia A nu conține o astfel de bilă (reprezentând răspunsul la cerința 1);
• dacă C = 2, pe prima linie, un șir strict crescător de K numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 2);
• dacă C = 3, pe prima linie, un șir strict crescător de K numere naturale, separate prin câte un spațiu (reprezentând răspunsul la cerința 3).

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• N număr natural, 4 ≤ N ≤ 100000
• K număr natural, 2 ≤ K ≤ N/2

Exemplul 1

input.txt:

1 9 3

output.txt:

4

Explicație:

Se rezolvă cerința 1.

N = 9. Avem 9 bile inscript, ionate cu 0, 1, 2, 3, 4, 5, 6, 7, 8.

Bila specială este X = 4 deoarece: X = (0 + 1 + 2 + 3 + 5 + 6 + 7 + 8)/8 = 32/8 = 4

Exemplul 2

input.txt:

1 3 3

output.txt:

-1

Explicație:

Se rezolvă cerința 1.

N = 8. Se va scrie în fișierul de ieșire valoarea −1 deoarece cutia A nu conține nicio bilă specială.

Exemplul 3

input.txt:

9999999 8 3

Ouput:

ValueError: Invalid value for C

Rezolvare

# Function to validate input constraints
def validate_input_constraints(C, N, K):
    if not (1 <= C <= 3):
        raise ValueError("Invalid value for C")
    if not (4 <= N <= 100000):
        raise ValueError("Invalid value for N")
    if not (2 <= K <= N // 2):
        raise ValueError("Invalid value for K")

# Open input and output files
fin = open("input.txt", "r")
fout = open("output.txt", "w")

# Read input values
C, N, K = map(int, fin.readline().split())

# Validate input constraints
validate_input_constraints(C, N, K)

# Function to write the result to the output file
def write_result(s):
    fout.write(" ".join(map(str, s)) + '\n')

# Function for case 1
def c1():
    if N % 2 == 1:
        fout.write(str((N - 1) // 2) + '\n')
    else:
        fout.write("-1\n")

# Function for case 2
def c2():
    K_square = K * K
    S = 0
    s = [0] * K

    for i in range(K - 1):
        s[i] = i
        S += s[i]

    if K_square - S <= N - 1:
        s[K - 1] = K_square - S
        write_result(s)
        return

    s[K - 1] = K - 1
    S += s[K - 1]

    dif = K_square - S
    g = dif // (N - K)
    rest = dif % (N - K)

    for i in range(1, g + 1):
        s[K - i] += (N - K)

    if s[K - (g + 1)] + rest != K:
        s[K - (g + 1)] += rest
    else:
        s[K - (g + 1)] += (rest + 1)
        s[K - g] -= 1

    write_result(s)

# Function for case 3
def c3():
    s = [0] * K

    if K % 2 == 0:
        # K is even
        m = K // 2
        for i in range(K):
            s[i] = m
            m += 1
            if m == K:
                m += 1
        write_result(s)
        return

    # K is odd
    M = K // 2
    s[0] = M
    s[K - 1] = 2 * K + 1 - s[0]
    s[M] = K - 1

    for i in range(1, M):
        s[i] = M + i
        s[K - 1 - i] = 2 * K - s[i]

    write_result(s)

# Main program
if C == 1:
    c1()
elif C == 2:
    c2()
elif C == 3:
    c3()

# Close input and output files
fin.close()
fout.close()