| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Nimetame arvujada $A_1, A_2, \dots, A_N$ järjestatuks, kui iga 1ドル \le i < N$ korral kehtib $A_i \le A_{i+1}$.
Vaatleme järgmist meetodit arvujada järjestamiseks: kõigepealt tükeldatakse jada $M$ lõiguks (jada esimesed $k_1$ elementi moodustavad ühe lõigu, järgmised $k_2$ elementi teise j.n.e kuni viimased $k_M$ elementi moodustavad viimase lõigu) ja edasi tohib omavahel vahetada terveid lõike, aga mitte muuta elementide järjekorda ühegi lõigu sees.
On selge, et mõnede lõikudeks jaotuste korral on jada järjestamine lõikude vahetamise teel võimalik (kindlasti saab iga $N$-elemendilise jada järjestada selle $N$ lõiguks tükeldamise järel) ja mõnede korral ei ole (näiteks üheks lõiguks "tükeldamisel" ei saa järjestada ühtki jada, mis pole juba algselt järjestatud).
Kirjutada programm, mis leiab antud jada jaoks vähima arvu $M,ドル mille korral leidub selline jada tükeldus $M$ lõiguks, et terve jada saab lõikude vahetamise teel järjestada.
Tekstifaili esimesel real on jada elementide arv $N$ (1ドル \le N \le 500,000円$) ja teisel real $N$ tühikutega eraldatud täisarvu: jada elemendid $A_i$ (1ドル \le A_i \le N$).
Tekstifaili ainsale reale väljastada üks täisarv: minimaalne lõikude arv, milleks peab jada tükeldama, et selle saaks lõikude vahetamise teel järjestada.
6 5 6 4 3 1 2
4
Jada võib tükeldada lõikudeks (5 6), (4), (3) ja (1 2). Seejärel võib lõigu (1 2) panna esimeseks, lõigu (3) teiseks, lõigu (4) kolmandaks ja lõigu (5 6) viimaseks ning tulemus on järjestatud.
3 1 2 1
2
Sobib tükeldus lõikudeks (1 2) ja (1).