== include(page="template/taskheader" task_id="atlas") ==
Poveste şi cerinţă...
!>problema/atlas?Atlas.png!
_„Primăvara prin topirea zăpezii iau naştere râuri şi lacuri numite *Wadi*, lacuri ce seacă vara.”_ (Wikipedia). Asta se întâmplă în Munţii Atlas din nordul Africii. Noi avem de simulat aceasta în următorul mod:
Avem un şir de numere, care reprezintă înălţimile fiecărui loc în care poate ajunge apa. Fiecare element din şir reprezintă înălţimea în metri a unei zone cu laţimea de un metru. Zonele sunt lipite. Apa cade de pe poziţia $0$, de la o înălţime suficient de mare şi va curge spre dreapta. Numim “unitate de apă” cantitatea de apă ce ocupă o zonă a unui pătrat $1X1$. De exemplu, dacă se va topi o cantitate de $4$ unităţi de apă, aceasta va cădea de pe zona $0$ spre dreapta şi va ajunge să ocupe zonele haşurate. Se observă că dacă ajunge pe o anumită zonă apa curge spre dreapta până se loveşte de un perete vertical. Noi lucrăm cu proiecţia într-un plan a zonei imaginare, aşa că vom considera toate elementele ca având grosime neglijabilă.
h2. Cerinta
Se dă configuraţia zonei şi se cere, pentru mai multe cantităţi posibile de apă topită (exprimate în “unităţi de apă”), să se determine cea mai din dreapta poziţie pe care ajunge apa şi la ce înălţime ajunge pe acea poziţie.
h2. Date de intrare
Fişierul de intrare $atlas.in$ ...
În fişierul de intrare *atlas.in* sunt mai multe teste. Pe prima linie a fişierului se găseşte $T$, numărul de teste. În continuare, sunt $4∙T$ linii. Fiecare test este descris de $4$ linii astfel: Pe prima linie a testului se găseşte $n$, numărul de zone pe care le poate traversa apa după ce cade (acestea sunt numerotate de la $1$ la $n$). Se ştie că apa cade de pe zona $0$ de înălţime infinită, iar la dreapta este zona $n+1$, de înălţime de asemenea infinită. Pe linia a doua a testului sunt $n$ numere naturale, separate prin câte un spaţiu, reprezentând, în ordine de la $1$ la $n$ înălţimile celor $n$ zone. Pe linia a treia a testului se găseşte $q$, numărul de întrebări. Pe linia a $4$-a a testului sunt $q$ numere, separate prin câte un spaţiu, ce reprezintă câte un număr de unităţi de apă care se topeşte.
h2. Date de ieşire
În fişierul de ieşire $atlas.out$ ...
Fişierul *atlas.out* conţine câte o linie pentru fiecare întrebare a fiecărui test, în ordinea apariţiei testelor şi apoi în ordinea apariţiilor întrebărilor în fiecare test. Pe fiecare dintre acestea se află câte $2$ numere separate printr-un spaţiu ce reprezintă, în ordine, răspunsul la fiecare întrebare. Primul număr este întreg şi reprezintă poziţia cea mai mare la care ajunge apa. Al doilea este un număr raţional şi reprezintă înălţimea la care ajunge apa la poziţia dată de primul număr. Acesta va fi afişat sub forma unei fracţii ireductibile “numarator/numitor”.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n, q ≤ 100000$
* $0 ≤ Înălţimile pilonilor ≤ 100000$
* $1 ≤ Valorile din întrebări ≤ 100000 × 100000$
* $1 ≤ T ≤ 3$
* În scrierea numărului raţional nu se scrie spaţiu nici înainte şi nici după caracterul /
h2. Exemplu
table(example). |_. atlas.in |_. atlas.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
5
0 3 1 4 5
3
4 9 6
3
2 3 1
2
1 2
| 3 2/1
4 17/4
3 10/3
1 3/1
3 2/1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="atlas") ==
