Lista de probleme 888

După o zi productivă de făcut curățenie, Henry și Hetty au ieșit în oraș la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, 1 ≤ i ≤ N, cunoaștem atât numărul K[i] de mese cu care este conectată direct, cât și lista ordonată de mese vecine acesteia: V[i,1], V[i,2] … V[i,K[i]].

Benzile rulante au rolul de a transporta preparatele la clienți. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa V[i,j], va pleca de la masa i spre masa:

• V[i,j+1], dacă 1 ≤ j < K[i]
• V[i,1], dacă j = K[i].

În plus, dacă un preparat nou este trimis de la masa 1 spre masa V[1,1], știm că acesta va ajunge la masa i pentru prima oară venind dinspre masa V[i,1], pentru orice i, 1 ≤ i ≤ N.

Henry și Hetty au intrat în restaurant la momentul de timp 0. Ei știu că pe parcursul vizitei lor pe benzile rulante vor fi așezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul (x, y, t), semnificând faptul că la momentul de timp t preparatul va fi așezat pe bandă în dreptul mesei x pentru a pleca spre spre masa V[x,y]. Ei mai știu și că timpul necesar unui preparat de a parcurge distanța dintre două mese vecine este de o unitate. Cei doi se vor așeza la o masă și vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry și Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?

După calificarea la campionatul european de fotbal din Franța, având în vizor N jucători din care trebuie să convoace câțiva în echipa națională, selecționerul României a apelat la niște metode mai puțin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să găsească formula câștigătoare pentru meciul de deschidere cu Franța. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucători trebuie sa aibă valoarea exact X și coeficientul de aroganță cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componența lotului. Coeficientul de aroganță al unui lot de jucători e definit ca diferența dintre valoarea maximă a unui jucător din lot și valoarea minimă a unui jucător din lot. Se mai știe că valoarea lotului nu poate depăși o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulțime nevidă de jucători aleși dintre cei N. Atenție, un lot poate fi format și dintr-un singur jucător.

Se dă numărul N de jucători, numărul Vmax definit mai sus și valoarea fiecărui jucător. Selecționerul României a găsit formula câștigătoare și e curios dacă puteți și voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflați pentru fiecare valoare X din intervalul [1,Vmax] coeficientul de aroganță minim posibil pentru care există cel puțin un lot dintre cei N jucători cu valoare exact X. Dacă nu se poate obține nici un lot de valoare exact X, se consideră ca răspuns -1.

Eșuînd în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Se dă un graf orientat în care arcele au asociate costuri (numere naturale nenule). Să se determine câte arce (x,y) din graf au costul egal cu costul drumului de cost minim de la x la y.

Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

Se dau n numere naturale. Determinaţi o aranjare a acestor numere pe un cerc, astfel încât suma produselor de câte două numere vecine să fie maximă.

Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:

1. Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
2. Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.

Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.

Aurel a învăţat la matematică despre şiruri de numere. Fiind curios din fire, el ar vrea acum să ştie câte şiruri crescătoare de numere naturale nenule cu suma elementelor mai mică sau egală cu S există.

Ajutaţi-l pe Aurel să afle câte astfel de şiruri există.

X şi Y se joacă cu N biluţe, fiecare biluţă având scrisă pe ea o cifră nenulă. Inventivi din fire, aceştia au împărţit cele N biluţe în două grămezi, astfel încât valoarea medie a grămezii lui X să fie egală cu valoarea medie a grămezii lui Y. Valoarea medie a unei grămezi este egală cu suma tuturor numerelor din grămadă împărţită la numărul de elemente ale acesteia.

Dându-se cele N valori scrise pe biluţe, aflaţi în câte moduri pot fi împărţite biluţele în două grămezi ale căror valori medii să fie egale. Cum acest număr poate fi prea mare, afişaţi doar restul împărţirii acestui număr la 666013.

Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor.

Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său.