25159번 - Šetnja 점수다국어

U ulici jorgovana nalazi se $N$ kuća poredanih slijeva nadesno označenih redom prirodnim brojevima od $1$ do $N$. Mirko se trenutno nalazi kod kuće s oznakom $X$ i želi doći do kuće s oznakom $Y$. Smije se kretati lijevo i desno, odnosno kad se nalazi kod neke kuće može otići do jedne od najviše dviju susjednih kuća.

Budući da voli duge noćne šetnje po mjesečini i pod zvjezdanim nebom, te zavirivanje u tuđa dvorišta odlučio je šetati od kuće $X$ do kuće $Y$ na način da kuću s oznakom i posjeti točno $A_i$ puta.

Mirku baš i ne ide snalaženje u prostoru pa te moli da osmisliš takvu šetnju umjesto njega. I šetnje koje ne posjete svaku kuću traženi broj puta donijet će neki broj bodova pa pozorno promotri sekciju BODOVANJE.

U prvom retku redom nalaze se prirodni brojevi $N$ ($1 ≤ N ≤ 100\,000$), $X$ ($1 ≤ X ≤ N$) i $Y$ ($1 ≤ Y ≤ N$), brojevi iz teksta zadatka.

U drugom retku nalazi se niz od $N$ prirodnih brojeva $A_i$ ($1 ≤ A_i ≤ 100\,000$), niz iz teksta zadatka. Zbroj $A_1 + A_2+ \dots + A_n$ bit će manji ili jednak $100\,000$.

U prvom retku ispiši broj $K$ ($1 ≤ K≤ 200\,000$), duljinu tvoje predložene šetnje.

U drugom retku ispiši niz od $K$ prirodnih brojeva $B_k$ ($1 ≤ B_k ≤ N$, $k=1\dots K$) koji opisuju Mirkovu šetnju, tj. redom one kuće koje će Mirko posjetiti.

Da bi ispis bio valjan mora vrijediti:

• $B_1 = X$ jer mora krenuti od $X$-te kuće;
• $B_K = Y$ jer mora završiti kod $Y$-te kuće;
• $|B_i - B_{i-1}| = 1$ za $i=2,\dots , K$ jer se u svakom koraku smije i mora pomaknuti do susjedne kuće.

Ulazni podaci bit će takvi da rješenje postoji.

Broj bodova računa se na sljedeći način:

Svaki primjer zasebno nosi 4 boda.

Ako je $K > 200\,000$ ili nije zadovoljen neki od ostalih kriterija iz sekcije IZLAZNI PODACI broj bodova na tom primjeru bit će 0.

Neka $V_i$ označava broj prolazaka kraj i-te kuće u ispisanoj šetnji, tj. $V_i$ je broj pojavljivanja broja $i$ u ispisanom nizu $B$. Neka je $P$ zbroj apsolutnih razlika pripadnih članova nizova $A$ i $V$, tj. $P = |A_1 - V_1| + |A_2 - V_2| + \dots + |A_n - V_n|$.

Ako je $P = 0$, tj. ako je u ispisanoj šetnji svaka kuća posjećena traženi broj puta dobit ćete sva 4 boda.

Inače broj osvojenih bodova iznosi $3 \times \sqrt{\frac{1}{P}}$ zaokružen na dva decimalna mjesta.

Opis trećeg primjera: Mirko će redom posjetiti kuće 3, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4. Na taj način krenut će od treće i završit u četvrtoj kao što je i želio. Prvu kuću posjetit će jednom, drugu dva puta, treću tri puta, četvrtu četiri puta, petu tri puta i šestu jednom.