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

Lista de probleme 7

Filtrare

Mai multe opțiuni

#2309 Competitie

La o competiție au participat N concurenți. Fiecare dintre ei a primit un număr de concurs astfel încât să nu existe concurenți cu același număr. Numerele de concurs aparțin mulțimii {1,2,...,N}. Din păcate, clasamentul final a fost pierdut, iar comisia își poate aduce aminte doar câteva relații între unii participanți (de genul “participantul cu numărul 3 a ieșit înaintea celui cu numărul 5”). Șeful comisiei are nevoie de un clasament final și vă cere să-l ajutați determinând primul clasament în ordine lexicografică ce respectă relațiile pe care și le amintește comisia.

ONI 2001, clasa a IX-a

Rezolvă

#2123 Relatii

Să considerăm N variabile, denumite cu litere mici ale alfabetului englez, începând cu litera a. Să considerăm de asemenea M relaţii de ordine între aceste N variabile, sub forma: var1>var2 sau var1<var2, unde var1 şi var2 sunt două nume de variabile (deci litere mici distincte dintre primele N litere ale alfabetului englez).

Scrieţi un program care să ordoneze crescător cele N variabile pe baza celor M relaţii cunoscute.

Olimpiada Municipala Informatica Iasi 2015

Rezolvă

#1861 TopSort

Se dă un graf orientat aciclic cu N noduri numerotate de la 1 la N. Să se realizeze o sortare topologică a nodurilor.

Rezolvă

#2768 SortTopMinLex

Se consideră un graf orientat aciclic cu n noduri și m arce. Să se determine sortarea topologică a nodurilor grafului, minimă lexicografic.

Folclorul informatic

Rezolvă

#4027 LongestPath

Se dă un graf orientat aciclic (adică nu există circuite). Lungimea unui drum elementar este dată de numărul de arce. Să se determine lungimea maximă a unui drum elementar în acest graf orientat aciclic.

Folclorul informatic

Rezolvă

#1101 Project Management

La o firmă de software se lucrează la un mare proiect. Proiectul constă în executarea a n (n număr natural) faze de dezvoltare, numerotate cu numerele 1, 2, …, n. Unele faze pot fi executate în paralel (în acelaşi timp), însă executarea altor faze nu poate fi începută până când nu se finalizează executarea anumitor faze.

Să se scrie un program care să se determine:

a) timpul minim t în care se poate finaliza executarea proiectului
b) pentru fiecare fază k (k din {1,2,…,n}), momentul de timp ck la care poate începe faza k cel mai devreme, respectiv momentul de timp dk la care poate începe faza k cel mai târziu, fără a influenţa durata totală de executare a proiectului.

OJI 2009, Clasele XI-XII

Rezolvă

#146 graph

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă. Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Grigore Moisil 2013

Rezolvă