Concurs Paco 2001

Clasele III - IV:

Problema 1

Fie n un numar intreg (n<30.000) dat la tastatura.
a) Sa se determine cifra maxima ditre ultimele trei cifre ale numarului n.
b) sa se precizeze daca suma ultimelor trei cifre este numar par.
Exemplu:
pentru n=5243 se va afisa
a) 4
b) suma nu este numar par.
(Stelian Niculescu, Doru Popescu Anastasiu)

Problema 2:

Se dau de la tastatura cinci cifre. Sa se decida daca exista cifre care
se repeta.
In caz afirmativ sa se afiseze aceste cifre, iar in caz negativ sa se
afiseze
un mesaj.
Exemple:
pentru
2 1 0 0 2
raspunsul este
2 0
Pentru
1 2 3 6 5
raspunsul este
NU
(Adrian Atanasiu)

Clasele V-VI

Problema 1.

Fie un numar p (1<=p<=4) dat de la tastatura.
Sa se scrie pe ecran toate numerele N de p cifre cu proprietatile 
urmatoare:
1) N-1 si N+1 sunt numere prime;
2) Suma cifrelor lui N este tot un numar prim.
De exemplu, pentru p=2, numarul N=12 face parte din solutie, deoarece
N-1=11, N+1=13 sunt numere prime, iar suma cifrelor lui N este 1+2=3,
tot un numar prim.
Daca nu exista nici un numar N cu p cifre care sa verifice aceste
proprietati, se va da un mesaj.
(Adrian Atanasiu)

Problema 2:

O firma de constructii trebuie sa construiasca un profil sub forma de
triunghi format din bare de fier. Firma dispune de o bara lunga obtinuta
prin sudarea mai multor bare mai mici. Posibilitatea de formare a unui
triunghi consta in desfacerea a doua puncte de sudura, indoirea barelor
in aceste puncte si sudarea capetelor.
Exemplu:
Daca bara este formata din segmentele de lungimi A1A2=2, A2A3=1, A3A4=2,
A4A5=2.5, sudate in aceasta ordine, atunci se obtine un triunghi indoind
bara in punctele de sudura A3 si A4.
De la tastatura se citesc n numarul de puncte (n<=20) si cele n-1
lungimi ale barelor (in ordine de la stanga la dreapta). Pe ecran se vor
afisa doua numere care corespund indicilor punctelor unde se face
indoirea, daca problema are solutie; altfel sa va afisa un mesaj.
Pentru exemplul anterior (pentru care exista solutie), pe ecran se vor
afisa indicii
3 4
(Doru Popescu Anastasiu)

Clasele VII-VIII

Problema 1:

Se da de la tastatura un numar n (1<=n<=9). 
Sa se scrie pe ecran toate numerele de 2n cifre, cu proprietatile:
i) Fiecare cifra 1,2,..,n apare exact de doua ori.
ii) Pentru fiecare k=1,..,n, intre cele doua aparitii ale lui k se
gasesc exact k cifre.
Exemplu: 
pentru n=3 avem 
312132
231213
(Adrian Atanasiu)

Problema 2:

Un laborator accepta firmele interesate in utilizarea aparaturii proprii
doar doua ore pe zi, intr-un interval fix de zile. Fiecare firma trebuie
sa-si determine propriul orar pentru utilizarea laboratorului exact doua
ore pe zi. Aceste doua ore pot fi in prima perioada a zilei, in a doua
perioada sau in a treia perioada.
Orarul este fixat de la inceput pentru toata perioada celor N zile si
trebuie sa respecte anumite conditii.
Daca o firma selecteaza intr-o zi a treia perioada, atunci este obligata
ca in urmatoarea zi sa selecteze prima perioada; la fel, prima perioada
poate fi selectata numai daca in ziua precedenta a fost selectata
perioada a treia.
Pentru un numar de zile N dat (1<=N<=44), scrieti un program care
calculeaza cele M posibilitati de intocmire a orarului.
Exemplu:
Pentru N=4, cele M=5 orare posibile sunt

ZIUA | 1 2 3 4
--------|-----------------------------------
ORAR 1 | 2 2 2 2
ORAR 2 | 3 1 3 1
ORAR 3 | 2 3 1 2
ORAR 4 | 2 2 3 1
ORAR 5 | 3 1 2 2

Respectand conditiile, se observa ca nu se pot programa prima perioada
in prima zi si a treia perioada in ultima zi.
Numarul N se va introduce de la tastatura si numarul M se va afisa pe
ecran.
(Balcaniada de informatica, Albania, sept. 2001)

Clasele IX-X

Problema 1:

