Fişierul intrare/ieşire:stup.in, stup.outSursăGrigore Moisil 2011, Clasele 11-12
AutorPerticas CatalinAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stup

Într-un stup oarecare locuiesc N albine. Stupul este compartimentat în parcele în aşa fel încât fiecare parcelă se învecinează cu alte 6 parcele identice. Cele N albine au primit fiecare câte o parcelă pentru a-şi putea cultiva cele necesare. Se ştie că ele nu au primit aceste teritorii la întâmplare. Albina cu cele mai multe merite, albina 1, a primit parcela din centrul stupului, iar toate celelalte au primit parcele în ordine descrescătoare a meritelor mergând în spirală de la căsuţa primei albine. Astfel, albina 1 are cele mai multe merite, în timp ce albina N are cele mai puţine. De-a lungul timpului, aceste albine au format triburi, iar în momentul de faţă niciun trib nu se înţelege prea bine cu vreun alt trib. Felul în care s-au format triburile nu este nici el întâmplător, toate albinele care aparţin unui trib au numere de ordine consecutive, aşa că dacă a şi b fac parte din acelaşi trib, atunci a+1, a+2, ..., b-1 fac şi ele parte din trib. O albină x vrea să-şi vadă o veche prietenă, albina y, dar pentru a ajunge la ea, trebuie să treacă prin parcelele altora, deci e posibil să trebuiască să treacă şi prin triburi străine. Albina x este foarte generoasă şi vă recompensează cu 100 de puncte dacă îi determinaţi drumul până la prietena y, drum care trece printr-un număr minim de triburi străine.

Cerinţă

Scrieţi un program care determină numărul minim de triburi prin care trebuie sa treacă albina x pentru a-şi îndeplini scopul.

Date de intrare

Pe prima linie a fişierului de intrare stup.in se află N M x y, patru numere naturale separate prin câte un spaţiu, unde x, y şi N au semnificaţia din enunţ, iar M este numărul de triburi formate. În continuare găsiţi descrierea fiecărui trib în următorul format b1, b2, ... bM. Primul trib este format din albinele 1, 2, ..., b1, al doilea din b1+1, b1+2, ..., b2 şi aşa mai departe. bM va fi întotdeauna egal cu N, iar fiecare trib are cel puţin o albină.

Date de ieşire

În fişierul de ieşire stup.out se află un singur număr natural, reprezentând numărul minim de triburi cerut.

Restricţii

  • 1 ≤ N ≤ 100 000
  • Pentru 20% din teste N ≤ 23.
  • Pentru următoarele 30% din teste M = N, adică fiecare albină va forma un singur trib.

Exemplu

stup.instup.out
10 5 4 9
3 5 6 9 10
3

Explicaţie

Triburile ce se formează sunt (1, 2, 3), (4, 5), (6), (7, 8, 9), (10). Un drum ce trece prin 3 triburi este [4, 1, 9].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content