Lista de probleme 892

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.

Scrieţi un program care, pentru o matrice 9 x 9 dată, reprezentând un puzzle SUDOKU, determină o soluţie a unui astfel de puzzle.

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

1. Numărul de elicoptere cumpărate să fie minim.
2. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
3. Suma lungimii tuturor rutelor să fie minimă.

Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

1. numărul minim de elicoptere ce vor fi cumpărate de administraţie;
2. numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
3. suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

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.

Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe. Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

După ce în problema #Plata şi-a cumpărat biscuiţi, iar în problema #Maraton şi-a făcut temele, Costy s-a hotărât să meargă în vizită la prietenul său Paul. Și pentru că Paul este prietenul său cel mai bun, bineînţeles că nu se va duce cu mâna goala. Va trece pe la magazin şi îi va cumpăra un pachet de biscuiţi. Marea problemă a eroului nostru este oraşul rău famat, la fiecare intersecţie existând pericole. Oraşul are forma de două triunghiuri dreptunghice isoscele cu un vârf comun, ca în figura următoare:

C 
X X
X X X
X X X B
      X X
      X X X
      X X X P 

C – reprezintă poziţia iniţială a lui Costy, care se va afla mereu în colţul din stânga sus.
B – reprezintă poziţia magazinului, care se va afla mereu în vârful comun al celor 2
triunghiuri.
P – reprezintă poziţia lui Paul, care se va afla mereu în colţul din dreapta jos.

Cum spuneam, la fiecare intersecţie există pericole. O intersecţie X[i][j] reprezintă intersecţia străzii orizontale i, cu strada verticală j. Gradul de periculozitate al unei intersecţii este un număr întreg X[i][j]. Definim gradul unui drum ca fiind suma gradelor intersecţiilor ce compun acel drum.

Costy poate merge de la o intersecţie X[i][j], doar la o intersecţie X[i][j + 1] (în dreapta) sau X[i + 1][j](în jos).

Eroul nostru, Costy merge la magazin pentru a-şi cumpăra biscuiţi. Vânzătorul îi spune că biscuţii costă S nasturi, şi că doreste ca plata lor să fie făcută cu n tipuri diferite de nasturi. De asemenea, vânzătorul precizează că ar dori ca numărul de nasturi din fiecare tip i să depăşească valoarea x[i], dar, să nu depăşească valoarea y[i]. Presupunând că baiatul are o infinitate de nasturi din fiecare tip şi că doreşte să rămână cu cât mai mulţi nasturi de tipurile n, n-1, n-2,.. în buzunar, ajutaţi-l să efectueze plata şi să pună cât mai repede mâna pe biscuiţi.