Question

5.Căpitanul Jack O’Neel se află pe o navă spaţială. Nava are lungimea de n camere şi lăţimea de o cameră. El se află în camera numărul 1. În fiecare cameră se află un dispozitiv de teleportare. Acest dispozitiv te poate teleporta într-o altă cameră din cele n. Să se spună dacă O’Neel poate ajunge în camera h. Date de intrare: Pe prima linie numărul n şi numărul h. Pe a doua linie sunt n numere, fiecare număr indică în ce cameră îl transmite pe Jack O’Neel teleportorul din acea cameră. Date de ieşire: Dacă O’Neel poate ajunge în camera h se va printa „DA” şi camerele prin care a trecut. Dacă nu poate ajunge în camera h să se printeze „NU”. Obs: Dacă O’Neel trece de două ori prin aceeaşi cameră, acesta nu mai încearcă să ajungă în camera h şi se va printa „NU”. Exemple: Date de intrare: n=5 h=4 teleportari: 2 3 4 1 3 Date de ieşire: DA 1 2 3 4 Date de intrare: n=4 h=4 teleportari:1 2 3 4 date de ieşire: NU

Answer 1

#include <iostream>

using namespace std;

struct camera{int dest;bool a_fost=false;};

camera cam[100000];

int trecut[100000];

int main(){

int n,h;

cin>>n>>h;

for(int i = 1;i<=n;i++)

{

cin >> cam[i].dest;

}

cam[1].a_fost = true;
trecut[0]=1;
int ptr = 1;

int pos = 1;

while(!cam[h].a_fost){

pos = cam[pos].dest;
trecut[ptr++]=pos;

if(cam[pos].a_fost){cout << "NU";return 0;}
cam[pos].a_fost = true;

}

cout << "DA";
for(int i = 0; i < ptr;i++){
cout << trecut[i] << " ";
}

}