SECTIUNEA PROGRAMARE LICEU
SECTIUNEA DE PROGRAMARE A CONCURSULUI PRIMAVARA MICILOR PROGRAMATORI
SUBIECTE:
CLASELE IX-XII
Subiectul I – Regi
profesor propunător Ilea Lucian Liceul “Emil Racoviţă” Cluj Napoca
În această problemă se consideră că o tablă de şah poate fi reprezentată cu ajutorul unei matrici pătratice de ordin n. Matricea conţine valori 0 sau 1. Valorile 0 corespund câmpurilor libere iar valorile 1 corespund câmpurilor ocupate. Spre deosebire de jocul de şah, unde regele poate să mute în oricare din cele opt câmpuri vecine, de data aceasta vor fi considerate ca fiind mutări posibile doar acelea în care numărul de ordine al liniei este strict mai mare decât al liniei curente. Sunt posibile, aşadar, maxim trei mutări ale unui rege situat în poziţia (i,j) şi anume spre câmpurile (i+1,j-1), (i+1,j), (i+1,j+1). Nu vor fi considerate situaţiile în care regele ajunge în afara tablei sau într-o poziţie ocupată.
Se cere să se scrie un program care determină numărul de trasee diferite pe care un rege care porneşte de oriunde din linia 1 ajunge oriunde în linia n. Deoarece rezultatul poate să fie foarte mare, se cere să se afişeze doar restul împărţirii sale la 10000.
Datele de intrare se citesc din fişierul regi.in.
Datele de ieşire (un număr natural reprezentând restul împărţirii numărului de trasee la 10000) se vor scrie în fişierul regi.out.
Restricţii şi precizări
- 1≤n≤50
- câmpurile ocupate se pot găsi oriunde, inclusiv în prima şi ultima linie
- datele de intrare se consideră corecte
Exemple
regi.in
3
0 0 0
1 0 1
0 0 0
regi.out 9
Explicatii: Exista 3 trasee cu pornire din (1,1), 3 trasee cu pornire din (1,2), 3 trasee cu pornire din (3,3). (3+3+3) mod 10000 = 9
regi.in
4
0 0 0 1
1 0 1 0
0 0 0 1
1 0 1 0
regi.out 14
Timp de executie / test: 1 secunda
Subiectul II - Planks
profesor propunător Ilea Lucian Liceul “Emil Racoviţă” Cluj Napoca
La un depozit de materiale de construcţii se ţine evidenţa tuturor scândurilor de lemn care pot fi cerute spre vânzare. Există n scânduri de lungimi cunoscute, L1, L2, L3, …, Ln. Cererile clienţilor se prezintă ca o succesiune de m numere naturale, acestea reprezentând lungimile scândurilor solicitate. Gestionarul depozitului are o metodă proprie de a verifica dacă el poate îndeplini cererea unui client, anume, atunci când are o astfel de cerere, el alege cea mai lungă scândură pe care o are în depozit, taie din ea, dacă este cazul, o bucată cu lungimea solicitată de client şi apoi, dacă a mai ramas ceva din scândura iniţială, bucata rămasă este dusă înapoi în depozit.
Să se scrie un program care citeşte n, apoi lungimile scândurilor din depozit, apoi numărul de cereri, apoi lungimile scândurilor cerute de clienţi. Programul trebuie să afişeze numărul cererilor care nu au putut fi onorate.
Datele de intrare se citesc din fişierul planks.in.
Datele de ieşire (un număr natural reprezentând numărul de cereri care nu au putut fi onorate) se vor scrie în fişierul planks.out.
Restricţii şi precizări:
- 1≤n≤10000
- Lungimile scândurilor din depozit şi ale scândurilor solicitate sunt numere naturale nenule şi mai mici sau egale cu 10000
- m (numărul de cereri este un număr natural nenul şi mai mic sau egal cu 10000)
Exemple
planks.in
5
6 5 3 3 7
5
4 7 5 3 4
planks.out 2
Explicaţii: Dupa onorarea primei comenzi scandurile din depozit au lungimile
6 5 3 3 3
A doua cerere nu poate fi onorata. A treia si a patra cerere pot fi onorate. Ultima cerere nu poate fi onorata.
Timp de executie / test: 1 secunda
Pentru 50 % din teste se considera ca n≤1000.
SUBIECTE:
CLASELE IX-XII
Subiectul I – Regi
profesor propunător Ilea Lucian Liceul “Emil Racoviţă” Cluj Napoca
În această problemă se consideră că o tablă de şah poate fi reprezentată cu ajutorul unei matrici pătratice de ordin n. Matricea conţine valori 0 sau 1. Valorile 0 corespund câmpurilor libere iar valorile 1 corespund câmpurilor ocupate. Spre deosebire de jocul de şah, unde regele poate să mute în oricare din cele opt câmpuri vecine, de data aceasta vor fi considerate ca fiind mutări posibile doar acelea în care numărul de ordine al liniei este strict mai mare decât al liniei curente. Sunt posibile, aşadar, maxim trei mutări ale unui rege situat în poziţia (i,j) şi anume spre câmpurile (i+1,j-1), (i+1,j), (i+1,j+1). Nu vor fi considerate situaţiile în care regele ajunge în afara tablei sau într-o poziţie ocupată.
Se cere să se scrie un program care determină numărul de trasee diferite pe care un rege care porneşte de oriunde din linia 1 ajunge oriunde în linia n. Deoarece rezultatul poate să fie foarte mare, se cere să se afişeze doar restul împărţirii sale la 10000.
Datele de intrare se citesc din fişierul regi.in.
Datele de ieşire (un număr natural reprezentând restul împărţirii numărului de trasee la 10000) se vor scrie în fişierul regi.out.
Restricţii şi precizări
- 1≤n≤50
- câmpurile ocupate se pot găsi oriunde, inclusiv în prima şi ultima linie
- datele de intrare se consideră corecte
Exemple
regi.in
3
0 0 0
1 0 1
0 0 0
regi.out 9
Explicatii: Exista 3 trasee cu pornire din (1,1), 3 trasee cu pornire din (1,2), 3 trasee cu pornire din (3,3). (3+3+3) mod 10000 = 9
regi.in
4
0 0 0 1
1 0 1 0
0 0 0 1
1 0 1 0
regi.out 14
Timp de executie / test: 1 secunda
Subiectul II - Planks
profesor propunător Ilea Lucian Liceul “Emil Racoviţă” Cluj Napoca
La un depozit de materiale de construcţii se ţine evidenţa tuturor scândurilor de lemn care pot fi cerute spre vânzare. Există n scânduri de lungimi cunoscute, L1, L2, L3, …, Ln. Cererile clienţilor se prezintă ca o succesiune de m numere naturale, acestea reprezentând lungimile scândurilor solicitate. Gestionarul depozitului are o metodă proprie de a verifica dacă el poate îndeplini cererea unui client, anume, atunci când are o astfel de cerere, el alege cea mai lungă scândură pe care o are în depozit, taie din ea, dacă este cazul, o bucată cu lungimea solicitată de client şi apoi, dacă a mai ramas ceva din scândura iniţială, bucata rămasă este dusă înapoi în depozit.
Să se scrie un program care citeşte n, apoi lungimile scândurilor din depozit, apoi numărul de cereri, apoi lungimile scândurilor cerute de clienţi. Programul trebuie să afişeze numărul cererilor care nu au putut fi onorate.
Datele de intrare se citesc din fişierul planks.in.
Datele de ieşire (un număr natural reprezentând numărul de cereri care nu au putut fi onorate) se vor scrie în fişierul planks.out.
Restricţii şi precizări:
- 1≤n≤10000
- Lungimile scândurilor din depozit şi ale scândurilor solicitate sunt numere naturale nenule şi mai mici sau egale cu 10000
- m (numărul de cereri este un număr natural nenul şi mai mic sau egal cu 10000)
Exemple
planks.in
5
6 5 3 3 7
5
4 7 5 3 4
planks.out 2
Explicaţii: Dupa onorarea primei comenzi scandurile din depozit au lungimile
6 5 3 3 3
A doua cerere nu poate fi onorata. A treia si a patra cerere pot fi onorate. Ultima cerere nu poate fi onorata.
Timp de executie / test: 1 secunda
Pentru 50 % din teste se considera ca n≤1000.
Comentarii
Trimiteți un comentariu