Încercați-vă puterile
PROBLEME propuse pentru rezolvareÎn perioada 14-30 aprilie s-a desfășurat la Liceul de Informatică din Cluj tabăra de antrenament a lotului lărgit (informatică) având ca scop pregătirea și selecționarea echipelor participante la CEOI'98 și Balcaniada de Informatică. P049801: Funcții surjectiveproblemă propusă de prof. Doina Rancea, Liceul "Tiberiu Popoviciu", Cluj-Napoca Enunț: Să se determine numărul funcțiilor surjective f:A?B, unde A și B sunt două mulțimi formate din litere mici ale alfabetului. Date de intrare: Pe prima linie a fișierului de intrare FUNCTII.IN sunt scrise literele aparținând mulțimii A, iar pe a doua linie literele aparținând mulțimii B. Date de ieșire: În fișierul de ieșire FUNCTII.OUT se va scrie numărul funcțiilor surjective f:A?B. Exemplu: FUNCTII.IN FUNCTII.OUT ab 1 x P049802: Fractal problemă propusă de Cătălin Frâncu, student,Universitatea Politehnică, București Enunț: Se consideră în plan mulțimea A0=[0,1)Ž[0,1). Remarcați că A0 este un pătrat de latură 1 care își conține latura din stânga și pe cea de jos, dar nu și le conține pe cea din dreapta și pe cea de sus. Mulțimea A0 se împarte în 3Ž3 pătrate egale de latură 1/3. Pătratele formate au aceeași proprietate cu A0, adică își conțin laturile din stânga și de jos, dar nu și pe cea din dreapta și pe cea de sus. Numerotăm aceste pătrate în ordinea indicată de figura 1: n Pătrate care nu fac parte din mulțimea Az o Pătrate care fac parte din mulțimea Az Așadar P1=[0,1/3)Ž[0,1/3), P2=[1/3,2/3)Ž[0,1/3) etc. Din mulțimea A0 se elimină un set prestabilit de pătrate (indicat printr-o submulțime a mulțimii {1,2,3,4,5,6, 7,8,9,10}), obținând astfel o mulțime A1. Pentru fiecare pătrat de latură 1/3 care a rămas în mulțimea A1, se aplică același procedeu: se împarte pătratul în 3Ž3 pătrățele cu latura de trei ori mai mică (1/9); aceste pătrățele se numerotează în aceeași ordine, apoi același set prestabilit de pătrate se elimină. În felul acesta se obține mulțimea A2. Figura 2 prezintă mulțimea A2 în cazul în care setul de pătrate eliminate la fiecare pas este {1,4,6,8,10}. Operația de împărțire și eliminare se face la infinit, păstrând însă mereu același set de indici de pătrate eliminate. Notăm mulțimea rămasă după repetarea de o infinitate de ori a eliminării cu AĄ. Observați că mulțimea AĄ nu este vidă. De exemplu, dacă pătratul numerotat cu 1 nu se află în setul de pătrate eliminate la fiecare pas, atunci punctul de coordonate (0,0) se află în mulțimea AĄ. Se dau patru numere naturale, PX, QX, PY, QY, astfel încât 0ŁPX<QXŁ1000 și 0ŁPY<QYŁ1000. Aceste numere reprezintă un punct de coordonate raționale din mulțimea A0, M(PX/QX,PY/QY). Să se determine dacă punctul M aparține sau nu mulțimii AĄ. Date de intrare: Fișierul text FRACTAL.IN conține cel mult cinci seturi de date de test de forma: PX QX // Coordonata X a punctului M PY QY // Coordonata Y a punctului M NE // Numărul pătratelor eliminate (0<NE<9) E1 E2 ? ENE // Indicii pătratelor eliminate (indicii sunt în ordine strict crescătoare) Date de ieșire: Pentru fiecare set de date de intrare se va afișa pe ecran o linie conținând mesajul 'DA' sau 'NU', după cum punctul M aparține sau nu mulțimii AĄ. Pe ecran nu se vor afișa alte date de ieșire! Exemplu: FRACTAL.IN Răspunsul pe ecran: 1 2 DA 1 2 NU 8 1 2 3 4 6 7 8 9 1 3 2 3 1 1 P049803: Cuvinte încrucișateProblemă propusă de prof. Ion Maxim, Liceul de Informatică, Suceava Enunț: Într-un careu pătratic de cuvinte încrucișate de dimensiune n sunt plasate p puncte negre. Din fișierul de intrare CAREU.IN se citesc pozițiile (li ci) ale celor p puncte negre și cuvinte de lungime cel mult n formate numai din literele mari ale alfabetului englez. Se cere să se completeze careul astfel încât toate cuvintele date să se regăsească în careu (pe orizontală sau pe verticală), eventual separate prin puncte negre. Într-un careu, numerotarea liniilor și coloanelor se face de la 1 la n începând din colțul din stânga-sus, în jos și spre dreapta. Date de intrare: Pe prima linie a fișierului de intrare CAREU.IN sunt scrise cele două numere naturale n (3ŁnŁ10) și p (0ŁpŁ25), despărțite printr-un spațiu. Pe următoarele p linii sunt scrise perechi de numere naturale, reprezentând pozițiile punctelor negre. În următoarele linii ale fișierului sunt cuvintele care trebuie plasate în careu. Date de ieșire: Fișierul de ieșire CAREU.OUT va conține n linii, fiecare conținând n caractere, reprezentând careul completat. Punctele negre se reprezintă prin caracterul '@'. În calculul lungimii unei linii sau coloane se includ și punctele negre, dacă acestea există pe acea linie sau coloană. Între caracterele din fișierul de ieșire nu există spații. Exemplu: CAREU.IN CAREU.OUT 4 2 C@RA 1 2 ANOD 4 3 SALA AS AS@S ROL C RA S CASA SALA ADAS NAS ANOD P049804: Comerț interplanetarProblemă propusă de prof. Maria Niță, Liceul "Emanoil Gojdu", Oradea Enunț: Datorită revoluției științei și tehnicii, în anul 8991, a devenit posibil comerțul dintre Pământ și cele mai îndepărtate galaxii din Univers. Pământul dorește să importe produse din câteva din galaxiile sectorului Napoca. Planetele cuprinse în aceste galaxii exportă produse valoroase, de care omenirea are nevoie. Rapoartele preliminare au evidențiat următoarele date: - numărul de planete din fiecare galaxie este cuprins între unu și 26. Planetele sunt identificate printr-o majusculă. - fiecare planetă este specializată în producerea și exportul unui singur produs. Planete distincte exportă produse distincte. - unele perechi de planete sunt conectate prin linii de transport hiperspațiale. Dacă planetele A și B sunt conectate, ele pot face comerț fără taxe. Dacă planeta C este conectată cu planeta B, dar nu și cu planeta A, atunci A și C pot face comerț prin intermediul lui B, dar B își va reține 5% din întregul transport ca și taxă. (Deci A va primi doar 95% din ce a trimis C, iar C va primi doar 95% din ce a trimis A). În general, oricare două planete pot face comerț, cu condiția de a fi conectate printr-un set de linii de transport, dar fiecare planetă intermediară de pe parcursul drumului își va reține 5% din întregul transport (ceea ce nu este neapărat echivalent cu 5% din cantitatea originală de produs). - cel puțin o planetă dintr-o galaxie e dispusă să deschidă o linie de transport care să fie conectată cu Pământul. O astfel de linie cu Pământul, este identică cu oricare linie din galaxie, în materie de comerț. De exemplu, dacă o planetă K deschide o linie pentru a se conecta cu Pământul, atunci planeta K va face comerț fără taxe cu Pământul, sau poate face comerț cu orice planetă conectată cu K, cu condiția să plătească taxele planetelor intermediare. Există o standardizare prin care s-a asociat o valoare relativă (un număr real pozitiv, mai mic decât 10) produsului de bază al fiecărei planete. Cu cât numărul este mai mare, cu atât este produsul mai valoros. Mai multe produse de valoare pot fi revândute cu un profit mai mare. Să se determine planeta care are exportul cel mai mare spre Pământ, atunci când taxele sunt luate în considerare. Date de intrare: Fișierul de intrare IMPORT.IN, conține descrierea uneia sau mai multor galaxii. Fiecare descriere a unei galaxii începe cu o linie care conține un număr întreg N ce reprezintă numărul planetelor din galaxie. Următoarele N linii conțin descrierea fiecărei planete sub următoarea formă: O literă (pentru identificarea planetei), un spațiu, valoarea relativă a exportului planetei, sub forma d.dd, un spațiu, un string care conține litere și/sau caracterul '*'; o literă indică o linie de transport către acea planetă, și '*' indică o linie de transport către Pământ. Date de ieșire: În fișierul de ieșire, IMPORT.OUT, pentru fiecare descriere a unei galaxii, trebuie listată o singură linie de forma "Import din P", unde P este litera planetei cu cel mai mare export, după ce taxele de transport au fost luate în considerare. (Dacă mai multe planete au aceeași valoare de export, atunci se va lista planeta care are prioritate alfabetică). Exemplu: IMPORT.IN IMPORT.OUT 1 Import din F F 0.81 * Import din A 5 Import din A E 0.01 *A D 0.01 A* C 0.01 *A A 1.00 EDCB B 0.01 A* 10 S 2.23 Q* A 9.76 C K 5.88 MI E 7.54 GC M 5.01 OK G 7.43 IE I 6.09 KG C 8.42 EA O 4.55 QM Q 3.21 SO P049805: Aeroportproblemă propusă de asistent Simona Motogna, Universitatea Babeș-Bolyai, Cluj-Napoca și prof. Clara Ionescu, Liceul "Tiberiu Popoviciu", Cluj-Napoca Enunț: Pe un aeroport de tranzit sunt n terminale și m porți pe fiecare terminal. Călătorii aterizează cu un avion și vor decola - în scopul de a ajunge la destinație - cu un alt avion. Aterizarea are loc la un anumit terminal, la o anumită poartă, iar decolarea la altă poartă, eventual de pe alt terminal. În consecință, toți călătorii au de traversat un drum în interiorul aeroportului de la poarta de aterizare la poarta de decolare. Distanțele dintre porți, terminale, respectiv prima poartă de pe terminal la coridorul central, sunt identice (x=1). Realizați o planificare a aterizărilor și decolărilor astfel încât suma lungimilor drumurilor pe care o vor străbate călătorii în aeroport să fie minimă. Atenție: un avion aterizat nu poate fi programat pentru decolare! Date de intrare: Pe prima linie a fișierului AERO.IN se află două numere întregi n și m, reprezentând numărul de terminale, respectiv numărul de porți de pe fiecare terminal (1<=n<=10, 1<=m<=10). Pe următoarele linii se află date cu privire la călătoriile care trebuie planificate sub forma: loc1 loc2 nr_pasageri unde loc1 și loc2 sunt șiruri de caractere având cel mult 30 de caractere, reprezentând denumirile localităților, nr_pasageri este un număr întreg (1Łnr_pasageriŁ100). Prima localitate reprezintă locul de unde vin călătorii, cea de a doua reprezintă localitatea unde se duc. Datele sunt despărțite printr-un spațiu. Date de ieșire: Rezultatele se vor scrie în fișierul text AERO.OUT care va conține pe prima linie un număr întreg, reprezentând suma lungimilor drumurilor pe care o vor parcurge călătorii. Pe liniile care urmează se vor scrie date cu privire la planificarea zborurilor: localitate poarta Datele vor fi despărțite prin câte un spațiu. Exemplu: AERO.IN AERO.OUT 2 4 75 Bucuresti Washington 27 Bucuresti 2 Budapesta New_York 13 Washington 3 Bucuresti Chicago 30 Budapesta 5 Praga Washington 5 New_York 6 Chicago 1 Praga 4 P049806: Asemănareproblemă propusă de lector Vasile Prejmerean, Universitatea Babeș-Bolyai, Cluj-Napoca Enunț: Se dau poligoanele P=(P1,P2,...,Pn) și Q=(Q1,Q2,... ,Qn) situate în plan, prin coordonatele reale ale vârfurilor succesive Pi(xi,yi), și Qj(,), i,jÎ{1,...,n} (3ŁnŁ100). Se cere sa se determine daca cele doua poligoane P și Q sunt asemenea, caz în care se va specifica succesiunea vârfurilor din Q corespunzătoare vârfurilor P1,P2,...,Pn din P. Date de intrare: Fișierul de intrare POL.IN conține: n - numărul de vârfuri x1 y1 - coordonatele primului vârf al poligonului P ... xn yn - coordonatele vârfului n al poligonului P , - coordonatele primului vârf al poligonului Q ... , - coordonatele vârfului n al poligonului Q Date de ieșire: Fișierul de ieșire POL.OUT va avea forma: i1 i2 . . . in - numerele de ordine ale vârfurilor din Q sau 0 - dacă cele două poligoane nu sunt asemenea Exemple: POL.IN 5 0 0 0 4 4 4 6 2 4 0 0 0 2 2 0 4 4 4 4 0 POL.OUT 0 POL.IN 5 0 0 0 4 2 6 4 4 4 0 0 1 0 3 2 3 2 1 1 0 POL.OUT 3 4 5 1 2 sau 2 1 5 4 3 [cuprins] |