Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | papuci.in, papuci.out | Sursă | Algoritmiada 2009, Runda 2 |
| Autor | Adrian Airinei | Adăugată de |  Stefan Istrate •stef2n |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Papuci
De ceva timp, Ionel isi doreste sa viziteze muzeul X, iar astazi tocmai s-a ivit aceasta ocazie. Ca orice vizitator, va trebui, insa, sa respecte regulamentul muzeului, astfel ca ghidul i-l explica la intrare. Baiatul va vizita cele N camere ale muzeului in ordine, de la camera 1 la camera N. In prima camera, va incalta o pereche de papuci (proprietarii muzeului vor sa protejeze astfel covoarele de o inestimabila valoare), iar in fiecare din camerele urmatoare va da jos perechea de papuci curenta si va lua alta pereche pe care o va purta doar in camera respectiva. Papucii sunt de 26 de tipuri (etichetate cu literele de la 'a' la 'z'), iar fiecare camera a muzeului dispune de o pereche dintr-unul din aceste tipuri. Timpul in care Ionel da jos papucii de tipul i si incalta papucii de tipul j este dat de elementul A[i][j] al unei matrice patratice A furnizate la intrarea in muzeu.
Baiatul isi doreste o vizita cat mai lunga in muzeu, de aceea ghidul ii prezinta Regula Vizitatorilor Speciali. Ionel primeste o lista de K perechi (a, b) de camere. Pentru fiecare din acestea, el trebuie sa decida, inainte sa-si inceapa vizita in muzeu, daca solicita inversarea papucilor din camera a cu cei din camera b sau nu. Apoi se va bucura de vizita si va profita de timpul cat schimba papucii intre doua camere consecutive, punand cat mai multe intrebari ghidului.
Date de intrare
Pe prima linie a fisierului de intrare papuci.in se vor afla numerele N si K cu semnificatiile de mai sus. Pe linia a doua se va afla un sir de N litere mici ale alfabetului englez, astfel incat al i-lea caracter sa reprezinte tipul initial de papuci din camera i. Pe urmatoarele 26 de linii se vor afla cate 26 de numere naturale reprezentand matricea A (A[i][j] = timpul de care are nevoie Ionel pentru a descalta papucii de tipul i si a incalta papucii de tipul j). Pe fiecare din urmatoarele K linii se vor afla cate 2 numere a si b, 1 ≤ a ≤ b ≤ N, reprezentand o inversare de papuci pe care Ionel o poate face intre camerele a si b inainte de a-si incepe vizita.
Date de iesire
Pe prima linie a fisierului de iesire papuci.out se va scrie timpul maxim obtinut de Ionel doar din descaltarea si incaltarea perechilor de papuci la trecerea dintr-o camera intr-alta pe parcursul intregii vizite. Pe a doua linie se va scrie un numar T reprezentand numarul de inversari din cele K pe care le-a utilizat pentru a obtine acest timp maxim. Pe linia a 3-a se vor scrie numerele de ordine ale celor T inversari folosite (inversarile sunt numerotate de la 1 la K in ordinea in care apar in fisierul de intrare).
Restrictii
- 1 ≤ N, K ≤ 100.000
- Elementele matricii A sunt numere naturale mai mici sau egale cu 1000.
- Matricea A nu va fi neaparat simetrica fata de diagonala principala.
- Orice camera i apare cel mult o data in cele K inversari.
- Nu exista doua inversari (a,b) si (c,d) cu c > a, c < b si b < d.
- Cele T inversari trecute in fisierul de iesire trebuie sa fie distincte.
- In cazul in care exista mai multe solutii care determina timpul maxim corect, oricare din ele este acceptata.
Exemplu
| papuci.in | papuci.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
