ai

Institutul Naţional de Robotică Avansată realizează o serie de teste ultimei generaţii de roboţi inteligenţi proiectaţi de specialiştii acestuia. Sistemul de testare se bazează pe o reţea de senzori formată din $n$ segmente egale dispuse orizontal şi $n$ segmente egale dispuse vertical. Distanţa între două segmente alăturate orizontale, respectiv verticale este de $1$ metru. Fiecare segment orizontal este în contact cu fiecare segment vertical. Denumim nod un punct în care un segment orizontal şi unul vertical vin în contact. Segmentele sunt numerotate: cele orizontale de sus în jos începând de la $1$ iar cele verticale de la stânga la dreapta începand de la $1$.

Un nod va fi identificat prin două numere: primul reprezintă numărul segmentului orizontal iar al doilea numărul segmentului vertical care vin în contact în respectivul nod.

Într-unul dintre nodurile reţelei se află o ţintă. În alte două noduri se află câte o sursă ce emite o rază laser. O astfel de sursă emite raza într-o singură direcţie. Raza laser are o grosime neglijabilă. Cele două surse sunt astfel orientate încât raza emisă de fiecare “loveşte” ţinta. Cele două noduri în care sunt plasate sursele sunt astfel alese încât cele două raze nu se intersectează decât în nodul unde se află ţinta.

În alte două noduri ale reţelei se află câte un robot. Fiecare robot se poate deplasa dintr-un nod în cele vecine (cele aflate sus, jos, în stânga şi în dreapta), dar fără să iasă din cadrul reţelei. Roboţii se deplasează cu $1$ m/secundă.

Se efectuează experimente în care roboţii sunt programaţi să se deplaseze prin reţea cu scopul de a proteja ţinta faţă de cele două raze laser. Un robot poate proteja ţinta fie ocupând nodul unde se află sursa, fie ocupând un nod prin care trece raza laser în drumul de la sursă către ţintă (razele laser nu “ocolesc” roboţii). Dimensiunea roboţilor este atât de mică încât, în acest al doilea caz, ei protejează ţinta faţă de raza laser doar când nodurile unde sunt sursa, ţinta şi robotul sunt coliniare iar robotul este între sursă şi ţintă. În momentul în care un robot ajunge într-un nod unde protejează ţinta faţă de una dintre raze, el se poate opri sau poate să îşi continue deplasarea. Dacă îşi continuă deplasarea astfel încât noua poziţie ocupată de acel robot şi poziţiile ţintei şi sursei nu mai sunt coliniare, atunci acel robot nu mai protejează ţinta. Din modul în care sunt alese poziţiile nodurilor pentru ţintă şi sursele laser rezultă că nu există nicio poziţie în care un robot să protejeze simultan ţinta faţă de ambele raze.

Fiecare robot este dotat cu o reţea neuronală şi poate învăţa din experimentele anterioare pe unde să se deplaseze. Pentru a mări capacitatea de adaptare a roboţilor, în $k$ noduri ale reţelei sunt aşezate obstacole care fac ca roboţii să nu poată trece prin nodurile respective. Deoarece obstacolele folosite sunt transparente, razele laser pot trece prin acestea fără a le fi afectată intensitatea sau direcţia. Două sau mai multe obstacole dispuse pe acelaşi segment, în noduri alăturate, formează un zid. Lungimea unui zid este egală cu numărul de obstacole din care este alcătuit.

Cerinţă

$1)$ Determinaţi lungimea maximă a unui zid.
$2)$ Determinaţi numărul minim de secunde în care cei doi roboţi pot proteja ţinta faţă de cele două raze laser.

Date de intrare

Fişierul ai.in conţine:

• pe prima linie o valoare naturală $n$, reprezentând numărul segmentelor ce compun reţeaua;
• pe a doua linie cinci perechi de valori naturale separate prin câte un spaţiu $T_1 \ T_2 \ S_1 \ S_2 \ S_3 \ S_4 \ R_1 \ R_2 \ R_3 \ R_4$ cu următoarea semnificaţie: $T_1 \ T_2$ reprezintă coordonatele nodului unde se află ţinta, $S_1 \ S_2$ coordonatele nodului în care este amplasată prima sursă, $S_3 \ S_4$ coordonatele nodului în care este amplasată a doua sursă, $R_1 \ R_2$ coordonatele poziţiei iniţiale a primului robot, respectiv $R_3 \ R_4$ coordonatele poziţiei iniţiale a celui de-al doilea robot;
• pe a treia linie o valoare naturală $k$, reprezentând numărul obstacolelor din reţea;
• pe următoarele $k$ linii se găseşte câte o pereche de valori naturale separate printr-un spaţiu. Fiecare prereche reprezintă coordonatele unui nod în care este amplasat un obstacol.

Date de ieșire

Fişierul ai.out va conţine pe prima linie un număr natural ce reprezintă răspunsul la cerinţa $1)$ iar pe a doua linie un număr natural care reprezintă răspunsul la cerinţa $2)$.

Restricții și precizări

• $n \leq 1 \ 000$
• $k \leq 150 \ 000$

• la începutul experimentului poziţiile ţintei, surselor laser, roboţilor şi obstacolelor sunt diferite.
• roboţii nu pot ocupa şi nu pot trece prin nodul în care se află ţinta,
• roboţii pot ocupa un nod în acelaşi timp.
• un robot nu poate proteja ţinta faţă de o rază decât atunci când este plasat exact într-un nod, nu şi atunci când se află între două noduri.
• un obstacol poate să aparţină în acelaşi timp atât unui zid orizontal cât şi unui zid vertical.
• dacă fişierul de ieşire conţine o singură valoare, se consideră că aceasta reprezintă răspunsul la prima cerinţă
• în toate testele efectuate, există cel puţin o posibilitate ca ţinta să fie apărată de către una dintre raze de unul dintre roboţi iar faţă de cealaltă rază să fie apărată de celălalt robot.
• pentru rezolvarea primei cerinţe se acordă $20\%$ din punctaj; pentru rezolvarea ambelor cerinţe se acordă $100\%$ din punctaj.

Exemplu

ai.in

6
4 4 1 1 6 5 1 3 3 4
8
1 2 
2 3 
2 5 
4 2 
6 2 
2 2 
2 4 
5 2

ai.out

4
8

Explicație

Cel mai lung zid are lungimea $4$ (este cel plasat pe segmentul orizontal cu numărul $2)$; obstacolele de pe segmentul vertical $2$ formează două ziduri cu lungimile $2$ şi $3$.

Primul robot ajunge în $4$ secunde în poziţia $6 \ 5$ protejând astfel ţinta faţă de raza emisă de sursa din poziţia $6 \ 5$ iar al doilea în 8 secunde în poziţia $3 \ 3$ protejând astfel ţinta faţă de raza emisă de sursa din poziţia $1 \ 1$. După $8$ secunde ţinta e protejată faţă de ambele raze laser.