Încercați-vă puterile!
PROBLEME propuse pentru REZOLVAREÎn ultimele două numere ale GInfo ați fost provocați la întrecere cu problemele de selecție date lotului lărgit de informatică. Din păcate "nu ați ridicat mănușa...", am primit foarte puține rezolvări. În acest număr al revistei supunem atenției problemele cu care s-au confruntat concurenții de la Olimpiada de Informatică a Europei Centrale și de Est. P089801: PătrateSe dau N pătrate situate în plan, având laturile pa ralele cu axele de coordonate. Coordonatele vârfurilor sunt numere întregi. Pătratele nu se ating și nu se suprapun. Se cere să se determine numărul de pătrate vizibile din originea O, O = (0,0). Un pătrat este vizibil din originea O, dacă există două puncte distincte A și B de coordonate întregi, situate pe o aceeași latură a pătratului, astfel încât interiorul triunghiului OAB nu are puncte comune cu nici unul dintre celelalte pătrate. Date de intrare Prima linie a fișierului de intrare SQUARES.IN conține un număr întreg N, 1<=N<=1000, reprezentând numărul de pătrate. Fiecare din următoarele N linii descrie un pătrat prin numerele întregi X, Y și L separate prin câte un spațiu 1<=X,Y,L<=10000. X și Y sunt coordonatele colțului din stânga-jos al pătratului, iar L este lungimea laturii. Date de ieșire Prima (și singura) linie a fișierului de ieșire SQUARES.OUT trebuie să conțină numărul pătratelor vizibile din origine. Exemple SQUARES.IN SQUARES.OUT 3 3 2 6 3 1 4 1 3 4 1 SQUARES.IN SQUARES.OUT 4 2 1 2 1 3 1 1 2 4 2 3 7 1 P089802: Cărți de jocAlice și Bob au o mulțime de N cărți de joc etichetate cu numere de la 1 la N (două cărți nu pot avea aceeași etichetă) și o mașină de amestecat cărțile. Presupunem că N este număr impar. Mașina acceptă o mulțime de cărți aranjate arbitrar și realizează următoarea operație de dublă-amestecare: pentru fiecare poziție i, 1<=i<=N, în cazul în care cartea de pe poziția i are eticheta j și cartea de pe poziția j are eticheta k, atunci după terminarea operației de dublă-amestecare, poziția i va fi ocupată de cartea având eticheta k. Alice și Bob se joacă. Alice scrie (pentru ea) numerele de la 1 la N într-o ordine oarecare: a1, ..., aN. Apoi, rearanjează cărțile astfel încât poziția ai să fie ocupată de cartea etichetată cu ai+1 pentru orice i, 1<=i<=N-1. Poziția aN va fi ocupată de cartea cu eticheta a1. Astfel cărțile sunt așezate în ordinea x1, x2, ..., xN, unde xi este cartea de pe poziția i. În continuare Alice execută S operații de dublă-amestecare, folosind mașina. În final cărțile ajung în ordinea p1, p2, ..., pN pe care Alice o comunică lui Bob. De asemenea îi comunică și numărul S. Bob trebuie să găsească ordinea x1, x2, ..., xN în care se aflau inițial cărțile (înainte de prima operație de amestecare). Date de intrare Prima linie a fișierului de intrare CARDS.IN conține două numere întregi separate printr-un spațiu: numărul întreg impar N, 1<=N<=1000, reprezentând numărul de cărți și numărul întreg S, 1<=S<=1000, reprezentând numărul operațiilor de dublă-amestecare. Următoarele linii descriu ordinea finală a cărților după executarea celor S operații de dublă-amestecare. Pentru fiecare a i-a operație, 1<=i<=N, linia i+1 din fișierul de intrare conține pi (eticheta cărții de pe poziția i după efectuarea tuturor operațiilor de dublă-amestecare). Date de ieșire Fișierul de ieșire CARDS.OUT va conține N linii care descriu ordinea cărților înainte de prima operație de dublă-amestecare. Pentru orice i, 1Ł iŁ N, linia i din fișierul de ieșire trebuie să conțină o valoare xi (eticheta cărții de pe poziția i, înainte de prima operație de dublă-amestecare). Exemple CARDS.IN CARDS.OUT 5 2 2 4 5 1 4 5 1 3 3 2 CARDS.IN CARDS.OUT 7 4 4 6 7 3 5 1 6 2 1 4 2 7 3 5 P089803: ReduceriFie o secvență de N numere întregi și pozitive: a=[a1,a2,...,aN] asupra căreia se pot efectua operații de reducere. O operație de reducere constă în înlocuirea a două elemente consecutive ai și ai+1 prin diferența ai-ai+1. Pentru o secvență de N numere întregi, se pot efectua exact N-1 operații de reducere distincte, fiecare generând o nouă secvență cu N-1 elemente. De exemplu, notăm cu con(a,i) secvența de N-1 elemente obținută din a=[a1,a2,...,aN] prin înlocuirea elementelor ai și ai+1 cu numărul întreg ai-ai+1: con(a,i)=[a1,...,ai-1,ai-ai+1,ai+2,...,aN] Efectuând N-1 reduceri asupra unei secvențe de N numere întregi, evident se va obține, în final, un singur număr. De exemplu, efectuând reducerile 2, 3, 2 și 1 în această ordine asupra secvenței [12,10,4,3,5] se obține numărul 4, astfel: con([12,10,4,3,5],2) = [12,6,3,5] con([12,6,3,5] ,3) = [12,6,-2] con([12,6,-2] ,2) = [12,8] con([12,8] ,1) = [4] Dată fiind o secvență a1, a2,..., aN și un număr T, să se determine o succesiune de N-1 reduceri care trebuie efectuate asupra secvenței date inițial, astfel încât să se obțină numărul T. Date de intrare Prima linie a fișierului de intrare SUBTRACT.IN conține două numere întregi separate printr-un spațiu: N, 1<=N<=100, reprezentând numărul de elemente din secvența inițială, și numărul T, 10000<=T<=10000. Următoarele N linii conțin elementele secvenței date, fiecare număr ai pe linie nouă, 1<=ai<=100. Date de ieșire Fișierul de ieșire SUBTRACT.OUT conține N-1 linii, descriind o succesiune de operații de reducere care transformă secvența dată inițial în numărul T. Linia k din fișierul de ieșire conține un număr întreg reprezentând a k-a operație de reducere aplicată secvenței. Se presupune că există cel puțin o asemenea succesiune de reduceri. Exemple SUBTRACT.IN SUBTRACT.OUT 4 5 1 10 2 2 1 5 2 SUBTRACT.IN SUBTRACT.OUT 5 4 2 12 3 10 2 4 1 3 5 P089804: SoldațiN soldați din țara Caroiaj sunt așezați la întâmplare pe teritoriul țării. O poziție în țara Caroiaj este dată de coordonatele (x,y), numere întregi. Soldații pot să-și schimbe poziția astfel: într-o mutare, un soldat poate să se deplaseze cu o unitate în sus, în jos, la stânga sau la dreapta (își schimbă fie coordonata x, fie coordonata y cu 1 sau -1). Soldații vor să se alinieze pe orizontală, unul lângă altul (astfel încât pozițiile lor finale vor fi (x,y), (x+1,y), ..., (x+N-1,y), pentru un anumit x și y). Întregii x și y sunt oarecare. Ordinea finală a soldaților pe linie, este de asemenea oarecare. Să se determine numărul minim de schimbări de poziție a tuturor soldaților, necesare pentru aliniere. Doi sau mai mulți soldați nu pot ocupa în același timp aceeași poziție. Date de intrare Prima linie a fișierului SOLDIERS.IN conține un număr întreg N, 1<=N<=10000, reprezentând numărul de soldați. Următoarele N linii conțin pozițiile inițiale ale soldaților: pentru orice i, 1<=i<=N, linia i+1 conține o pereche de numere întregi x[i] și y[i] separate printr-un singur spațiu, reprezentând coordonatele soldatului i, -10000<=x[i], y[i]<=10000. Date de ieșire Prima și singura linie a fișierului de ieșire SOLDIERS.OUT va conține numărul minim total de schimbări de poziție a soldaților, necesar pentru aliniere. Exemple SOLDIERS.IN SOLDIERS.OUT 3 4 1 0 2 4 3 2 SOLDIERS.IN SOLDIERS.OUT 5 8 1 2 2 2 1 3 3 -2 3 3 P089805: ȘoseleN orașe numerotate de la 1 la N sunt legate prin șosele cu sens unic. Fiecărei șosele i se asociază lungimea sa și taxa (exprimată în număr de monede), care trebuie plătită pentru parcurgerea acesteia. Bob și Alice locuiesc în orașul 1. După ce Bob și-a dat seama că Alice a trișat la jocul cu cărți, s-au certat și a hotărât să se mute în orașul N. El vrea să ajungă acolo cât mai repede posibil, dar stă cam prost cu banii. Să se determine cel mai scurt drum de la orașul 1 la orașul N, care poate fi parcurs cu cel mult toată suma de bani pe care-i are Bob la dispoziție. Date de intrare Prima linie a fișierului de intrare ROADS.IN conține un număr întreg K, 0<=K<=10000, reprezentând numărul maxim de monede pe care le poate cheltui Bob. A doua linie conține un număr întreg N, reprezentând numărul de orașe, (2<=N<=100) . A treia linie conține un întreg R, 1<=R<=10000, reprezentând numărul de șosele. Următoarele R linii oferă informații despre fiecare dintre cele R șosele:
S, D, L și T sunt numere întregi separate printr-un singur spațiu. Rețineți că aceleași două orașe pot fi legate prin șosele diferite. Date de ieșire Prima și singura linie din fișierul de ieșire ROADS.OUT trebuie să conțină lungimea drumului dintre orașul 1 și orașul N care necesită pentru parcurgere taxe în valoare totală mai mică sau egală decât K. Dacă nu există drum, în fișierul de ieșire se va scrie numărul -1. Exemple ROADS.IN ROADS.OUT 5 11 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2 ROADS.IN ROADS.OUT 0 -1 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0 P089806: MingeaProfesorul Baltazar este mare microbist. Ziua lui de naștere a fost sărbătorită cu câteva zile înainte de a pleca la Campionatul Mondial de Fotbal ?98 din Franța. Prietenii i-au făcut cadou un puzzle în formă de dodecaedru cu care să se joace în timpul meciurilor plictisitoare. Jucăria are 12 fețe egale, de forma unui pentagon, numerotate de la 1 la 12. Figura de mai jos reprezintă cele două semisfere ale dodecaedrului, cu numerotarea ce va fi utilizată în problemă. Semisferele sunt "lipite" una de alta, astfel încât fața numerotată cu 7 este vecină cu fețele 8, 12, 11, 2 și 6 (două fețe sunt vecine dacă au o muchie comună). De exemplu, muchiile a și b de pe semisfera din stânga, vor fi lipite de muchiile a și b de pe semisfera din dreapta, ca în figura de mai jos. În plus, sunt date 12 căpăcele în formă de pentagon, numerotate și ele de la 1 la 12. Muchiile căpăcelelor sunt marcate cu numere din mulțimea {0, 1, 2}. Fiecare dintre cel 12 căpăcele poate fi pus pe oricare dintre cele 12 fețe ale dodecaedrului, în orice poziție (dintre cele 5 obținute prin rotirea căpăcelului). Jocul constă în așezarea căpăcelelor pe fețele dodecaedrului, astfel încât două căpăcele vecine să aibă muchia comună marcată cu același număr. Ajutați-l pe Profesorul Baltazar să rezolve jocul! Date de intrare Fișierul de intrare BALL.IN conține 12 linii. Pentru orice i, 1<=i<=12, linia i descrie căpăcelul i prin specificarea celor cinci numere cu care sunt marcate muchiile sale, separate printr-un spațiu. Această secvență precizează marcajele muchiilor căpăcelului i, în ordinea acelor de ceasornic, începând cu o muchie oarecare, (numită în cele ce urmează muchia de referință i). Date de ieșire Fișierul de ieșire BALL.OUT va conține descrierea soluției jocului pe 12 linii conținând fiecare două numere întregi. Pentru orice i, 1<=i<=12, linia i va conține doi întregi t[i] și n[i] separați prin câte un singur spațiu, care identifică căpăcelul de pe fața i și poziția sa astfel: Pe fața i se pune căpăcelul t[i]. Căpăcelul poate fi pus pe fața i în cinci poziții diferite. Poziția exactă va fi specificată prin numărul n[i], care reprezintă numărul feței din dreptul muchiei de referință t[i] (privind din centrul feței i). Mai precis, muchia de referință a căpăcelului t[i] se așează pe dodecaedru astfel încât aceasta se suprapune cu muchia care desparte fața i de fața n[i]. Dacă jocul nu are soluție, în fișierul de ieșire va fi scris numai numărul -1. Exemple BALL.IN BALL.OUT 0 0 1 1 2 1 2 0 2 1 0 1 3 7 2 0 1 0 1 12 4 0 0 1 2 1 7 9 0 2 1 1 2 9 1 2 0 1 2 1 11 8 0 2 1 2 1 8 2 2 2 1 0 1 4 6 1 2 2 0 0 5 4 0 2 1 0 2 2 12 0 2 1 2 0 6 3 2 0 1 2 0 10 7 BALL.IN BALL.OUT 1 0 2 0 2 1 2 2 2 2 1 2 2 7 1 1 0 0 0 8 2 1 1 0 2 1 7 1 2 1 1 1 1 11 4 1 2 2 1 1 12 2 2 1 2 2 1 5 2 2 2 0 1 0 3 12 0 1 2 1 2 10 5 2 2 1 0 0 9 3 1 2 0 2 0 6 10 2 2 2 0 1 4 7 [cuprins] |