Tommy este un motan alintat care adoră să se plimbe prin orice tunel. De aceea, stăpânii lui i-au construit o nouă jucărie, formată din N tuneluri interconectate (etichetate cu numerele distincte de la 1 la N. Toate tunelurile au aceeași lungime, sunt formate din M elemente unitare identice (numerotate cu numerele distincte de la 1 la M) și au ieșiri la ambele capete. Conectarea dintre două tuneluri alăturate se face printr-un element unitar numit pasaj. În exemplul din Figura 1, jucăria este formată din 4 tuneluri, fiecare tunel fiind format din 9 elemente unitare.
Pentru a fi mai provocator, stăpânii motanului plasează în ultimul element unitar al ultimului tunel o recompensă.
Motan isteț, Tommy a învățat deja toate regulile jocului:
- poate intra prin capătul din stânga al oricărui tunel (prin elementul unitar
1); - nu trece de multe ori prin același pasaj;
- dacă nu se află lângă un pasaj, continuă să meargă prin tunel către dreapta;
- dacă ajunge la un pasaj, atunci trece prin acesta în tunelul alăturat;
- dacă ajunge în ultimul element unitar al tunelului etichetat cu
N, atunci Tommy iese din acest tunel cu recompensă, chiar dacă ar exista un pasaj ce conectează acest ultim element la ultimul element din tunelulN-1(veziFigura 2.b); - dacă ajunge în ultimul element unitar al tunelului etichetat cu
N-1și există un pasaj care conectează acest element cu ultimul element unitar al tunelului etichetat cuN, atunci Tommy trece prin acest pasaj în ultimul element din ultimul tunel, ia recompensa și iese din tunelFigura 2.a). În cazul în care acest pasaj nu există, Tommy iese din tunelulN-1fără recompensă; - dacă ajunge în ultimul element unitar al unui tunel cu eticheta mai mică decât
N-1, atunci Tommy iese din tunel fără recompensă.
Ajutați-l pe Tommy să ajungă cât mai repede la recompensă respectând regulile jocului!
Cerința
Scrieţi un program care citește numerele naturale N, M și X, iar apoi determină:
- eticheta tunelului prin care iese Tommy dacă intră în tunelul cu eticheta
Xrespectând regulile jocului; - numărul
Lde elemente unitare (ale tunelurilor și ale pasajelor) prin care Tommy ar trebui să treacă, respectând regulile jocului, pentru a ajunge la recompensă.
Date de intrare
Fișierul tunel2.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată 1 sau 2.
A doua linie a fișierului conține cele trei numere naturale N, M și X, separate prin câte un spațiu, cu semnificația din enunț. Următoarele N-1 linii descriu pasajele dintre tuneluri. Prima linie dintre cele N-1 indică pasajele dintre tunelurile etichetate cu 1 și 2, următoarea linie indică pasajele dintre tunelurile etichetate cu 2 și 3, …, ultima dintre cele N-1 linii indică pasajele dintre tunelurile etichetate cu N-1 și N.
Primul număr din fiecare astfel de linie reprezintă numărul P de pasaje, iar următoarele P numere distincte, scrise în ordine crescătoare, reprezintă pozițiile elementelor unitare (dintre cele două tuneluri) conectate prin cele P pasaje.
Date de ieșire
- Dacă
C=1, fișierultunel2.outva conține pe prima linie un număr natural reprezentând răspunsul la cerința1. - Dacă
C=2, fișierultunel2.outva conține pe prima linie numărul naturalLreprezentând răspunsul la cerința2.
Restricții și precizări
3 ≤ N ≤ 10004 ≤ M ≤ 200001 ≤ P ≤ M−2- Pot exista cel mult
150000pasaje care interconectează tunelurile. - Pot exista pasaje învecinate care să conecteze elementele unitare din două tuneluri alăturate (vezi
Figura 1) în care tunelurile1și2sunt interconectate prin pasajele învecinate dintre elementele6, respectiv7). - Primul element unitar din fiecare tunel nu este conectat la niciun pasaj.
- Ultimul element unitar din tunelurile etichetate cu
1, 2,..., N-2nu este conectat la niciun pasaj. - Oricare element unitar poate fi conectat la cel mult un pasaj.
- Oricare două tuneluri etichetate cu numere consecutive sunt interconectate prin cel puțin un pasaj.
- Pentru fiecare intrare într-un tunel există traseu către ieșire.
- Pentru fiecare test există cel puțin o intrare într-un tunel prin care Tommy poate ajunge la ieșirea cu recompensă din tunelul
N. - Pentru cerința
1se acordă40p. iar pentru cerința2se acordă60p. - În concurs, limita de memorie a fost 32MiB.
Exemplul 1:
tunel2.in
1 4 9 4 3 2 4 6 2 3 5 3 4 6 9
tunel2.out
1
Explicație
Se rezolvă cerința 1 . N=4, M=9, X=4.
Tommy, intra prin tunelul etichetat cu X=4 și iese prin tunelul etichetat cu 1 (vezi Figura 2.d).
Exemplul 2:
tunel2.in
2 4 9 4 3 2 4 6 2 3 5 3 4 6 9
tunel2.out
17
Explicație
Se rezolvă cerința 2 . N=4, M=9, X=4. Figurile 2.a, 2.b, 2.c, 2.d conțin trecerea lui Tommy prin tunele pentru fiecare din cele patru intrări. Doar 2 dintre aceste treceri îl duc pe Tommy la recompensă (vezi Figura 2.a și Figura 2.b). Dacă Tommy intră prin tunelul 2 atunci el ajunge la recompensă trecând prin numărul minim L=17 (=min(17,19)) elemente unitare.
#include <fstream>
//#include <iostream>
using namespace std;
ifstream f("tunel2.in");
ofstream g("tunel2.out");
int C, N,NN,M,X,Y, lmin=-1, t;
char a[2005][20005];
void date()
{
int i,j,p,x;
f>>C>>N>>M>>X;
NN=2*N-1;
for(j=2;j<=NN;j=j+2)
{
f>>p;
for(i=1;i<=p;++i)
{ f>>x; a[j][x]=1; }
}
NN=2*N-1;
}
void drum1(int j, int i)
{
if(j==M)
{
Y=i;
if(i==NN-2 && a[NN-1][M]==1) Y=NN;
}
else
{
if(a[i+1][j]==1)drum1(j+1,i+2);
else
if(a[i-1][j]==1)drum1(j+1,i-2);
else
drum1(j+1,i);
}
}
void drum2(int j, int i, int k)
{
if(j==1)
{
if(lmin==-1)lmin=k;
else lmin=min(lmin,k);
}
else
{
if(a[i-1][j]==1)drum2(j-1,i-2,k+3);
else
if(a[i+1][j]==1)drum2(j-1,i+2,k+3);
else
drum2(j-1,i,k+1);
}
}
int main()
{
date();
if(C==1)
{
drum1(1,2*X-1);
g<<(Y+1)/2;
}
else
{
drum2(M-1,NN,2);
if(a[NN-1][M]==1) drum2(M-1,NN-2,4);
g<<lmin;
}
g<<'\n';
return 0;
}
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("tunel2.in");
ofstream g("tunel2.out");
const int NMAX = 1000;
const int MMAX = 20000;
const int SUS = 0;
const int JOS = 1;
const int STANGA = 2;
const int DREAPTA = 3;
int c, n, m, x;
vector <int> pasaj_in_jos[MMAX + 2];
void citeste() {
f >> c;
f >> n >> m >> x;
for (int i = 1; i < n; i++) {
int p;
f >> p;
for (int j = 1; j <= p; j++) {
int poz;
f >> poz;
pasaj_in_jos[poz].push_back(i);
}
}
}
bool am_pasaj_in_jos(int i, int j) {
int st = 0, dr = pasaj_in_jos[j].size() - 1;
while (st <= dr) {
int m = (st + dr) / 2;
if (pasaj_in_jos[j][m] == i) return true;
if (pasaj_in_jos[j][m] < i) st = m + 1;
else dr = m - 1;
}
return false;
}
bool am_pasaj_in_sus(int i, int j) {
return am_pasaj_in_jos(i - 1, j);
}
void c1() {
int i = x, j = 1;
int vin_din = STANGA;
while (j <= m && !(i == n && j == m)) {
if (vin_din == STANGA) {
if (am_pasaj_in_sus(i, j)) {
i--;
vin_din = JOS;
continue;
}
if (am_pasaj_in_jos(i, j)) {
i++;
vin_din = SUS;
continue;
}
}
j++;
vin_din = STANGA;
}
g << i << '\n';
}
int traseu_c2(int i, int j, int vin_din, int pasaje) {
while (j > 0) {
if (vin_din == DREAPTA) {
if (am_pasaj_in_sus(i, j)) {
i--;
vin_din = JOS;
pasaje++;
continue;
}
if (am_pasaj_in_jos(i, j)) {
i++;
vin_din = SUS;
pasaje++;
continue;
}
}
j--;
vin_din = DREAPTA;
}
return m + 2 * pasaje;
}
void c2() {
int lungime_minima = traseu_c2(n, m - 1, DREAPTA, 0);
if (am_pasaj_in_sus(n, m))
lungime_minima = min(lungime_minima, traseu_c2(n - 1, m, JOS, 1));
g << lungime_minima << '\n';
}
int main() {
citeste();
if (c == 1) c1();
else c2();
return 0;
}
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream f("tunel2.in");
ofstream g("tunel2.out");
const int NMAX = 1000;
const int MMAX = 200000;
const int SUS = 0;
const int JOS = 1;
const int STANGA = 2;
const int DREAPTA = 3;
int c, n, m, x;
set <int> pasaj_in_jos[MMAX + 2];
void citeste() {
f >> c;
f >> n >> m >> x;
for (int i = 1; i < n; i++) {
int p;
f >> p;
for (int j = 1; j <= p; j++) {
int poz;
f >> poz;
pasaj_in_jos[poz].insert(i);
}
}
}
bool am_pasaj_in_jos(int i, int j) {
return pasaj_in_jos[j].find(i) != pasaj_in_jos[j].end();
}
bool am_pasaj_in_sus(int i, int j) {
return am_pasaj_in_jos(i - 1, j);
}
void c1() {
int i = x, j = 1;
int vin_din = STANGA;
while (j <= m && !(i == n && j == m)) {
if (vin_din == STANGA) {
if (am_pasaj_in_sus(i, j)) {
i--;
vin_din = JOS;
continue;
}
if (am_pasaj_in_jos(i, j)) {
i++;
vin_din = SUS;
continue;
}
}
j++;
vin_din = STANGA;
}
g << i << '\n';
}
int traseu_c2(int i, int j, int vin_din, int pasaje) {
while (j > 0) {
if (vin_din == DREAPTA) {
if (am_pasaj_in_sus(i, j)) {
i--;
vin_din = JOS;
pasaje++;
continue;
}
if (am_pasaj_in_jos(i, j)) {
i++;
vin_din = SUS;
pasaje++;
continue;
}
}
j--;
vin_din = DREAPTA;
}
return m + 2 * pasaje;
}
void c2() {
int lungime_minima = traseu_c2(n, m - 1, DREAPTA, 0);
if (am_pasaj_in_sus(n, m))
lungime_minima = min(lungime_minima, traseu_c2(n - 1, m, JOS, 1));
g << lungime_minima << '\n';
}
int main() {
citeste();
if (c == 1) c1();
else c2();
return 0;
}