| Fișierul intrare/ieșire | bonsai.in, bonsai.out | Sursă | OJI 2026 clasa a 7-a |
|---|---|---|---|
| Autor | Andrei Cotoi | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.35 sec | Limită de memorie | 32768 KB |
| Scorul tău | N/A | Dificultate |
   1.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Bonsai (clasa a 7-a)
În grădina palatului de vară, maestrul grădinar Andrei caută locul perfect pentru amplasarea unui bonsai prezidențial. Grădina palatului este formată din mai multe parcele, dispuse pe N linii și M coloane. Deoarece grădina palatului este frecventată de turiști, fiecărei parcele îi este asociat un număr natural, reprezentând importanța parcelei respective.
Bonsaiul prezidențial poate fi plantat doar sub forma unei cruci simetrice (un centru și 4 brațe egale pe direcțiile Nord, Sud, Est, Vest), care nu conține valori nule (parcele cu importanța 0) și are număr maxim de parcele pe care se poate amplasa un bonsai. Un bonsai este definit de centrul său (i, j) și de raza maximă posibilă R, cu care se poate extinde pe toate cele 4 direcții (numărul de parcele al unui braț, fără a număra centrul). Un bonsai cu R=0 ocupă o singură parcelă (centrul), iar un bonsai cu R=1 ocupă centrul și cei 4 vecini: (i-1,j), (i+1,j), (i,j-1), (i,j+1).
Andrei are trei criterii diferite de alegere, în funcție de cerința președintelui:
- Criteriul simplitate: Președintele își dorește un bonsai simplu de rază R=0, astfel Andrei trebuie să caute toate locurile posibile în care se poate amplasa un bonsai de rază R=0.
- Criteriul măreție: Președintele își dorește cel mai extins bonsai posibil, astfel Andrei este nevoit să caute raza maximă Rmax pe care o poate avea un bonsai în grădină.
- Criteriul vizibilitate: Președintele își dorește cea mai mare vizibilitate turistică pentru bonsaiul său, astfel Andrei este nevoit să caute locul în care, dacă ar planta bonsaiul, acesta ar avea importanță maximă. Importanța unui loc în care bonsaiul poate fi plantat este reprezentată de suma importanței parcelelor pe care le acoperă.
Cerințe
Se dau C, reprezentând cerința care trebuie rezolvată (C=1, C=2 sau C=3), N, M, dimensiunile grădinii și N×M valori naturale, reprezentând importanța fiecărei parcele.
- Dacă C=1, ajutați-l pe Andrei să determine în câte locuri posibile din grădină ar putea planta un bonsai de rază R=0.
- Dacă C=2, ajutați-l pe Andrei să determine raza maximă Rmax a unui bonsai care poate fi plantat în grădină.
- Dacă C=3, ajutați-l pe Andrei să determine locul cu importanța maximă în care poate planta bonsaiul, precum și coordonatele (i, j) ale centrului acestuia. Dacă există mai multe locuri cu aceeași importanță maximă, se va alege cel cu raza R cea mai mare. Dacă există mai multe astfel de locuri cu importanța egală și cu aceeași rază R, se va alege locul cu i minim, iar în caz de egalitate, cel cu j minim.
Date de intrare
Pe prima linie a fișierului bonsai.in se află un număr natural C, care reprezintă cerința (1, 2 sau 3). Pe a doua linie se află două numere naturale N și M, cu semnificația din enunț. Următoarele N linii conțin câte M valori, reprezentând importanța fiecărei parcele. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Date de ieșire
În fișierul de ieșire bonsai.out se află:
- Un singur număr: P care reprezintă numărul de locuri din grădină în care Andrei poate planta un bonsai de rază R=0, dacă C=1.
- Un singur număr: Rmax, reprezentând raza maximă a unui bonsai care poate fi plantat în grădină, dacă C=2.
- Trei numere separate prin câte un spațiu: S, i, j, care reprezintă suma parcelelor ocupate de bonsaiul de importanță maximă și linia, respectiv coloana pe care se află centrul bonsaiului determinat, dacă C=3.
Restricții și precizări
- 1 ≤ N, M ≤ 1000
- Importanța fiecărei parcele este un număr natural ≤ 1000.
- Valoarea 0 reprezintă un obstacol și nu poate face parte din locul bonsaiului.
- Se garantează că există cel puțin o parcelă cu importanța nenulă.
- Un bonsai nu se poate extinde în afara grădinii.
| # | Punctaj | Restricții |
|---|---|---|
| 1 | 29 | C=1 |
| 2 | 31 | C=2 și N, M ≤ 100 |
| 3 | 10 | C=2 și nu există restricții suplimentare |
| 4 | 9 | C=3 și N, M ≤ 100 |
| 5 | 21 | C=3 și nu există restricții suplimentare |
Exemple
| bonsai.in | bonsai.out | Explicații |
|---|---|---|
| 1 3 6 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 |
9 |
Parcelele situate în pozițiile (1, 2), (1, 5), (1, 6), (2, 1), (2, 3), (2, 4), (2, 6), (3, 2) și (3,5) pot fi centre pentru un bonsai prezidențial de rază R=0. Parcelele (2,2) și (2,5) pot fi centre pentru un bonsai de rază R=1, dar nu sunt considerate valide. |
| 2 3 6 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 |
1 |
Există două locuri posibile pentru plantarea unui bonsai prezidențial cu raza maximă R=1: Primul cu centrul în (2,2): vecinii sunt (1, 2), (3, 2), (2, 1), (2,3). Toți au valoarea 1. Al doilea cu centrul în (2,5): vecinii sunt (1, 5), (3, 5), (2, 4), (2,6). Toți au valoarea 1. Astfel, Rmax=1 și sunt 2 parcele care pot fi centru. |
| 3 4 4 1 2 1 0 2 5 2 0 1 2 1 0 0 0 0 9 |
13 2 2 |
Avem mai multe locuri posibile pentru amplasarea bonsaiului prezidențial, cele mai relevante fiind: 1. Bonsaiul prezidențial cu centrul în (2,2) are raza R=1 și importanța lui este 5(Centru)+2(Nord)+2(Sud)+2(Vest)+2(Est)=13. 2. Bonsaiul cu centrul în (4,4) are raza R=0 (valorile vecinilor în cele patru puncte cardinale sunt 0 sau în afara tabloului bidimensional). Importanța este 9. Maximul importanței este 13 și se obține pentru bonsaiul prezidențial cu centrul în (2,2). |
| 3 3 6 0 2 0 0 0 0 2 2 2 0 10 0 0 2 0 0 0 0 |
10 2 2 |
Avem două posibilități: 1. Bonsaiul prezidențial cu centrul în (2,2) are R=1 și importanța 2+2+2+2+2=10. 2. Bonsaiul prezidențial cu centrul în (2,5) are R=0 și importanța 10. Se alege bonsaiul prezidențial cu raza R cea mai mare, adică bonsaiul cu centrul în (2,2). |
