Fişierul intrare/ieşire:subsir1000.in, subsir1000.outSursăAlgoritmiada 2011, Runda 3
AutorAdrian AirineiAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsir1000

Pentru a cumpăra bilete la Finala Cupei, N oameni s-au aşezat la coadă. Fiecare om are locul său preferat pe care doreşte să stea, reprezentat printr-un număr strict pozitiv mai mare decât 1 şi mai mic sau egal decât N. Totuşi, toată lumea ştie că nu vor fi bilete suficiente pentru toţi, aşa că organizatorii s-au hotărât să ia un subşir de oameni de lungime maximă cărora să le dea biletele rămase. Totuşi, pentru a nu stârni suspiciuni, s-a hotarât ca în acest subşir oricare două persoane consecutive trebuie să nu aibă numerele locurilor preferate prime între ele (în acest mod organizatorii cred că persoanele nu vor ieşi în evidenţă).
Aşadar, în schimbul unei părţi din profit în valoare de 100 de puncte, organizatorii vă cer ajutorul: trebuie să determinaţi cel mai lung subşir astfel încât oricare două elemente consecutivenu fie prime între ele.

Date de intrare

Fişierul de intrare subsir1000.in se află pe prima linie N, numărul de persoane. Pe următoarea linie se afla N numere aflate în intervalul [2, N] reprezentând locurile preferate ale persoanelor.

Date de ieşire

În fişierul de ieşire subsir1000.out trebuie să afişaţi lungimea celui mai lung subşir care respectă restricţiile date.

Restricţii

  • 2 ≤ N ≤ 100 000
  • Considerând că şirul dat este A = (a1,a2,...aN), se numeşte subşir al lui A un şir B = (ai1,ai2,...aiK) cu proprietatea că 1 ≤ i1 < i2 < ... < iK ≤ N.
  • Pe organizatori nu îi interesează dacă din subşir fac parte două sau mai multe persoane cu acelaşi loc preferat. Ei le dau biletele şi îi lasă pe ei să îşi rezolve problema.

Exemplu

subsir1000.insubsir1000.out
7
5 3 4 6 2 5 6
4

Explicaţie

O soluţie posibila este: 3 6 2 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content