Fișierul intrare/ieșire parcare.in, parcare.out Sursă Olimpiada pe scoala 2016 clasa a 7-a
Autor Isabela Coman Adăugată de avatar Isabela_coman Coman Isabela Patricia Isabela_coman
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Parcare ( clasa a 6-a )

Mihai a construit de curând un mare mall. La subsolul acestuia se găsește o parcare dreptunghiulară cu 2 intrări, IN1 si IN2. Parcarea are M linii de parcare, respectiv N sectoare numerotate cu litere mari. Cum parcarea este mai mereu aglomerată, Mihai dorește să pună la dispoziție clienților săi o aplicație pentru telefoanele mobile, pentru rezervarea locurilor de parcare. După ce rezervă un loc de parcare, un client poate vedea informații despre locurile de parcare libere, in eventualitatea in care acesta ar dori să mai rezerve și alte locuri de parcare pentru prieteni. Mihai vrea să testeze aplicația și rezervă un loc de parcare de pe telefonul lui mobil.

Cerință

Cunoscând numărul de linii M și numărul de sectoare N, parcarea rezervată de Mihai, cât și locurile de parcare care sunt deja ocupate la momentul rezervării, aplicația trebuie să furnizeze urmatoarele informații:
a) Câte sectoare ale parcării sunt complet goale, inainte ca Mihai să facă rezervarea.
b) Câte locuri de parcare sunt goale, de o parte si de alta a locului de parcare rezervat de Mihai, pe aceeasi linie cu locul de parcare al lui Mihai.
c) Distanța minimă, măsurată in metri, ce poate fi parcursă de la una din intrări până la locul rezervat de Mihai și intrarea pe care trebuie să intre clientul pentru a parcurge dinstanța minima. Pentru usurința calculului, considerăm că lungimea și lățimea unui loc de parcare, cât și lățimea benzilor de circulație au aceași mărime, și anume 1m.

Date de intrare

Fișierul de intrare parcare.in conține:

  • pe prima linie valorile M si N, reprezentând numărul de linii, respectiv de sectoare ale parcarii.
  • pe a doua linie locul de parcare rezervat de Mihai.
  • pe a treia linie un numar P, reprezentând numărul de parcări ocupate,
  • pe a patra linie codurile celor P parcari ocupate, despărțite prin câte un spațiu.

Date de ieșire

Fișierul de iesire parcare.out conține:

  • pe prima linie, numărul de sectoare goale,
  • pe a doua linie, numărul de parcări goale de-o parte si de alta a locului de parcare rezervat de Mihai
  • pe a treia linie distanța minimă până la locul de parcare, cât si intrarea pe care trebuie să intre clientul pentru a parcurge distanța minima. În cazul în care distanța minimă poate fi parcursă pornind de la oricare dintre cele 2 intrări, vor fi afișate ambele intrări.

Restricții

  • 1 <= M <= 1000 ;
  • 2 <= N <= 702 , N par
  • Sectoarele sunt denumite in ordine alfabetica: A,B,C, ….Z, AA, AB, AC, ..etc;
  • Pentru 80% din teste 1 <= N<= 26
  • Se acordă punctaje parțiale: 30p punctul a) ; 30p punctul b) ; 40p punctul c);

Exemplu

parcare.in parcare.out Explicație
8 6
C3
6
A4 A5 B6 E3 E6 F4
2
3
9 1
2 sectoare sunt complet goale: Sectoarele C si D
Sunt 3 parcari libere, pe aceasi linie cu C3, de-o parte si de alta parcarii C3.
Distanta minima pana la C3 este 9 (vezi traseul verde din desen) .
Clientul trebuie sa intre prin intrarea 1.
8 6
C5
6
A4 A5 B6 E3 E6 F4
2
4
11 1 2
2 sectoare sunt complet goale
Sunt 4 parcari libere: B5, D5, E5, F5
Distanța minimă este 11 și ea poate fi parcursă de la oricare din cele 2 intrări.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii