Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ML1_B - Złożoność czasowa

Dany jest kod programu składający się z k linii. Program ten przyjmuje n danych wejściowych. Każda z k linii zawiera jedną z trzech instrukcji:

  • for - Rozpoczęcie pętli. Instrukcje wewnątrz pętli zostaną wykonane n razy. Jeden obrót pętli dla każdej danej wejściowej.
  • end - Zakończenie pętli.
  • instruction - Dowolna instrukcja inna niż rozpoczęcie i zakończenie pętli.

Gwarantujemy, że pętle są poprawnie zagnieżdżone czyli dla każdej instrukcji for istnieje odpowiadająca jej instrukcja end. Gwarantujemy również, że każda pętla zawiera w sobie inną pętlę for lub instrukcję instruction.

Zdefiniujmy złożoność czasową naszego programu jako największy stopień zagnieżdżenia pętli for. Możliwe złożoności czasowe to:

  • O(1) - Złożoność stała. Występuje, gdy program nie zawiera żadnej pętli for, czyli jest niezależny od liczby danych wejściowych.
  • O(n) - Złożoność liniowa. Występuje, gdy program zawiera pętle for, ale nie są one zagnieżdżone.
  • O(n^s) - Złożoność wielomianowa. Występuje, gdy program zawiera zagnieżdżone pętle for, a największy stopień ich zagnieżdżenia wynosi s.

Odpowiedz na pytanie, jaka jest złożoność czasowa danego programu?

Wejście

W pierwszej linii wejścia znajduje się liczba linii kodu k ∈ [1, 1000].

W kolejnych k liniach znajduje się kod programu. Każda linia zawiera jedną z instrukcji: for, end, instruction.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest złożoność czasowa danego programu?

Przykład

Wejście:

18
instruction
for
for
instruction
end
for
instruction
instruction
instruction
for
instruction
instruction
end
instruction
end
end
instruction
instruction

Wyjście:

O(n^3)

Dodane przez:Maciej Boniecki
Data dodania:2019-06-23
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Mini Liga 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.