Лабораторная работа для групп М3305 — М3308 Цифровая сортировка, стек и очередь. 20 октября 2016 года. Задача A. Стек (!) (1 балл). Имя входного файла: Имя выходного файла: Ограничение по времени: Ограничение по памяти: stack.in stack.out 2 секунды 6


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
ËàáîðàòîðíàÿðàáîòàäëÿãðóïïÌ3305-Ì3308
Öèôðîâàÿñîðòèðîâêà,ñòåêèî÷åðåäü.20îêòÿáðÿ2016ãîäà.
Çàäà÷àA.Ñòåê(!)(1áàëë)
Èìÿâõîäíîãîôàéëà:
stack.in
Èìÿâûõîäíîãîôàéëà:
stack.out
Îãðàíè÷åíèåïîâðåìåíè:2ñåêóíäû
Îãðàíè÷åíèåïîïàìÿòè:64ìåãàáàéòà
Ðåàëèçóéòåðàáîòóñòåêà.Äëÿêàæäîéîïåðàöèèèçúÿòèÿýëåìåíòàâûâåäèòåååðåçóëüòàò.
Íàâõîäïðîãðàììåïîäàþòñÿñòðîêè,ñîäåðæàùèåêîìàíäû.Êàæäàÿñòðîêàñîäåðæèòîäíóêî-
ìàíäó.Êîìàíäàýòîëèáî
+N
,ëèáî
-
.Êîìàíäà
+N
îçíà÷àåòäîáàâëåíèåâñòåê÷èñëà
N
,ïî
ìîäóëþíåïðåâûøàþùåãî
10
9
.Êîìàíäà
-
îçíà÷àåòèçúÿòèåýëåìåíòàèçñòåêà.Ãàðàíòèðóåòñÿ,÷òî
íåïðîèñõîäèòèçâëå÷åíèÿèçïóñòîãîñòåêà.Ãàðàíòèðóåòñÿ,÷òîðàçìåðñòåêàâïðîöåññåâûïîëíåíèÿ
êîìàíäíåïðåâûñèò
10
6
ýëåìåíòîâ.
Ôîðìàòâõîäíîãîôàéëà
Âïåðâîéñòðîêåâõîäíîãîôàéëàñîäåðæèòñÿêîëè÷åñòâîêîìàíä
M
(
1
6
M
6
10
6
).Êàæäàÿ
ïîñëåäóþùàÿñòðîêàèñõîäíîãîôàéëàñîäåðæèòðîâíîîäíóêîìàíäó.
Ôîðìàòâûõîäíîãîôàéëà
Âûâåäèòå÷èñëà,êîòîðûåóäàëÿþòñÿèçñòåêà,ïîîäíîìóâêàæäîéñòðîêå.Ãàðàíòèðóåòñÿ,÷òî
èçúÿòèéèçïóñòîãîñòåêàíåïðîèçâîäèòñÿ.
Ïðèìåð
stack.in
stack.out
6
+1
+10
-
+2
+1234
-
10
1234
Ñòðàíèöà1èç5
ËàáîðàòîðíàÿðàáîòàäëÿãðóïïÌ3305-Ì3308
Öèôðîâàÿñîðòèðîâêà,ñòåêèî÷åðåäü.20îêòÿáðÿ2016ãîäà.
Çàäà÷àB.Î÷åðåäü(1áàëë)
Èìÿâõîäíîãîôàéëà:
queue.in
Èìÿâûõîäíîãîôàéëà:
queue.out
Îãðàíè÷åíèåïîâðåìåíè:2ñåêóíäû
Îãðàíè÷åíèåïîïàìÿòè:64ìåãàáàéòà
Ðåàëèçóéòåðàáîòóî÷åðåäè.Äëÿêàæäîéîïåðàöèèèçúÿòèÿýëåìåíòàâûâåäèòåååðåçóëüòàò.
Íàâõîäïðîãðàììåïîäàþòñÿñòðîêè,ñîäåðæàùèåêîìàíäû.Êàæäàÿñòðîêàñîäåðæèòîäíóêî-
ìàíäó.Êîìàíäàýòîëèáî
+N
,ëèáî
-
.Êîìàíäà
+N
îçíà÷àåòäîáàâëåíèåâî÷åðåäü÷èñëà
N
,
ïîìîäóëþíåïðåâûøàþùåãî
10
9
.Êîìàíäà
-
îçíà÷àåòèçúÿòèåýëåìåíòàèçî÷åðåäè.Ãàðàíòèðó-
åòñÿ,÷òîðàçìåðî÷åðåäèâïðîöåññåâûïîëíåíèÿêîìàíäíåïðåâûñèò
10
6
ýëåìåíòîâ.
Ôîðìàòâõîäíîãîôàéëà
Âïåðâîéñòðîêåñîäåðæèòñÿêîëè÷åñòâîêîìàíä
M
(
1
6
M
6
10
6
).Âïîñëåäóþùèõñòðîêàõ
ñîäåðæàòñÿêîìàíäû,ïîîäíîéâêàæäîéñòðîêå.
Ôîðìàòâûõîäíîãîôàéëà
Âûâåäèòå÷èñëà,êîòîðûåóäàëÿþòñÿèçî÷åðåäè,ïîîäíîìóâêàæäîéñòðîêå.Ãàðàíòèðóåòñÿ,÷òî
èçâëå÷åíèÿèçïóñòîéî÷åðåäèíåïðîèçâîäèòñÿ.
Ïðèìåð
queue.in
queue.out
4
+1
+10
-
-
1
10
Ñòðàíèöà2èç5
ËàáîðàòîðíàÿðàáîòàäëÿãðóïïÌ3305-Ì3308
Öèôðîâàÿñîðòèðîâêà,ñòåêèî÷åðåäü.20îêòÿáðÿ2016ãîäà.
Çàäà÷àC.Ïðàâèëüíàÿñêîáî÷íàÿïîñëåäîâàòåëüíîñòü(1
áàëë)
Èìÿâõîäíîãîôàéëà:
()()
([])
([)]
((]]
)(
YES
YES
NO
NO
NO
Ñòðàíèöà3èç5
ËàáîðàòîðíàÿðàáîòàäëÿãðóïïÌ3305-Ì3308
Öèôðîâàÿñîðòèðîâêà,ñòåêèî÷åðåäü.20îêòÿáðÿ2016ãîäà.
Çàäà÷àD.Ïîñòôèêñíàÿçàïèñü(2áàëëà)
Èìÿâõîäíîãîôàéëà:
postfix.in
Èìÿâûõîäíîãîôàéëà:
postfix.out
Îãðàíè÷åíèåïîâðåìåíè:2ñåêóíäû
Îãðàíè÷åíèåïîïàìÿòè:64ìåãàáàéòà
Âïîñòôèêñíîéçàïèñè(èëèîáðàòíîéïîëüñêîéçàïèñè)îïåðàöèÿçàïèñûâàåòñÿïîñëåäâóõîïå-
ðàíäîâ.Íàïðèìåð,ñóììàäâóõ÷èñåë
A
è
B
çàïèñûâàåòñÿêàê
AB
+
.Çàïèñü
BC
+
D

îáîçíà÷àåò
ïðèâû÷íîåíàì
(
B
+
C
)

D
,àçàïèñü
ABC
+
D

+
îçíà÷àåò
A
+(
B
+
C
)

D
.Äîñòîèíñòâîïîñòôèêñ-
íîéçàïèñèâòîì,÷òîîíàíåòðåáóåòñêîáîêèäîïîëíèòåëüíûõñîãëàøåíèéîïðèîðèòåòåîïåðàòîðîâ
äëÿñâîåãî÷òåíèÿ.
Äàíîâûðàæåíèåâîáðàòíîéïîëüñêîéçàïèñè.Îïðåäåëèòååãîçíà÷åíèå.
Ïîäñêàçêà:èñïîëüçóéòåñòåê.
Ôîðìàòâõîäíîãîôàéëà
Âåäèíñòâåííîéñòðîêåçàïèñàíîâûðàæåíèåâïîñòôèêñíîéçàïèñè,ñîäåðæàùååîäíîçíà÷íûå
÷èñëàèîïåðàöèè
+
,

,

.Ñòðîêàñîäåðæèòíåáîëåå100÷èñåëèîïåðàöèé.
Ôîðìàòâûõîäíîãîôàéëà
Íåîáõîäèìîâûâåñòèçíà÷åíèåçàïèñàííîãîâûðàæåíèÿ.Ãàðàíòèðóåòñÿ,÷òîðåçóëüòàòâûðàæå-
íèÿ,àòàêæåðåçóëüòàòûâñåõïðîìåæóòî÷íûõâû÷èñëåíèéïîìîäóëþìåíüøå
2
31
.
Ïðèìåð
postfix.in
postfix.out
89+17-*
-102
Ñòðàíèöà4èç5
ËàáîðàòîðíàÿðàáîòàäëÿãðóïïÌ3305-Ì3308
Öèôðîâàÿñîðòèðîâêà,ñòåêèî÷åðåäü.20îêòÿáðÿ2016ãîäà.
Çàäà÷àE.Ïðèîðèòåòíàÿî÷åðåäü(3áàëëà)
Èìÿâõîäíîãîôàéëà:
priorityqueue.in
Èìÿâûõîäíîãîôàéëà:
priorityqueue.out
Îãðàíè÷åíèåïîâðåìåíè:2ñåêóíäû
Îãðàíè÷åíèåïîïàìÿòè:64ìåãàáàéòà
Ðåàëèçóéòåïðèîðèòåòíóþî÷åðåäü.Âàøàî÷åðåäüäîëæíàïîääåðæèâàòüñëåäóþùèåîïåðàöèè:
äîáàâèòüýëåìåíò,èçâëå÷üìèíèìàëüíûéýëåìåíò,óìåíüøèòüýëåìåíò,äîáàâëåííûéâîâðåìÿîäíîé
èçîïåðàöèé.
Âñåîïåðàöèèíóìåðóþòñÿïîïîðÿäêó,íà÷èíàÿñåäèíèöû.Ãàðàíòèðóåòñÿ,÷òîðàçìåðî÷åðåäèâ
ïðîöåññåâûïîëíåíèÿêîìàíäíåïðåâûñèò
10
6
ýëåìåíòîâ.
Ôîðìàòâõîäíîãîôàéëà
Âõîäíîéôàéëñîäåðæèòîïèñàíèåîïåðàöèéñî÷åðåäüþ.Îïåðàöèèìîãóòáûòüñëåäóþùèìè:

push
x
òðåáóåòñÿäîáàâèòüýëåìåíò
x
âî÷åðåäü.

extract-min
òðåáóåòñÿóäàëèòüèçî÷åðåäèìèíèìàëüíûéýëåìåíòèâûâåñòèåãîââûõîäíîé
ôàéë.Åñëèî÷åðåäüïóñòà,ââûõîäíîéôàéëòðåáóåòñÿâûâåñòèçâåçäî÷êó*.

decrease-key
xy
òðåáóåòñÿçàìåíèòüçíà÷åíèåýëåìåíòà,äîáàâëåííîãîâî÷åðåäüîïåðàöèåé
push
âñòðîêåâõîäíîãîôàéëàíîìåð
x
,íà
y
.Ãàðàíòèðóåòñÿ,÷òîíàñòðîêå
x
äåéñòâèòåëüíî
íàõîäèòñÿîïåðàöèÿ
push
,÷òîýòîòýëåìåíòíåáûëðàíååóäàëåíîïåðàöèåé
extract-min
,è÷òî
y
ìåíüøå,÷åìïðåäûäóùååçíà÷åíèåýòîãîýëåìåíòà.
Âî÷åðåäüïîìåùàþòñÿèèçâëåêàþòñÿòîëüêîöåëûå÷èñëà,íåïðåâûøàþùèåïîìîäóëþ
10
9
.
Ôîðìàòâûõîäíîãîôàéëà
Âûâåäèòåïîñëåäîâàòåëüíîðåçóëüòàòâûïîëíåíèÿâñåõîïåðàöèé
extract-min
,ïîîäíîìóâêàæ-
äîéñòðîêåâûõîäíîãîôàéëà.Åñëèïåðåäî÷åðåäíîéîïåðàöèåé
extract-min
î÷åðåäüïóñòà,âûâåäèòå
âìåñòî÷èñëàçâåçäî÷êó*.
Ïðèìåð
priorityqueue.in
priorityqueue.out
push3
push4
push2
extract-min
decrease-key21
extract-min
extract-min
extract-min
2
1
3
*
Ñòðàíèöà5èç5

Приложенные файлы

  • pdf 44441674
    Размер файла: 148 kB Загрузок: 0

Добавить комментарий