Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Lista de probleme 10

Filtrare

Mai multe opțiuni

#4505 Mewtwo

Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.

Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M, fiecare celulă reprezentând conținutul unei camere. În această clădire se află:

  • Ash (codificat cu A): Ash se află inițial în această cameră
  • Mewtwo (codificat cu M): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință.
  • Gary (codificat cu G): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră
  • cameră liberă (codificată cu _): Ash poate accesa această cameră
  • cameră ocupată (codificată cu #): Ash nu poate accesa această cameră

Planul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N, E, S, V). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.

Rezolvă

#484 LantMinim

Se dă lista muchiilor unui graf neorientat și două vârfuri p q . Să se determine cel mai scurt lanț cu extremitățile p q.

Rezolvă

#538 LungimeMinima

Se dă lista muchiilor unui graf neorientat cu n vârfuri și vârf p . Să se determine toate nodurile q ale grafului cu proprietatea că lungimea minimă a unui lanț de la q la p este L.

Rezolvă

#541 Lant1

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

Rezolvă

#126 DMax

Să se determine maximul distanţelor minime între nodul 1 şi celelalte noduri, într-un graf neorientat.

Rezolvă

#1604 DMin

Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța de la x la y.

Rezolvă

#4074 Distante

Se consideră un graf neorientat conex cu n noduri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Se dă o pereche de noduri p q. Determinați nodurile r cu proprietatea că distanța minimă dintre p și r este egală cu distanța minimă dintre r și q.

Rezolvă

#549 Epidemie

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

Rezolvă

#4064 Ghiocel

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu indicele g locuiește Ghiocel. El are k colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghicei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

Rezolvă

#2165 graf1

Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului. Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1, 2, …, N și două vârfuri ale sale notate X și Y (1 ≤ X, Y ≤ N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.

OJI 2006

Rezolvă