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:
* 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ță.
!>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ță.
* 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 ale circuitului.
** Se dau două numere, **ls** și **cs**, ce reprezintă coordonatele punctului de start al 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.
** -Poziția de start nu este parte componentă a primului segment din circuit. Doar ne spune de unde plecăm în direcția **d** cu segmentul. Primul pătrățel al primului segment va fi vecin cu poziția de start.-
** Direcția **d** este redată prin literele A, B, C, D, E, F, G și H, conform desenului alăturat.
** Direcția **d** este redată prin literele A, B, C, D, E, F, G și H, conform desenului de mai jos.
** 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.
** -Direcția se schimbă când se întâlnește o altă 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ă **n** 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 sunt mașinile.
** Pentru a nu îngreuna sistemul, perioada de timp **t** este constantă pe tot parcursul cursei.
** Toate mașinile se raportează la această perioadă **t**.
* 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ă.
h2. Cerință
Înainte de prima cursă, te apuci să faci câteva teste asupra sistemului și încerci să afli unde se află fiecare mașină pe circuit, la sfârșitul ultimei perioade de timp **t**.
Î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**.
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 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 prima linie coordonatele punctului de start ale circuitului, **ls** și **cs**.
Pe următoarea linie dau două numere despărțite printr-un spațiu, **t** și **n**, cu semnificația de mai sus.
* 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ătoarele **n** linii se regăsesc distanțele **x [~t~]** despărțite printr-un spațiu, cu semnificația de mai sus.
* 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.
h2. Date de ieșire
* 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.
În fișierul de ieșire $cursaf13.out$ se vor afișa informațiile astfel:
h2. Date de ieșire
* Fiecare rând reprezintă răspunsul pentru o mașină. Ordinea mașinilor este cea din fișierul de intrare.
* Pe fiecare rând se afișează două numere, ce reprezintă coordonatele mașinii (linie și coloană) la sfârșitul ultimei perioade de timp **t**.
Î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**.
h2. Restricții
* 0 ≤ **ls**, **cs**
* **d** poate fi oricare dintre majusculele cuprinse între A - H
* 1 ≤ **k** ≤ 10 000
* 1 ≤ **n**, **t** ≤ 10 000
* 1 ≤ **x [~t~]** ≤ 10 000
* Circuitul nu poate avea mai mult de 10 000 de schimbări de direcție.
* Se garantează că circuitul se închide. O mașină 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.
* **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.
* 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.
* -Fiecare mașină pornește de pe primul pătrățel al primului segment pentru măsurarea distanței parcurse.-
* Se garantează că toate punctele circuitului au coordonate numere naturale.
* -Coordonatele finale ale mașinii se raportează la coordonatele **ls** și **cs**.-
* Se garantează că toate punctele circuitului au coordonate numere naturale mai mici decât 4 milioane
h2. Exemplu
table(example).
|_. cursaf13.in |_. cursaf13.out |_. Explicații |
| 0 0
C10E10G10A10
4 2
16 12 20 11
12 24 15 21
| 10 9
0 9
| 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;
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;
G10 - 10 pătrățele în stânga;
A10 - 10 pătrățele în sus.
După reprezentarea circuitului ca în figura alăturată, putem vedea cât a parcurs fiecare mașină.
Pentru mașina 1, vom parcurge 16 pătrățele pentru prima perioadă, apoi 12 pătrățele pentru a doua perioadă,
20 pătrățele pentru a treia perioadă și 11 pătrățele pentru ultima perioadă.
Astfel, mașina 1 se oprește -pe segmentul B- după schimbarea de direcție X, la coordonatele (10, 9).
Pentru mașina 2, vom parcurge 12 pătrățele pentru prima perioadă, apoi 24 pătrățele pentru a doua perioadă,
15 pătrățele pentru a treia perioadă și 21 pătrățele pentru ultima perioadă.
Astfel, mașina 2 se oprește pe segmentul B, la coordonatele (0, 9).
A8 - 8 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!
== include(page="template/taskfooter" task_id="cursaf13") ==
