Editing 3747 - Bile 4

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

Spunem că o bilă dintr-o cutie este <code>bila specială</code> a acestei cutii dacă numărul <code>X</code> 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 <code>K</code> din cutia <code>A</code> în cutia <code>B</code>.

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

= Cerința =
Scrieți un program care citește numerele <code>N</code> și <code>K</code>, apoi determină:

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

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

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține:

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

= Restricții și precizări =

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

== Exemplul 1 ==
input.txt:

1 9 3

output.txt:

4

Explicație:

Se rezolvă cerința <code>1</code>.

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

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

== Exemplul 2 ==
input.txt:

1 3 3

output.txt:

-1

Explicație:

Se rezolvă cerința <code>1</code>.

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

== Exemplul 3 ==
input.txt:

9999999 8 3

Ouput:

ValueError: Invalid value for C

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
# 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()

</syntaxhighlight>