Soluții trimise

Fiind încântat de proba de biatlon de la jocurile olimpice de iarnă, Rareș s-a gândit să inventeze propriul joc. El a așezat în linie un număr de ținte, apoi și-a propus să le doboare folosind mingea. Mingea fiind mai mare, la o lovitură se doboară două ținte aflate una lângă alta. Dacă o țintă este izolată (fără alta vecină) ea poate fi doborâtă la o lovitură cu mingea.

Fiind inventiv, el și-a stabilit câteva reguli speciale de joc:

• Dacă o țintă este vecină cu o alta, aceasta nu poate fi doborâtă singură la lovitura următoare;
• El dorește să execute un număr maxim de lovituri până reușește să doboare toate țintele, respectând regulile jocului;
• Rareș este un foarte bun executant de lovituri cu mingea, așa că el reușește să lovească mereu ținta sau țintele propuse.

Problema are două cerințe, în funcție de valoarea lui C ∈ {1, 2}.

1. C=1. Să se determine numărul maxim de lovituri pe care le poate executa pentru șirul de valori din fișierul de intrare.
2. C=2. Rareș poate să modifice configurația țintelor în felul următor: formează N − 1 grupuri prin alipirea țintelor din ultimul grup la unul dintre celelalte grupuri. Dorește să formeze un astfel de set cu N − 1 grupuri asupra căruia să poată executa un număr de lovituri strict mai mare decât cel maxim posibil pe setul inițial de N grupuri. Programul trebuie să determine grupurile la care poate fi alipit ultimul astfel încât să se îndeplinească dorința lui.