0747 - Turism

Cerința

În oraşul Z sunt un număr de n obiective turistice, numerotate de la 1 la n. Pentru a ajuta turiştii să viziteze oraşul, primăria a cumpărat un autobuz special ce are k locuri şi care va parcurge cele n puncte de atracţie turistică începând cu obiectivul numerotat cu 1, apoi obiectivul numerotat cu 2, …, până la obiectivul numerotat cu n şi apoi revine la obiectivul 1, traseul având formă circulară. În fiecare staţie aşteaptă un anumit număr de călători; pentru fiecare călător se ştie numărul de staţii pe care doreşte să le parcurgă. Călătorii au acces în autobuz numai dacă sunt locuri libere, în ordinea în care așteaptă în stație, iar cei care nu pot urca părăsesc staţia; la următoarea oprire în staţia respectivă vor aştepta alţi călători. Pentru fiecare staţie parcursă costul unui bilet este 1 leu. Autobuzul va face pentru ultima urcare a călătorilor şi un ultim tur în care doar coboară călători şi nu urcă nimeni. Se cere numărul de curse complete realizate şi suma încasată pentru cursele realizate.

Determinarea valorilor ce reprezintă suma încasată şi numărul de curse complete realizate.

Date de intrare

Fișierul de intrare turism.in conține pe prima linie trei numere naturale: n(numărul de staţii), k(numărul de locuri) şi m(numărul de opriri) separate printr-un spaţiu. Pe următoarele m linii secvenţe de valori ce reprezintă numărul de călători din stația respectivă şi pentru fiecare călător numărul staţiilor pe care le parcurge dacă are loc în mijlocul de transport, cu un spaţiu între ele.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa numărul ce reprezintă suma încasată şi numărul de curse realizate, separate prin exact un spațiu.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 0 < n ≤ 200,n ≤ m ≤ 10000, 2 < k ≤ 100

• 0 < numărul de staţii parcurse de un călător ≤ n

• autobuzul opreşte în fiecare staţie
• în fiecare staţie sunt cel mult k călători

Exemplu 1

Intrare

10 8 16

9 4 2 6 8 1 1 1 3 2

2 1 3

2 1 1

2 1 2

2 10 7

2 10 1

2 2 2

2 2 2

2 2 6

2 4 1

2 4 1

4 3 1 1 1

3 1 1 1

8 5 7 4 10 2 3 2 5

4 1 10 1 1

4 1 1 1 10

Ieșire

Datele de intrare corespund restricțiilor impuse.

138 3

Explicație

În prima staţie urcă primii 8 în autobuz, în a doua coboara 3(cei 3 care au ales sa parcurga numai 1 staţie) şi urca 2, şi aşa mai departe până se parcurg toate cele 16 opriri alea autobuzului. Suma încasată este : 138.

Exemplu 2

Intrare

16 8 9

9 4 2 6 8 1 1 20 3 2

2 1 3

2 20 1

2 1 2

2 10 7

2 50 1

3 2 2

4 2 2

2 2 6

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 0747 Turism

def conditii(nr_statii, nr_locuri, nr_opriri):

   restrictii = (
       0 < nr_statii <= 200,
       nr_statii <= nr_opriri <= 10_000,
       2 < nr_locuri <= 100
   )

   return all(restrictii)

def conditii_calatori(nr_statii, nr_calatori, calatori):

   if not nr_calatori == len(calatori):
       return False

   for c in calatori:
       if not 0 < c <= nr_statii:
           return False

   return True

if __name__ == "__main__":

   scaune = [0] * 110
   cost = 0

   nr_statii, nr_locuri, nr_opriri = [int(x) for x in input().split()]

   if not conditii(nr_statii, nr_locuri, nr_opriri):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       # Pentru fiecare oprire...
       for i in range(1, nr_opriri+1):
           # ...scădem 1 din fiecare scaun ocupat
           for j in range(1, nr_locuri+1):
               if scaune[j]:
                   scaune[j] -= 1
           # Inițializăm poziția primului scaun liber cu 1
           poz = 1

           rand_input = [int(x) for x in input().split()]
           nr_calatori = rand_input[0]
           calatori = rand_input[1:]

           if not conditii_calatori(nr_statii, nr_calatori, calatori):
               print("Datele de intrare nu corespund restricțiilor impuse.")
               exit(0)

           # Pentru fiecare călător...
           for cal in calatori:
               # ...căutăm primul scaun liber și îl ocupăm
               while poz <= nr_locuri and scaune[poz]:
                   poz += 1
               if poz <= nr_locuri:
                   scaune[poz] = cal
                   cost += cal

       print("Datele de intrare corespund restricțiilor impuse.")

       # Calculăm numărul de opriri necesare bazat pe numărul maxim de călători per stație
       maxim = scaune[0]
       for i in range(1, nr_locuri):
           if scaune[i] > maxim:
               maxim = scaune[i]

       rez = (nr_opriri - 1) // nr_statii + 1
       if maxim:
           rez += (maxim - nr_opriri % nr_statii - 1) // nr_statii + 1

       print(cost, rez)

</syntaxhighlight>