Fişierul intrare/ieşire:light2.in, light2.outSursăRMMS 2011 - Ziua 1
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test1.5 secLimită de memorie24576 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Light2

În laboratorul de fizică sunt N becuri. Iniţial toate becurile sunt stinse. Fiecare din cei K elevi din laborator îşi alege un număr natural di (2 ≤ di ≤ N) şi schimbă starea tuturor becurilor din di în di. Prin schimbarea stării unui bec se înţelege că un bec stins va deveni aprins iar un bec aprins va deveni stins. După ce un elev schimbă starea becurilor sale, acesta părăseşte clasa.

Scrieţi un program care calculează câte becuri vor rămâne aprinse, după ce toţi elevii părăsesc clasa.

Date de intrare

Fişierul de intrare light2.in conţine pe prima linie un întreg pozitiv N, reprezentând numărul de becuri din laborator. A doua linie conţine numărul K, numărul de elevi. A treia linie din fişier conţine K numere naturale d1, d2, ... dK, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire light2.out va conţine un singur număr natural, reprezentând numărul de becuri care rămân aprinse, după ce toţi elevii părăsesc clasa.

Restricţii

  • 3 ≤ N ≤ 1012
  • 1 ≤ K ≤ 22
  • 1 ≤ di ≤ min(N, 106)
  • Numerele di nu sunt în mod necesar distincte două câte două

Exemplu

light2.inlight2.out
8
2
2 3
4

Explicaţie

Iniţial, toate becurile sunt stinse. După ce primul elev schimbă starea becurilor sale, al 2-lea, al 4-lea, al 6-lea şi al 8-lea bec vor fi aprinse. După ce al doilea elev schimbă starea becurilor sale, vor rămâne aprinse becurile cu numerele de ordine 2, 3, 4 şi 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content