Un cunoscut cautator de comori a descoperit recent insemnarile unui fost
mare pirat. Conform acestor insemnari el ar putea gasi o comoara
ingropata de acesta in mijlocul Oceanului Indian.
Aceste insemnari contin n (1<=n<=50) fasii de uscat in forma
dreptunghiulara in interiorul carora ar putea fi ascunsa comoara. In
aceste insemnari mai este consemnat faptul ca aceasta comoara este
ingropata pe insula cu cea mai mare suprafata de uscat.
Sa se afle aria suprafetei de uscat a insulei pe care este ascunsa
comoara si aria insulei cu cea mai mare suprafata (pot exista si lacuri
in interiorul insulei).
Observatii:
- fasiile de uscat sunt date prin coordonatele colturilor din stanga-jos
si dreapta-sus;
- fasiile de uscat sunt paralele cu axele de coordonate;
- o insula este inconjurata doar de ocean;
- doar fasiile care sunt legate direct sau indirect de uscat apartin
aceleiasi insule;
- pe insule pot exista lacuri (care pot avea la randul lor insule
interioare), dar atentie ! comoara este ascunsa pe insula cu cea mai
mare suprafata de uscat (inclusiv cea a insulelor interioare din
lacurile ei).
Din fisierul 'comoara.in' se citesc datele de intrare sub forma
n - pe prima linie a fisierului (nuamrul de suprafete de forma
dreptunghiulara);
xi1 yi1 xi2 yi2 - pe rumatoarele n linii se dau coordonatele fasiilor de
pamant,
astfel: (xi1,yi1) sunt coordonatele coltului din stanga-jos,
(xi2,yi2) sunt coordonatele coltului din sreapta-sus.
Cele patru coordonate sunt numere reale cu doua zecimale exacte.
In fisierul 'comoara.out' se vor afisa:
- pe prima linie suprafata de uscat a insulei pe care este comoara, sau
numarul 0 in caz ca nu se poate stabili pe ce insula este ascunsa
comoara.
- pe a doua linie aria insulei cu cea mai mare suprafata.
Se vor afisa numere reale cu doua zecimale exacte.
Exemple:
comoara.in
4
0.00 0.00 2.00 1.00
1.00 0.00 2.00 3.00
3.00 2.00 4.00 3.00
5.00 5.00 7.00 7.00
comoara.out
0
4.00

comoara.in
5
0.00 0.00 100.00 1.00
99.00 0.00 100.00 100.00
0.00 0.00 1.00 100.00
0.00 99.00 100.00 100.00
10.00 10.00 40.00 40.00
comoara.out
1296.00
10000.00
Timp de executie: 1 secunda/test
(Bogdan Stroe)

Problema 2:

Se considera o tabla de sah de dimensiune nxn (3<=n<=25). Sa se aseze
dame pe aceasta tabla astfel incat orice dama ataca o alta dama si numai
una.
Care este numarul maxim de dame care se pot aseza pe tabla de sah ?
Fisierul de intarre este 'dame.in' si contine un singur numar n.
Fisierul de iesire, 'dame.out', are urmatoarea forma:
Pe prima linie numarul maxim k de dame care se pot aseza pe tabla.
Pe urmatoarele k linii sunt coordonatele (linie, coloana) ale pozitiei
fiecareia din cele k dame care formeaza o solutie a problemeie.
k
i1 j1
i1 j2
.......
ik jk
Exemplu:
Pentru n=3, o solutie posibila este
2
1 1
1 2
Timp de executie: 1 secunda/test
(Adrian Atanasiu)

Clasele XI-XII

Problema 1:
Dupa incheierea Marelui Premiu al palatului Copiilor, cei p copii
participanti (1<=p<=100.000.000) viziteaza un parc de distractii si
doresc sa traverseze un pod. Pentru aceasta ei trebuie sa respecte
anumite reguli:
Podul, lung de N metri (5<=N<=25) si lat de 1 metru, este pavat cu un
sir de N dale patrate de latura 1 metru, luminate electric. Fiecare dala
contine un bec rosu si un bec verde, dintre care exact unul este aprins.
Astfel, dala respectia va fi colorata cu ajutorul becului, fie in rosu,
fie in verde. 
Cel mult 5 dale sunt colorate in verde.
Fiecare copil incepe traversarea deplasandu-se din capul podului pe
patratul 1.
O astfel de deplasare dureaza o secunda. Dupa ce copilul ajunge intr-un
patrat X, culoarea acestuia se transforma in culoarea patratului N si
reciproc (deci, daca patratele X si N erau colorate diferit, culorile
lor se schimba; in caz contrar ele raman aceleasi).
Un copil aflat intr-un patrat X va avansa in patratul X+1 daca patratul
X este colorat in rosu; in caz contrar el avanseaza in patratul X+2
(printr-o saritura care nu atinge patratul X+1). Orice astfel de
deplasare (de unul sau doua patrate) dureaza o secunda (inclusiv
deplasarile care duc la iesirea de pe pod).
Copilul C+1 va incepe traversarea doar dupa ce copilul C a terminat-o,
pentru orice C (1<=C<=p).
Se cere determinarea timpului total in care copiii vor termina de
traversat podul.
Intrare:
pod.in
N P
X1 X2 .. XN - culorile initiale ale celor N dale (1 pentru rosu, 2
pentru verde)
Iesire:
pod.out
T - timpul necesar traversarii
Exemplu:
pod.in
6 2
1 2 2 1 1 1
pod.out
11
Timp de executie: 1 secunda/test
(Mihai Stroe)

Problema 2:

Intr-un mare oras din Romania candideaza pentru postul de primar n
(1<=n<=99) personalitati. Se stie ca orasul are n posturi de radio
(exact cati candidati la primarie sunt) si ca fiecare din ele sprijina
un anumit candidat (nu exista doua posturi de radio care sa sprijine
acelasi candidat). Pentru a-si face cunoscut programul electoral,
fiecare candidat participa singur la aceeasi ora (cu ceilalti
candidati) la o emisiune electorala difuzata de un post de radio diferit
de cel pe care il sprijina.
Se cere sa se determine numarul de modalitati de planificare a
candidatilor la emisiunile posturilor de radio difuzate la o anumita
ora.
Date de intrare:
fisierul text candidat.in contine pe prima linie numarul n.
Date de iesire:
Fisierul text candidat.out contine pe prima linie numarul de modalitati.
Exemplu:
candidat.in
3
candidat.out
2
Timp de executie: 1 secunda/test
(Doru Popescu Anastasiu)