Fișierul intrare/ieșire ordine.in, ordine.out Sursă OJI 2015 clasa a 6-a
Autor Marinel Șerban Adăugată de avatar Marcela Marcela Marcela
Timp de execuție pe test 1 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Ordine (clasa a 6-a)

Gigel a primit de ziua lui un joc cu bile. Jocul conține n bile numerotate cu numerele naturale distincte de la 1 la n. Jucându-se, Gigel a amestecat bilele astfel încât acum ele nu mai sunt în ordine. Ca să le pună înapoi în cutia jocului, Gigel ia de pe masă bilele una câte una, și le pune în cutie formând un șir. Însă Gigel se joacă și acum, astfel încât el nu pune bilele la rând, una după alta, ci are o regulă pe care o respectă cu strictețe. Astfel, Gigel încearcă să plaseze fiecare bilă pe care a luat-o de pe masă exact la mijlocul șirului de bile deja format. Dacă acest lucru nu este posibil (șirul are lungime impară), atunci el plasează bila la sfârșitul șirului de bile deja format. După ce toate bilele au fost puse în cutie, Gigel își dă seama că nu a notat ordinea în care a luat bilele de pe masă și, în mod firesc, își pune problema dacă nu cumva poate deduce acest lucru din șirul de bile pe care tocmai l-a format.

Cerință

Cunoscându-se numărul de bile și configurația finală a bilelor în șir să se determine:
1. numărul ultimei bile luate de pe masă;
2. ordinea în care bilele au fost luate de pe masă.

Date de intrare

Fișierul de intrare ordine.in conține pe prima linie numărul n de bile. Pe linia a doua a fișierului de intrare se găsesc n numere naturale, cu valori între 1 și n, separate prin câte un spațiu, care reprezintă șirul de bile obținut de Gigel în cutie. Linia a treia conține una dintre valorile 1 sau 2 reprezentând cerința 1, dacă se cere determinarea ultimei bile luate de Gigel de pe masă, respectiv cerința 2, dacă se cere determinarea ordinii în care Gigel a luat bilele de pe masă.

Date de ieșire

În fișierul de ieșire ordine.out va conține pe prima linie o valoarea naturală reprezentând numărul ultimei bile luate de Gigel, dacă cerința a fost 1, respectiv n numere naturale, cu valori cuprinse între 1 și n, separate prin câte un spațiu, care reprezintă ordinea în care Gigel a luat bilele de pe masă, dacă cerința a fost 2.

Restricții

  • 1 ≤ n ≤ 250 000;
  • Pentru cerința 1 se acordă 30% din punctaj, iar pentru cerința 2 se acordă 70% din punctaj.

Exemple

ordine.in ordine.out
7
1 7 2 5 3 4 6
1
5
7
1 7 2 5 3 4 6
2
1 3 7 4 2 6 5

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii