Petras.du.ioana: Am creat de la zero.

2023-05-17T21:33:05Z

Am creat de la zero.

New page

Sursa: [https://www.pbinfo.ro/probleme/3694/tomi]
----
== Cerinţa ==
Tomi este primarul ales în orașul Bittown. În oras sunt N locuitori și fiecare are un gard format din exact 60 de scânduri, fiecare dintre ele fiind vopsită în alb sau negru. Fiecare gard este codificat de Tomi printr-un număr natural a cărui reprezentare binară reproduce configurația gardului, de la stânga spre dreapta, scândurile negre fiind asimilate cu bitul 1 iar cele albe cu bitul 0. Astfel, ca exemplu, gardul care are doar ultimele două scânduri vopsite în negru va fi codificat de Tomi cu numărul 3. Tomi decide să-și construiască un gard care să fie reprezentativ pentru Bittown, adică să respecte toate regulile următoare:
1. Gardul primarului Tomi trebuie să aibă exact 60 de scânduri;
2. Trebuie să existe cel puțin K locuitori în Bittown care constată că pentru toate scândurile negre din gardul propriu, scândurile situate pe aceeași poziție în gardul primarului Tomi sunt vopsite tot în negru;
3. Numărul reprezentând codul gardului primarului Tomi trebuie să fie minim posibil.

== Date de intrare ==
Fișierul de intrare tomi.in conține pe prima linie doua numere naturale N și K. Pe cea de-a doua linie se află N numere, reprezentând codurile gardurilor locuitorilor din Bittown.

== Date de ieșire ==
Fișierul de ieșire tomi.out va conține un singur număr reprezentand codul gardului construit de primarul Tomi.

== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000
* Fiecare cod este strict mai mic decât 260.
* Pentru 19 puncte, toți copiii vor avea doar codurile 1, 2 sau 3.
* Pentru alte 38 puncte, codurile copiilor vor mai mici decât 60.

== Exemplu ==
; tomi.in
: 6 3
: 1 1 5 8 10 8
; tomi.out
: 5
<br>

=== Explicație ===
Răspunsul este 5 care are configurația în binar 101. Acesta este reprezentativ pentru codurile primelor trei garduri (1 1 5), pentru că le include configurațiile binare, respectând astfel regula 2.

== Rezolvare ==

<syntaxhighlight lang="python" line>

def verificare_reguli(cod_primar, coduri_locuitori, K):
count = 0
for cod_locuitor in coduri_locuitori:
if cod_locuitor & cod_primar == cod_locuitor:
count += 1
return count >= K

if __name__ == "__main__":
with open("tomi.in", "r") as fisier_intrare:
N, K = map(int, fisier_intrare.readline().split())
coduri_locuitori = list(map(int, fisier_intrare.readline().split()))

# Verificarea datelor de intrare
if N < 1 or N > 100000:
print("Eroare: N trebuie să fie între 1 și 100000.")
exit(1)
if K < 1 or K > N:
print("Eroare: K trebuie să fie între 1 și N.")
exit(1)
if len(coduri_locuitori) != N:
print("Eroare: Numărul de coduri de locuitori nu corespunde valorii N.")
exit(1)
for cod_locuitor in coduri_locuitori:
if cod_locuitor < 0 or cod_locuitor >= 2**60:
print("Eroare: Codul de gard al unui locuitor este invalid.")
exit(1)

cod_minim = float("inf")
for i in range(1, 2**60):
if verificare_reguli(i, coduri_locuitori, K):
cod_minim = i
break

with open("tomi.out", "w") as fisier_iesire:
fisier_iesire.write(str(cod_minim))

</syntaxhighlight>

3694 – Tomi - Revision history

Petras.du.ioana: Am creat de la zero.