Optimal proqram#1756

Optimal proqram

1 saniyə

64 meqabayt

Asan

Bildiyiniz kimi, proqram yazmaq çox zaman asan olmur. Proqramlarınızın mümkün qədər sürətli işləməsi lazım olduqda isə iş daha da çətinləşir. Bəzən isə bunun üçün ciddi səbəb olur. Əməliyyat sistemləri və verilənlər bazaları kimi böyük proqramların bir çoxunda "darboğazlar"—dəfələrlə icra olunan və toplam işləmə zamanının əsas hissəsini təşkil edən kod hissələri olur. Belə kod hissələrini assembler dilində yenidən yazmaq adətən məntiqlidir, çünki bir neçə saniyəlik sürət qazansa belə, kod milyardlarla dəfə icra olunduqda bunun böyük mənası olur.

Bu məsələdə biz optimal assembler kodunun avtomatik yaradılması tapşırığını nəzərdən keçirəcəyik. Bir funksiyanın (giriş/çıxış cütləri ilə verilmiş) hesablama qaydasını müəyyən edən mümkün olan ən qısa assembler proqramını tapmalısınız.

Sizin proqramınız yalnız beş əmri dəstəkləyən stek əsaslı maşında işləməlidir: ADD, SUB, MUL, DIV və DUP. İlk dörd əmri stack-in üstündəki iki elementi çıxarıb (pop) onların cəmini, fərqini, hasilini və ya tam bölməsini (integer quotient) stack-ə push edir. DUP əmri stek-in ən üstündəki elementi təkrarlayaraq stek-ə əlavə edir.

Əgər komandalar stack-in üstündə $a$ və $b$ olmaqla tətbiq edilsə, komandanın nəticəsində stack aşağıdakı kimi olacaq:

Proqram işləməyə başlayanda stack yalnız bir ədəd tam ədəddən—daxil olan qiymətdən—ibarət olur. Hesablama nəticəsində də stack-da yalnız bir ədəd olmalıdır—əsas nəticə.

Stack maşını aşağıdakı üç halda xəta vəziyyətinə keçəcək:

Əgər DIV əmri icra olunanda stek-in üstündəki element $0$ olarsa.
Əgər ADD, SUB, MUL və ya DIV əmri icra olunanda stek-də yalnız bir element olarsa.
Hər hansı əməliyyat nəticəsində alınan qiymət $30000$ -dən böyük və ya $- 30000$ -dən kiçik (modul üzrə) olarsa.

Giriş

Giriş verilənləri bir neçə funksiya təsvirindən ibarətdir. Hər təsvir bir ədəd tam ədəd $n$ ( $n \leq 10$ n \leq 10) ilə başlayır—giriş/çıxış cütlərinin sayı. Sonrakı iki sətrin hər birində $n$ tam ədəd var: birinci sətirdə girişlər (hamısı fərqlidir), ikinci sətirdə isə uyğun çıxışlar verilib. Bütün ədədlər modul üzrə ən çox $30000$ olacaq.

Giriş $n = 0$ n=0 olan təsvirlə bitir. Bu test halı işlənməməlidir.

Çıxış

Siz elə ən qısa proqramı tapmalısınız ki, $f (x_{i}) = y_{i}$ f(x_i) = y_i olsun bütün $i \in {1, \dots, n}$ i \in \{1, \ldots, n\} üçün. Yəni, təqdim olunan $x_{i}$ x_i girişləri üçün proqram xəta vəziyyətinə keçməməlidir, amma başqa girişlər üçün keçsə olar. Yalnız ən çox $10$ əmrdən ibarət proqramları nəzərə alın.

Hər funksiya təsviri üçün əvvəlcə təsvir nömrəsini çap edin. Sonra isə verilmiş funksiyanı hesablamaq üçün ən qısa əmrlər ardıcıllığını ardıcıl olaraq çıxışa verin. Əgər bir neçə belə proqram varsa, leksikoqrafik olaraq ən kiçiyini verin. Əgər funksiyanı hesablaya bilən $10$ və ya daha az əmrdən ibarət proqram yoxdursa, "Impossible" sətrini çap edin. Proqram sıfır əmrdən ibarətsə, "Empty sequence" sətrini çap edin.

Hər testdən sonra bir boş sətir çap edin.

Nümunələr

Nümunə 1