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

<syntaxhighlight lang="python3" line="1">

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")

1. Open input and output files

fin = open("input.txt", "r") fout = open("output.txt", "w")

1. Read input values

C, N, K = map(int, fin.readline().split())

1. Validate input constraints

validate_input_constraints(C, N, K)

1. Function to write the result to the output file

def write_result(s):

   fout.write(" ".join(map(str, s)) + '\n')

1. Function for case 1

def c1():

   if N % 2 == 1:
       fout.write(str((N - 1) // 2) + '\n')
   else:
       fout.write("-1\n")

1. 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)

1. 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)

1. Main program

if C == 1:

   c1()

elif C == 2:

   c2()

elif C == 3:

   c3()

1. Close input and output files

fin.close() fout.close()

</syntaxhighlight>