1686 - Leduri

From Bitnami MediaWiki
Revision as of 04:14, 1 April 2024 by Cristina94 (talk | contribs) (Pagină nouă: ==Enunţ== Am un cablu cu N leduri (numerotate de la 1 la N) aşezate echidistant. Inițial, unele leduri sunt aprinse, iar altele sunt stinse. Ledurile sunt legate între ele astfel încât atingerea fiecărui led produce modificarea atât a stării lui, cât şi a ledurilor vecine lui. Deci, dacă se atinge ledul i (2≤i≤N-1) atunci se modifică stările ledurilor i-1, i și i+1. Dacă se atinge ledul 1, atunci se modifică stările ledurilor 1 și 2, iar dacă se atinge...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Enunţ[edit | edit source]

Am un cablu cu N leduri (numerotate de la 1 la N) aşezate echidistant. Inițial, unele leduri sunt aprinse, iar altele sunt stinse. Ledurile sunt legate între ele astfel încât atingerea fiecărui led produce modificarea atât a stării lui, cât şi a ledurilor vecine lui. Deci, dacă se atinge ledul i (2≤i≤N-1) atunci se modifică stările ledurilor i-1, i și i+1. Dacă se atinge ledul 1, atunci se modifică stările ledurilor 1 și 2, iar dacă se atinge ledul N, atunci se modifică stările ledurilor N-1 și N. Vreau să modific starea ledurilor astfel încât să semene cu cablul cu N leduri pe care îl are Ionuț, prietenul meu (două cabluri seamănă dacă pentru orice i=1..N stările ledurilor de pe poziția i sunt identice).

Cerința[edit | edit source]

Cunoscând cum arată cablul lui Ionuț, ajutați-mă să determin numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca și cablul lui Ionuț.

Date de intrare[edit | edit source]

Fișierul de intrare leduri.in conține pe prima linie numărul natural N. Pe a doua linie sunt N cifre binare separate prin câte un spațiu reprezentând stările ledurilor de pe cablul meu. Cifra de pe poziția i este 0 dacă ledul i este stins, respectiv este 1 dacă ledul i este aprins (i=1..N). Pe a treia linie sunt N cifre binare separate prin câte un spațiu, reprezentând stările ledurilor de pe cablul lui Ionuț.

Date de ieșire[edit | edit source]

Fișierul de ieșire leduri.out va conține pe prima linie un singur număr natural reprezentând numărul minim de atingeri ale unor leduri astfel încât cablul meu să arate ca și cablul lui Ionuț.

Restricții și precizări[edit | edit source]

  • 1 ≤ N ≤ 100000
  • Se garantează că pentru toate testele există soluție.
  • Pentru teste valorând 30 de puncte, N va fi cel mult 20

Exemplu1[edit | edit source]

leduri.in
4
1 0 1 0
0 1 1 1
leduri.out
2

Exemplu2[edit | edit source]

leduri.in
5
1 0 1 1
1 0 1 1
leduri.out
Date de intrare invalide.

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line>

  1. 1686 Leduri

def verificare_date_intrare(N, starea_mea, starea_ionut):

 if not (1 <= N <= 100000):
   return False
 if len(starea_mea) != N or len(starea_ionut) != N:
   return False
 for bit in starea_mea:
   if bit not in {0, 1}:
     return False
 for bit in starea_ionut:
   if bit not in {0, 1}:
     return False
 return True

def numar_minim_atingeri(N, starea_mea, starea_ionut):

 atingeri = 0
 for i in range(N):
   if starea_mea[i] != starea_ionut[i]:
     atingeri += 1
     if i > 0:
       starea_mea[i - 1] = 1 - starea_mea[i - 1]
     if i < N - 1:
       starea_mea[i + 1] = 1 - starea_mea[i + 1]
 return atingeri

def main():

 with open("leduri.in", "r") as fin:
   N = int(fin.readline())
   starea_mea = list(map(int, fin.readline().split()))
   starea_ionut = list(map(int, fin.readline().split()))
 if not verificare_date_intrare(N, starea_mea, starea_ionut):
   with open("leduri.out", "w") as fout:
     fout.write("Date de intrare invalide.\n")
   return
 numar_atingeri = numar_minim_atingeri(N, starea_mea, starea_ionut)
 with open("leduri.out", "w") as fout:
   fout.write(str(numar_atingeri) + "\n")

if __name__ == "__main__":

 main()

</syntaxhighlight>