Lista de probleme 3

Etichete

N oraşe sunt conectate între ele prin M autostrăzi bidirecţionale, fiecare autostradă (a, b) având un cost de tranzit c ataşat. Se doreşte revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul şi necesită investigaţie, deoarece o parte dintre cele N oraşe sunt centre comerciale sau turistice importante.

Se doreşte să se afle răspunsul la o serie de Q întrebări de forma: (X, T) – câte dintre celelalte N-1 oraşe, au acces către oraşul X, cu o taxă totală de cel mult T către fiecare oraş?

#3004 Links

Se dau N puncte din plan prin coordonatele lor.
Se mai dau Q perechi de puncte, diferite de cele date inițial.

Să se verifice, pentru fiecare pereche de puncte (A , B) dintre cele Q, dacă există traseu care pornește din A și ajunge în B, prin deplasări cu pași de lungime 1 spre Nord, Vest, Sud, Est și evitând orice punct dintre cele N date inițial.

#3005 Sormin

Se dau un șir A[1..N] și un număr S. Dintre toate subșirurile de suma S, să se determine un subșir pentru care suma OR, pe biți, este minimă.