Fişierul intrare/ieşire:	atlas.in, atlas.out	Sursă	Lot Râmnicu Vâlcea 2015 - Baraj 1 Seniori
Autor	Marius Nicoli	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Atlas

„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ă.

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.

Date de intrare

Î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.

Date de ieşire

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”.

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 /

Exemplu

Cum se trimit solutii?