Încercați-vă puterile! PROBLEME propuse pentru REZOLVAREVă prezentăm în continuare enunțurile celor nouă probleme pe care au încercat să le rezolve membrii Lotului Național de Informatică în cadrul barajelor de selecție pentru Olimpiada Internațională de Informatică.
P079901: Arborelect. univ. Clara Ionescu, Univ. "Babeș Bolyai", Cluj Se consideră un arbore binar de căutare A având n noduri conținând cheile 1, 2,..., n. O permutare p = [p1,...,pn] a numerelor întregi 1, 2,..., n se numește consistentă cu arborele A dacă arborele de căutare poate fi construit pornind de la arborele vid prin inserarea numerelor întregi p1, p2,...,pn în această ordine. Să se determine numărul permutărilor mulțimii {1, 2,..., n} care sunt consistente cu un arbore dat. (Altfel spus: câte secvențe distincte de chei există pentru ca arborii binari de căutare - obținuți prin inserarea cheilor în ordinea dată - să fie identici cu arborele dat?)
Exemplu Arborele din figură are exact 8 permutări consistente. De exemplu, permutările 2, 1, 4, 3, 5 și 2, 4, 5, 3, 1 sunt consistente cu arborele din figura:
Inserând elemente consecutive din permutarea 2, 4, 5, 3, 1, se obține arborele dat:
Date de intrare Pe prima linie a fișierului ARBORE.IN este scris un singur număr natural n (1ŁnŁ100), reprezentând numărul de noduri din arbore. Pe cea de a doua linie se află n numere naturale distincte, separate printr-un singur spațiu. Aceste numere reprezintă cheile asociate arborelui dat în preordine. Primul număr este cheia asociată rădăcinii; este urmată de cheile asociate subarborelui stâng, și de cheile subarborelui drept (de asemenea în preordine).
Date de ieșire Rezultatul se va scrie în fișierul ARBORE.OUT și trebuie să reprezinte numărul permutărilor consistente cu arborele din fișierul de intrare. Atenție: Acest număr poate avea până la 200 de cifre.
Exemplu ARBORE.IN ARBORE.OUT 5 8 2 1 4 3 5
Explicație Cele 8 permutări consistente cu arborele dat sunt: 1) 2 1 4 3 5; 2) 2 1 4 5 3; 3) 2 4 1 3 5; 4) 2 4 3 1 5; 5) 2 4 5 3 1; 6) 2 1 4 5 3; 7) 2 4 1 5 3; 8) 2 4 3 5 1.
P079902: La cinemaCristian Cadar, student Univ. Politehnică București Un grup de n prieteni se duc la cinema. Fiecare dintre ei și-a cumpărat bilet separat, însă conform înțelegerii inițiale toți și-au luat bilete în rândul 17. Ajungând după începutul filmului, ei se așează la întâmplare pe acest rând. Fiecare dintre cei n prieteni consideră că locul de pe biletul său este cel mai bun, așa că fiecare dorește să ajungă pe locul său. Pentru a nu deranja prea tare restul spectatorilor ei se hotărăsc ca în fiecare minut, mai multe perechi de persoane să-și schimbe locurile între ele. La fiecare minut, numărul de schimbări de locuri poate fi oricât de mare, însă o persoană nu poate participa decât la o singură astfel de schimbare. Aflați numărul minim de minute necesare pentru ca fiecare persoană să ajungă pe locul său. Pentru simplificare, considerăm că persoana 1 are biletul cu locul 1, persoana 2 are biletul cu locul 2, și așa mai departe, persoana n are biletul cu locul n.
Date de intrare Datele de intrare se citesc din fișierul CINEMA.IN. Pe prima linie este scris numărul n (nŁ1000) de prieteni care merg la cinema. Pe fiecare din următoarele n linii se află câte un număr, reprezentând locul pe care prietenii s-au așezat inițial.
Date de ieșire Datele de ieșire se scriu în fișierul CINEMA.OUT. Prima linie a acestui fișier va conține numărul minim M de minute necesare pentru ca fiecare persoană să ajungă pe locul său. Urmează M blocuri cu următoarea structură: · prima linie a blocului conține numărul R de mutări care sunt executate la minutul respectiv; · următoarele R linii conțin perechi de numere (i j), separate printr-un spațiu, având semnificația: în minutul respectiv, persoana i își schimbă locul cu persoana j.
Exemplu CINEMA.IN CINEMA.OUT 3 2 3 1 1 1 2 2 1 3 2 3
P079903: D'Artagnanprof. Dana Lica, Liceul "I. L. Caragiale", Ploiești Când D'Artagnan avea 18 ani s-a hotărât să se ducă la Paris și să devină mușchetar. Singura modalitate de a călători era de a folosi șoselele regale care legau orașele. Fiecare șosea care lega două orașe avea (la ambele capete ale sale) porți care permiteau accesul în orașele respective. Fiecare astfel de poartă era păzită fie de mușchetarii regelui, fie de gardienii cardinalului. Rolul acestora era să noteze numele persoanelor care intrau în oraș. Din această cauză, dacă cineva intra într-un oraș pe o poartă păzită de mușchetari, era obligat să părăsească orașul pe o poartă păzită tot de mușchetari. Dacă nu ar fi respectat regula, la ieșirea pe o poartă păzită de gardieni ar fi fost arestat, deoarece nu figura pe lista persoanelor care au primit, din partea lor, permisiunea de intrare în oraș; dacă o persoană intra pe o poartă păzită de gardieni, era obligată să părăsească orașul tot pe o poartă păzită de gardieni.
Pentru ca situația lui D'Artagnan să fie și mai complicată, trebuie știut faptul că între mușchetari și gardieni existau mari neînțelegeri. Din acest motiv orice șosea dintre două orașe avea la un capăt o poartă păzită de gardieni, iar la celălalt capăt o poartă păzită de mușchetari. D'Artagnan a stat ore întregi în fața hărții pentru a căuta cel mai scurt drum pentru a ajunge la Paris. Evident, el putea părăsi orașul în care locuia, prin orice poartă. În Franța existau n orașe numerotate cu numere de la 1 la n., Parisul numerotat cu 1, iar orașul lui D'Artagnan cu n. Existau m șosele care legau câte două orașe și pe care se putea circula în ambele sensuri. Pentru fiecare șosea se cunosc: numerele de ordine ale orașelor pe care le unește, lungimea acesteia și tipul păzitorilor de la poarta orașului de plecare (evident la celălalt capăt se vor afla opozanții). Scrieți un program care determină lungimea minimă a unui drum care respectă condițiile de deplasare descrise, precum și orașele pe care le străbate.
Date de intrare Pe prima linie în fișierul text DART.IN este scris numărul n (1ŁnŁ50) de orașe. Pe a doua linie este scris numărul m (1ŁmŁ1000) de șosele. Pe următoarele m linii sunt descrise șosele în formatul i j L t, semnificând o șosea între orașele i și j de lungime L cu poarta păzită de t la ieșirea din orașul i. Datele sunt separate printr-un singur spațiu. i, j și L sunt numere naturale, iar t este un caracter: M pentru mușchetari, G pentru gardieni.
Date de ieșire Pe prima linie a fișierului DART.OUT se va scrie lungimea minimă a drumului determinat. Pe cea de-a doua linie se vor scrie numerele de ordine ale orașelor în ordinea în care trebuie parcurse de D'Artagnan. Numerele vor fi despărțite printr-un singur spațiu. În cazul în care problema admite mai multe drumuri minimale în fișier se va scrie un singur drum, iar în cazul în care problema nu admite soluții, fișierul de ieșire va conține mesajul: Fara solutie
Exemplu DART.IN DART.OUT 5 5 7 5 4 1 1 2 3 M 1 4 4 G 1 3 2 G 2 5 3 G 2 4 10 G 5 4 1 G 4 3 1 M
P079904: Evadatullect. univ. Clara Ionescu, Univ. "Babeș Bolyai", Cluj Un prizonier încearcă să evadeze din închisoare. El iese prin sistemul de canalizare format din M tuneluri și N intersecții de tuneluri. Fiecare tunel leagă două intersecții diferite și nu există două tuneluri diferite între aceeași pereche de intersecții. Prizonierul se găsește inițial în intersecția numărul 1 și trebuie să ajungă la intersecția numărul N unde se găsește ieșirea. Prizonierul are o bilă grea legată de picior printr-un lanț de lungime L. Pentru a reduce zgomotul, lanțul trebuie să fie în permanență întins. Bila se târăște pe măsură ce prizonierul înaintează și dacă lanțul trece prin (intră și iese) patru sau mai multe intersecții simultan frecarea lanțului este atât de mare încât prizonierul nu mai poate înainta. În plus, prizonierul nu poate face stânga împrejur în interiorul unui tunel; pe de altă parte în momentul în care el intră într-o intersecție, nu poate pleca de acolo prin tunelul prin care a intrat. Inițial, bila se găsește în intersecția numărul 2. Există un tunel de lungime exact L care leagă intersecțiile 1 și 2, lanțul găsindu-se inițial întins de-a lungul acestui tunel. Scrieți un program care stabilește dacă prizonierul poate evada (sau nu) din închisoare. În caz afirmativ, determinați lungimea celui mai scurt drum de evadare.
Date de intrare Pe prima linie a fișierului EVADAT.IN se află trei numere naturale: N (2<NŁ40) reprezentând numărul intersecțiilor, M (1ŁMŁ780) reprezentând numărul tunelurilor, și L (0<LŁ30000) reprezentând lungimea lanțului. Pe următoarele M linii sunt descrise tunelurile. Fiecare linie conține trei numere naturale: a, b (0<a,bŁN) și d (0<dŁ30000) semnificând faptul că există un tunel de lungime d între intersecțiile a și b.
Date de ieșire Fișierul EVADAT.OUT va conține un singur număr care reprezintă lungimea celui mai scurt drum de evadare (între intersecțiile 1 și N). Dacă nu există un asemenea drum, în fișier se va scrie numărul -1.
Exemplu EVADAT.IN EVADAT.OUT 8 8 10 22 1 2 10 1 3 2 3 4 2 4 7 2 4 5 6 5 6 4 6 4 4 7 8 2
P079905: FireValentin Gheorghiță, student Univ. Politehnică, București Un electrician folosește n (2<nŁ500) fire pentru cablarea casei din pod până în beci. Capetele firelor sunt numerotate de la 1 la n atât în pod cât și în beci. Deoarece electricianul este o persoană extrem de împrăștiată, un fir având capătul numerotat cu i în pod, nu are întotdeauna capătul din beci numerotat cu i. Electricianul poate urca în pod sau poate coborî în beci, inițial aflându-se în pod. Sarcina voastră este de a-l ajuta pe electrician să găsească corespondența capetelor din pod cu cele din beci, executând un număr minim de urcări și coborâri. În scopul găsirii capetelor corespunzătoare, electricianul (aflat în pod sau în beci) fie conectează două fire (dacă firul x este conectat cu firul y și firul y este conectat cu firul z, atunci firul x este conectat automat cu firul z), fie verifică dacă două fire sunt conectate la capătul opus. Aveți la dispoziție un unit (fire.PAS) care va conține următoarele funcții: Procedure Start procedură de inițializare; orice altă funcție sau procedură va fi apelată numai după apelul procedurii Start; Function Number:Integer funcția care returnează numărul de fire; Procedure Connect(x,y:Integer) procedura care permite conectarea firului x cu firul y;
Function IsConnect(x,y:Integer):Boolean; funcția care verifică dacă firele x și y sunt conectate la capătul opus;
Procedure Clear procedura care permite decuplarea tuturor legăturilor existente în locul în care se află electricianul (pod sau beci); Procedure GoUp procedura care produce mutarea electricianului din beci în pod; Procedure GoDown procedura care produce mutarea electricianului din pod în beci;
Procedure Solution(x,y:Integer) procedura prin care specificați că firul x aflat în pod corespunde firului y din beci; această procedură trebuie apelată pentru toate firele;
Procedure Stop procedura care semnalează finalul rezolvării; programul vostru nu va fi punctat decât după apelarea acestei proceduri.
Exemplul pe care vi-l oferă unit-ul anterior este cel din figură:
P079906: Ora de gimnasticăCristian Cadar, student Univ. Politehnică București După ora de germană urmează ora de gimnastică!!! Cei n elevi prezenți la oră sunt așezați în cerc, unii stau în picioare, alții sunt așezați în genunchi. Ei poartă tricouri numerotate de la 1 la n. Exercițiul presupune realizarea de genoflexiuni în felul următor: într-o aceeași unitate de timp orice elev își va schimba poziția (sau nu) în funcție de poziția sa, de poziția celui aflat cu două poziții în stânga sa și în funcție de poziția colegului aflat imediat în dreapta sa. Schimbările corespunzătoare unei unități de timp au loc simultan. Copiii se identifică prin numărul lor de ordine în cerc, număr desenat și pe tricoul lor. (În dreapta copilului având numărul i pe tricou, urmează cel cu numărul i+1, excepție făcând copilul cu numărul de ordine n, în dreapta căruia se află copilul cu numărul de ordine 1.) Scrieți un program care determină poziția fiecărui elev după un număr cunoscut k de unități de timp.
Date de intrare Pe prima linie a fișierului GYM.IN se află numărul k (0ŁkŁ2.000.000.000) reprezentând numărul unităților de timp. Pe cea de-a doua linie se află o secvență de atâtea caractere câți copii participă la exercițiu (5ŁnŁ10000). Al i-lea caracter indică poziția celui de-al i-lea elev ('J' pentru jos și 'S' pentru sus). Pe fiecare din următoarele linii se află câte patru caractere cu următoarea semnificație: dacă un anumit elev se află în starea indicată de primul caracter de pe linie, colegul aflat cu două poziții în stânga sa se află în starea indicată de cel de-al doilea caracter de pe linie și colegul din dreapta sa se află în starea indicată de cel de-al treilea caracter de pe linie, atunci elevul respectiv își va schimba poziția în starea indicată de cel de-al patrulea caracter de pe linie.
Date de ieșire Fișierul de ieșire GYM.OUT conține n caractere semnificând starea în care se află cei n copii după k unități de timp.
Exemplu GYM.IN GYM.OUT 2 SJJSJ JSJJS JJJJ JJSJ JSJJ JSSS SJJJ SJSS SSJS SSSJ
P079907: OrigamiRadu Lupșa, preparator Univ. "Babeș Bolyai", Cluj Origami este o veche artă japoneză ce constă în îndoirea unei simple foi de hârtie dreptunghiulare și obținerea unor forme de animale, flori, sau alte figuri. În zilele noastre, un amator de origami și de calculatoare a construit o mașină capabilă să fabrice origami, executând în acest scop o secvență de instrucțiuni simple. Mașina constă dintr-o masă pe care se plasează inițial o coală pătrată de hârtie și un dispozitiv de îndoire. Colțul stânga jos al hârtiei are coordonatele (0,0), iar colțul dreapta sus are coordonatele (100,100). Mașina primește o secvență de instrucțiuni; fiecare instrucțiune descrie câte o îndoire. Fiecare instrucțiune constă din coordonatele a două puncte, p1 și p2. Îndoirea se face în lungul liniei ce unește p1 și p2, partea din dreapta liniei (considerate dinspre p1 către p2) îndoindu-se peste partea din stânga. Una din problemele amatorului nostru de origami este aceea de a găsi în final un loc unde să perforeze origami-ul rezultat în scopul agățării lui într-un cui. În locul ales, grosimea origami-ului, adică numărul de pliuri suprapuse, trebuie să fie nici prea mică - caz în care origami-ul riscă să se rupă sub greutatea proprie -, nici prea mare - caz în care perforația este dificil de executat. Amatorul nostru alege deci o secvență de puncte și vrea să afle care este grosimea origami-ului în fiecare dintre aceste puncte. Scrieți un program care, plecând de la instrucțiunile de confecționare și de la coordonatele punctelor alese, calculează grosimea origami-ului în punctele date.
Date de intrare Datele se vor citi din fișierul ORIGAMI.IN. Prima linie a acestui fișier conține numărul n (0ŁnŁ8) de îndoiri. Fiecare din următoarele n linii conține coordonatele x1, y1, x2, y2 ale punctelor p1, respectiv p2. Pe următoarea linie se găsește numărul m (1ŁmŁ50) de puncte de test (candidate pentru puncte de perforație). Pe fiecare din următoarele m linii se găsesc coordonatele punctelor de test. Notă: coordonatele punctelor sunt numere reale; distanța dintre un punct de test și marginea hârtiei, respectiv față de o îndoitură nu este mai mică de 0.01.
Date de ieșire Ieșirea se va face în fișierul ORIGAMI.OUT. Pentru fiecare punct de test se va scrie o linie pe care se va afișa grosimea origami-ului în acel punct.
Exemplu ORIGAMI.IN ORIGAMI.OUT 2 4 -0.5 -0.5 1 1 2 1 75 0 75 0 6 2 10 60.1 0 80 60 2 40 30 10 20 50 40 20 40
P079908: PermanentMihai Scorțaru, student Univ. Tehnică Cluj Permanentul unei matrice este definit într-o manieră asemănătoare definiției determinantului; singura diferență constă în faptul că termenii care apar cu semnul - în dezvoltarea determinantului, vor apărea cu semnul + în dezvoltarea permanentului. În concluzie, formula pentru calculul permanentului unei matrice este:
unde S este mulțimea permutărilor mulțimii {1, 2,..., n}. Se consideră matricea pătratică A de dimensiune n definită prin aij=i*j. Să se determine numărul de cifre (în baza 10) al permanentului acestei matrice.
Date de intrare Fișierul de intrare PERM.IN conține numărul natural n (1ŁnŁ24.572.457).
Date de ieșire Fișierul de ieșire PERM.OUT va conține, pe o linie, numărul de cifre al permanentului matricei A.
Exemplu PERM.IN PERM.OUT 2 1
Explicație Pentru n=2 matricea A este: , iar permanentul ei este perm(A)=1*4+2*2=8, deci numărul de cifre este 1.
P079909: PitagoraMihai Scorțaru, student Univ. Tehnică Cluj Se consideră un număr natural a din intervalul [1,32457]. Să se găsească toate perechile de numere naturale b și c având proprietatea a<b<c pentru care există un triunghi dreptunghic care are laturi de lungimi a, b, c.
Date de intrare Fișierul de intrare PITAGORA.IN conține numărul natural a (1ŁaŁ32457).
Date de ieșire Fișierul de ieșire PITAGORA.OUT va conține, pe câte o linie, perechile de numere naturale b și c separate printr-un singur spațiu. Există întotdeauna cel puțin o astfel de pereche.
Exemple PITAGORA.IN PITAGORA.OUT 3 4 5 PITAGORA.IN PITAGORA.OUT 9 12 15 40 41 [cuprins] |