Mihai, fiind un mare pasionat al jocurilor în aer liber, a inventat un joc nou în speranța că își va convinge colegii să iasă afară să se joace. Jocul lui Mihai spune că se dau N pătrate ce se află la anumite nivele iar din fiecare pătrat se poate sări doar în anumite pătrate stabilite la începutul jocului. Dacă un jucător sare dintr-un pătrat aflat la nivelul X într-un pătrat aflat la un nivel mai mare Y, acesta folosește un efort egal cu [Y/X], iar dacă sare într-un pătrat aflat la un nivel mai mic sau egal Y, efortul folosit este [X/Y]. Jucătorul se află la început în pătratul de start S și scopul jocului este să ajungă în pătratul final F, depunând un efort minim.
Cerința
Cunoscând numărul de pătrate N, pătratul de start S, pătratul final F și pentru fiecare pătrat, pătratele în care jucătorul poate sări, se cere:
a) Efortul minim necesar pentru a ajunge în pătratul final.
b) Pătratele pe care jucătorul le sare până ajunge la pătratul final.
Date de intrare
Fişierul de intrare joc.in conține pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află trei numere naturale N, S și F cu semnificația din enunț. Pe următoarea linie se află N numere naturale reprezentând nivelul la care se află fiecare pătrat. Pe următoarele N linii se află pătratele în care se poate sări din fiecare pătrat. Astfel, pe linia i se află numărul de pătrate în care se poate sări din pătratul i-3 urmat de pătratele în care se poate sări. Dacă dintr-un pătrat nu se poate sări în niciun alt pătrat atunci pe linia lui se află 0.
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerintă. În acest caz, în fişierul de ieşire joc.out se va scrie un singur număr întreg reprezentând efortul minim necesar pentru a ajunge în pătratul final.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerintă. În acest caz, în fișierul de iesire joc.out se va scrie pe prima linie un număr natural M reprezentând numărul de pătrate necesare pentru a ajunge în pătratul final iar pe linia a doua se vor scrie cele M pătrate.
Restricții și precizări
1 ≤ S, F ≤ N ≤ 50 000S ≠ F- numărul total al săriturilor stabilite la începutul jocului nu depăşeşte
500 000; - nivelul maxim al unui pătrat
≤ 50 000; - va exista întotdeauna o modalitate printr-un număr nenul de pași de a ajunge de la pătratul
Sla pătratulF; - pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, iar pentru cerința a doua se acordă 60 de puncte.
Exemplul 1:
joc.in
1 5 1 4 20 10 34 45 5 2 2 3 2 4 5 0 2 1 3 2 4 1
joc.out
6
Explicație
p = 1
Pentru a ajunge din primul pătrat adică pătratul aflat la nivelul 20 în cel de-al patrulea pătrat adică pătratul aflat la nivelul 45 cu un efort minim jucătorul sare de pe pătratul aflat la nivelul 20 pe pătratul aflat la nivelul 10 cu efortul 2 iar de pe pătratul aflat la nivelul 10 pe pătratul aflat la nivelul 45 cu efortul 4 obținând efortul 6.
Atenție! Pentru acest test se rezolvă doar cerința a).
Exemplul 2:
joc.in
2 5 1 4 20 10 34 45 5 2 2 3 2 4 5 0 2 1 3 2 4 1
joc.out
3 1 2 4
Explicație
p = 2
Pentru a ajunge din primul pătrat adică pătratul aflat la nivelul 20 în cel de-al patrulea pătrat adică pătratul aflat la nivelul 45 cu un efort minim jucătorul sare de pe pătratul aflat la nivelul 20 pe pătratul aflat la nivelul 10 iar de pe pătratul aflat la nivelul 10 pe pătratul aflat la nivelul 45.
Atenție! Pentru acest test se rezolvă doar cerința b).
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Joc:
#include<stdio.h>
#define infinit 2000000000
struct nod
{
int inf , c;
nod * urm;
} * l[50005];
FILE *f;
int n,nh,m,x[50005],d[50005],t[50005],poz[50005],nivel[50005],P,S,F,nr=0;
void cit()
{
nod *p;
int a,b,i,j;
freopen("joc.in","r",stdin);
scanf("%d%d%d%d",&P,&n,&S,&F);
for(i=1;i<=n;i++){
l[i] = 0;
scanf("%d" , &nivel[i]);
}
for(i=1;i<=n;i++)
{
scanf("%d",&a);
for(j=1 ; j<=a ; j++){
scanf("%d" , &b);
p=new nod;
p -> inf = b;
if(nivel[i] > nivel[b])
p ->c = nivel[i]/nivel[b];
else
p ->c = nivel[b]/nivel[i];
p -> urm = l[i];
l[i] = p;
}
}
fclose(stdin);
}
void swap(int i,int j){
int aux;
poz[x[i]] = j;
poz[x[j]] = i;
aux = x[i];
x[i] = x[j];
x[j] = aux;
}
void HeapUp(int k){
if(k<=1)
return;
if(d[x[k]]<d[x[k/2]]){
swap(k,k/2);
HeapUp(k/2);
}
}
void HeapDw(int r,int k){
int st,dr,i;
if(2*r<=k){
st=d[x[2*r]];
if(2*r+1<=k)
dr=d[x[2*r+1]];
else
dr=st+1;
if(st<dr)
i=2*r;
else
i=2*r+1;
if(d[x[r]]>d[x[i]]){
swap(i,r);
HeapDw(i,k);
}
}
}
void BuildH(int k){
int i;
for(i=1;i<=k;i++)
HeapUp(i);
}
int scoate_heap(){
swap(1,nh);
poz[x[nh]]=0;
nh--;
HeapDw(1,nh);
return x[nh+1];
}
void dijkstra(int S)
{
int i,k;
nod *p;
for(i=1;i<=n;i++){
x[i]=poz[i]=i;
t[i]=0;
d[i]=infinit;
}
d[S]=0;
BuildH(n);
nh=n;
while(nh > 0){
k = scoate_heap();
p = l[k];
while( p ){
if(d[p->inf] > d[k]+p->c)
{
d[p->inf]=d[k]+p->c;
t[p->inf]=k;
HeapUp(poz[p->inf]);
}
p = p -> urm;
}
}
}
void lant(int i){
if(i!=0){
lant(t[i]);
nr++;
x[nr]=i;
}
}
int main(){
cit();
dijkstra( S );
FILE *f;
f=fopen("joc.out","w");
if(P==1)
fprintf(f,"%d
",d[F]);
else{
lant(F);
fprintf(f,"%d
",nr);
for(int i=1;i<=nr;i++)
fprintf(f,"%d ",x[i]);
}
fclose(f);
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #630 Joc
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #630 Joc de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!