Pentru că nu sunt suficienți bani pentru ultimele tehnologii GPS, trebuie să te bazezi pe un sistem mai vechi de urmărire, care funcționează astfel:
!>problema/cursaf13?problema-cursaf13-schema03.png!
* Un circuit din campionat este reprezentat pe o hartă. Harta este desenată ca un dreptunghi, împărțit în linii și coloane. Un pătrățel este considerat o unitate de distanță.
* Un circuit din campionat este reprezentat pe o hartă. Harta este desenată ca un dreptunghi, împărțit în linii și coloane. Un pătrățel este considerat o unitate de distanță.
* Pentru a putea modifica repede reprezentarea circuitului de la o cursă la alta, aceasta este codificată astfel:
** Se dau două numere, **ls** și **cs**, ce reprezintă coordonatele punctului de start al circuitului.
** Se dau două numere, **ls** și **cs**, ce reprezintă coordonatele punctului de start ale circuitului.
** Apoi, se dă secvența de codificare a circuitului ce cuprinde mai multe direcții, **d**, urmate de numărul de pătrățele **k** cu care mașina se deplasează în acea direcție.
** Direcția **d** este redată prin literele A, B, C, D, E, F, G și H, conform desenului de mai jos.
** Direcția **d** este redată prin literele A, B, C, D, E, F, G și H, conform desenului alăturat.
** Numărul ce urmează după direcție reprezintă numărul de pătrățele de pe hartă cu care mașina se deplasează în acea direcție.
* Mașinile urmăresc acest circuit și nu se abat de la el. Merg în aceleași direcții și se deplasează același număr de pătrățele, conform codificării date pentru circuit.
* Din momentul startului cursei, fiecare mașină transmite prin radio distanța, **x[~i~]**, pe care a parcurs-o într-o anumită perioadă de timp, **i**.
** Distanța **x [~i~]** reprezintă numărul de pătrățele parcurse de mașină pe hartă, în perioada **i**.
** Pe parcursul cursei, se verifică **t** perioade de timp pentru a vedea unde este fiecare mașină.
* Din momentul startului cursei, fiecare mașină transmite prin radio distanța, **x [~t~]**, pe care a parcurs-o într-o anumită perioadă de timp, **t**.
** Distanța **x [~t~]** reprezintă numărul de pătrățele parcurse de mașină pe hartă, în perioada **t**.
** Pe parcursul cursei, se verifică mai multe momente **t** pentru a vedea unde este fiecare mașină.
** Pentru a nu îngreuna sistemul, perioada de timp **t** este constantă pe tot parcursul cursei.
h2. Cerință
Înainte de prima cursă, te apuci să faci câteva teste asupra sistemului. Așa că ai convins un singur pilot să facă ture cu mașina pe circuit și încerci să determini poziția acestuia, la sfârșitul fiecărei perioade de timp **i**.
Înainte de prima cursă, te apuci să faci câteva teste asupra sistemului. Așa că ai convins un singur pilot să facă ture cu mașina pe circuit și încerci să determini poziția acestuia, la sfârșitul fiecărei perioade de timp **t**.
h2. Date de intrare
Fișierul de intrare $cursaf13.in$ conține:
* pe prima linie coordonatele punctului de start ale circuitului, **ls** și **cs**.
Fișierul de intrare $cursaf13.in$ conține pe prima linie coordonatele punctului de start ale circuitului, **ls** și **cs**.
* pe a doua linie secvența de codificare a circuitului, alcătuită din litere și numere. Secvența este împărțită în grupuri ce conțin o literă, reprezentând direcția **d** și un număr **k** reprezentând numărul de pătrățele cu care avansează mașina.
Pe următoarea linie se găsește secvența codificată a circuitului, alcătuită din litere și numere. Secvența este împărțită în grupuri ce conțin o literă, reprezentând direcția **d** și un număr reprezentând lungimea segmentului, **k**.
* pe a treia linie un singur număr **t**, reprezentând numărul de perioade de timp pentru care verificăm mașina de test.
Pe următoarea linie se dă numărul **t**, cu semnificația de mai sus pentru mașina de test.
* pe a patra linie **t** numere, despărțite printr-un spațiu, reprezentând distanțele **x[~i~]** parcurse de mașină în fiecare din cele **t** perioade de timp.
Pe următoarea linie se dau **t** distanțe **x [~t~]** despărțite printr-un spațiu, cu semnificația de mai sus.
h2. Date de ieșire
În fișierul de ieșire $cursaf13.out$ veți afișa **t** perechi de două numere, despărțite printr-un spațiu, câte o pereche pe linie. în total **t** linii. Perechea de pe linia **i** reprezintă coordonatele mașinii (linie și coloană) la finalul perioadei de timp **i**.
În fișierul de ieșire $cursaf13.out$ se vor afișa pe fiecare linie câte o pereche de câte două numere, despărțite printr-un spațiu. Acestea reprezintă coordonatele mașinii (linie și coloană) la fiecare perioadă de timp **t**.
h2. Restricții
* **d** este o literă mare între A și H
* 1 ≤ **k** ≤ 200
* 1 ≤ **t** ≤ 20 000
* 1 ≤ **x[~i~]** ≤ 1 000 000
* Circuitul are cel puțin 3 schimbări de direcție, dar nu poate avea mai mult de 20 000 de schimbări de direcție.
* Se garantează că circuitul se închide. Mașina care parcurge circuitul conform codificării lui se va afla, după ce parcurge o tură întreagă de circuit, în punctul de start, la coordonatele, **ls** și **cs**.
* Circuitul se poate autointersecta. Codificarea lui este o reprezentare cu vedere de sus. În realitate există tuneluri sau poduri.
* 0 ≤ **ls**, **cs**
* **d** poate fi oricare dintre majusculele cuprinse între A - H
* 1 ≤ **k** ≤ 2000
* 1 ≤ **t** ≤ 2000
* 1 ≤ **x [~t~]** ≤ 1000
* Circuitul nu poate avea mai mult de 1000 de schimbări de direcție.
* Se garantează că circuitul se închide. Mașina care parcurge circuitul conform codificării lui se afla, la final, în punctul de pornire al circuitului, la coordonatele, **ls** și **cs**.
* Circuitul se poate autointersecta. Este o reprezentare cu vedere de sus. În realitate există tuneluri sau poduri.
* Se garantează că circuitul nu are schimbări de direcție la 180 de grade (în direcția opusă). Nu vor exista două direcții alăturate A-E, B-F, C-G, D-H sau viceversa.
* Se garantează că toate punctele circuitului au coordonate numere naturale mai mici decât 4 milioane
* Se garantează că toate punctele circuitului au coordonate numere naturale.
h2. Exemplu
table(example).
|_. cursaf13.in |_. cursaf13.out |_. Explicații |
| 0 0
C7D3E5G10A8
5
13 7 28 11 16
| 6 10
8 5
8 10
7 0
2 9
| Circuitul începe la coordonatele (0,0). Apoi, conform codificării, urmează:
C7 - 7 pătrățele spre dreapta;
D3 - 3 pătrățele în diagonală jos-dreapta
E5 - 5 pătrățele în jos;
C10E10G10A10
4
16 12 20 11
| 6 10
10 2
0 8
9 10
| Circuitul începe reprezentarea din coordonatele (0,0). Apoi se reprezintă circuitul conform codificării:
C10 - 10 pătrățele spre dreapta;
E10 - 10 pătrățele în jos;
G10 - 10 pătrățele în stânga;
A8 - 8 pătrățele în sus.
A10 - 10 pătrățele în sus.
După reprezentarea circuitului ca în figura alăturată, vom deplasa mașina și vom vedea un se află
fiecare la fiecare perioadă **i**:
* pentru **i** = 1, va parcurge 13 pătrățele și va ajunge la coordonatele l = 6, c = 10.
* pentru **i** = 2, va parcurge 7 pătrățele și va ajunge la coordonatele l = 8, c = 5.
* pentru **i** = 3, va parcurge 28 pătrățele și va face termina prima tură și va continua traseul.
Va ajunge la coordonatele l = 8, c = 10, în cea de-a doua tură.
* pentru **i** = 4, va parcurge 11 pătrățele și va ajunge la coordonatele l = 7, c = 0.
* pentru **i** = 5, va parcurge 16 pătrățele și va ajunge la coordonatele l = 2, c = 9
|
h3. Explicație grafică pentru exemplu
Reprezentarea circuitului
!>problema/cursaf13?problema-cursaf13-schema03.png!
!problema/cursaf13?problema-cursaf13-schema01.png!
Reprezentarea poziției mașinii la fiecare perioadă de timp **i**
!problema/cursaf13?problema-cursaf13-schema02.png!
fiecare la fiecare perioadă t:
* pentru t = 1, va parcurge 16 pătrățele și va ajunge la coordonatele l = 6, c = 10.
* pentru t = 2, va parcurge 12 pătrățele și va ajunge la coordonatele l = 10, c = 2.
* pentru t = 3, va parcurge 20 pătrățele și va ajunge la coordonatele l = 0, c = 8.
* pentru t = 4, va parcurge 11 pătrățele și va ajunge la coordonatele l = 9, c = 10.
|
== include(page="template/taskfooter" task_id="cursaf13") ==
