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.|

PROGC03 - Kolejki i stosy

Napisz program realizujący obsługę zdarzeń związanych z przetwarzaniem stosów i kolejek. Każda linia w pliku wejściowym stanowi osobne polecenie. Każde polecenie informuje o typie operacji i zawsze zawiera numer stosu i/lub kolejki, których dotyczy. Numer stosu lub kolejki jest liczbą całkowitą z zakresu 0,...,9 (program obsługuje maksymalnie 10 stosów i 10 kolejek). Każdy stos/kolejka może zawierać maksymalnie 10 elementów (elementy to liczby całkowite z przedziału 0,...,1000). Przed przyjęciem pierwszego polecenia należy przyjąć, że żaden stos oraz żadna kolejka nie zostały jeszcze utworzone. Polecenia mogą pojawiać się na wejściu w dowolnej kolejności.

Zadanie zostało podzielone na 4 stopnie trudności (4 testy). Poniżej znajduje się opis poleceń, które program powinien obsłużyć, aby pozytywnie zaliczyć każdy z testów.

Test 1 (3 pkt.)

Spis zdarzeń, które należy obsłużyć:

  • Polecenie nakazujące utworzenie (pustego) stosu i numerze i:
    new_s i
  • Dodanie elementu e do stosu numer i:
    push i e
  • Usunięcie elementu ze szczytu stosu numer i:
    pop i
  • Przeniesienie elementu ze szczytu stosu numer i na stos numer j:
    stack->stack i j
  • Likwidacja stosu numer i wraz ze wszystkimi jego elementami:
    delete_s i
  • Wypisanie zawartości stosu o numerze i (elementy stosu wypisujemy w jednej linii, oddzielone spacjami, liczba będąca na szczycie stosu jest ostatnią liczbą w linii; jesli stos jest pusty, to wypisujemy napis empty):
    print_s i

Uwaga: w przypadku wszystkich poleceń, z wyjątkiem komendy 'drukuj_stos', nie należy wypisywać żadnych znaków na wyjście, a jedynie dokonywać odpowiednich zmian w zawartościach stosów. Wszystkie polecenia są poprawne (opis niepoprawnych poleceń - patrz Test 2).

Test 2 (2 pkt.)

Należy obsłużyć wszystkie polecenia wymienione w Teście 1, lecz należy uwzględnić możliwość pojawienia się następujących sytuacji błędnych:

  • Próba usunięcia elementu z pustego stosu. Należy w takiej sytuacji w osobnej linii na wyjściu wypisać:
    error: stack is empty
  • Próba dodania elementu do pełnego stosu. Należy wypisać:
    error: stack is full

Test 3 (3 pkt.)

Oprócz poleceń z dwóch pierwszych testów należy zaimplementować następujące:

  • Utworzenie nowej kolejki o numerze i:
    new_q i
  • Dodanie elemetu e na koniec kolejki numer i:
    enqueue i e
    Uwaga: w przypadku próby dodania elementu do kolejki, która jest pełna należy na wyjście wypisać napis:
    error: queue is full
  • Usunięcie elementu z początku kolejki numer i:
    dequeue i
    Uwaga: w sytuacji, gdy kolejka jes pusta wypisujemy na wyjście napis:
    error: queue is empty
  • Usunięcie kolejki numer i wraz z całą jej zawartością:
    delete_q i
  • Wypisanie kolejki numer i (wypisujemy jej elementy w jednej linii, przy czym początek linii zawiera elementy będące na końcu kolejki, natomiast ostatni element to jej początek):
    print_q i
    Jeśli kolejka jest pusta, to w osobnej linii wypisujemy słowo empty.

Test 4 (2 pkt.)

Oprócz poleceń z poprzednich testów należy zaimplementować następujące:

  • Przeniesienie elementu ze stosu numer i do kolejki numer j:
    stack->queue i j
  • Przeniesienie elementu z kolejki numer i do kolejki numer j:
    queue->queue i j
  • Przeniesienie elementu z kolejki numer i na stos numer j:
    queue->stack i j
  • W przypadku każdej z czterech operacji przenoszenia elementu ze stosu/kolejki na stos/kolejkę należy wypisać na wyjściu napis:
    error: wrong command
    gdy polecenie wymaga usunięcia elementu z pustej kolejki lub pustego stosu lub gdy polecenie wymaga umieszczenia elementu w pelnej kolejce lub pełnym stosie.

Uwaga: w przypadku wszystkich błędnych operacji (tzn. takich, których wynikiem jest wypisanie na ekran napisu rozpoczynającego sie od "error:" zawartości wszystkich stosów i kolejek nie ulegają zmianie.

Uwaga: wstawienie elementu do kolejki polega na umieszczeniu go na jej końcu. Wstawienie elementu na stos polega na umieszczeniu go na szczycie stosu. Usunięcie elementu z kolejki oznacza usunięcie elementu znajdującego się na jej początku. Usunięcie elementu ze stosu jest usunięciem z jego wierzchołka.

Test 1 - przykład

Wejście:
new_s 0
push 0 96
new_s 5
print_s 5
push 5 28
push 5 99
push 5 88
pop 0
print_s 5
push 0 65
stack->stack 5 0
print_s 0

Wyjście:
empty
28 99 88
65 88

Test 2 - przykład

Wejście:
new_s 0
push 0 96
new_s 5
print_s 5
push 5 28
push 5 99
push 5 33
push 5 88
pop 0
print_s 5
pop 0
push 0 65
push 5 99
push 5 13
push 5 99
push 5 1
push 5 99
push 5 0
push 5 9
push 5 87
stack->stack 5 0
print_s 0

Wyjście:
empty
28 99 33 88
error: stack is empty
error: stack is full
error: stack is full
65 0

Test 3 - przykład

Wejście:
new_s 0
push 0 96
new_s 5
print_s 5
push 5 28
push 5 99
new_q 0
push 5 33
push 5 88
pop 0
print_s 5
pop 0
push 0 65
push 5 99
dequeue 0
enqueue 0 4
new_q 9
push 5 13
push 5 99
enqueue 0 43
enqueue 0 21
enqueue 0 17
enqueue 0 4
enqueue 9 0
enqueue 0 4
enqueue 0 43
enqueue 0 40
push 5 1
push 5 99
enqueue 0 33
enqueue 0 99
enqueue 0 8
push 5 0
push 5 9
delete_q 0
print_q 9
push 5 87
new_q 0
enqueue 0 19
print_q 0
stack->stack 5 0
print_s 0

Wyjście:
empty
28 99 33 88
error: stack is empty
error: queue is empty
error: queue is full
error: stack is full
0
error: stack is full
19
65 0

Test 4 - przykład

Wejście:
new_s 0
push 0 96
new_s 5
print_s 5
push 5 28
push 5 99
new_q 0
push 5 33
push 5 88
pop 0
print_s 5
pop 0
push 0 65
push 5 99
dequeue 0
enqueue 0 4
new_q 9
push 5 13
push 5 99
enqueue 0 43
enqueue 0 21
enqueue 0 17
stack->queue 0 0
enqueue 0 4
stack->queue 0 0
enqueue 9 0
enqueue 0 4
enqueue 0 43
queue->queue 0 0
stack->stack 5 5
enqueue 0 40
push 5 1
push 5 99
enqueue 0 33
enqueue 0 99
enqueue 0 8
push 5 0
push 5 9
delete_q 0
print_q 9
push 5 87
new_q 0
stack->queue 5 0
enqueue 0 3
queue->queue 0 0
enqueue 0 19
stack->stack 5 0
print_s 0
print_s 5
print_q 0
print_q 9

Wyjście:
empty
28 99 33 88
error: stack is empty
error: queue is empty
error: wrong command
error: queue is full
error: queue is full
error: stack is full
0
error: stack is full
99
28 99 33 88 99 13 99 1
19 0 3
0

Dodane przez:Darek Dereniowski
Data dodania:2007-11-05
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: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.