Podstawy Programowania

Zadanie polega na symulacji działania programowalnego kalkulatora całkowitoliczbowego. Instrukcje dla kalkulatora podawane są w specjalnym języku PPCALC, a wszyskie operacje wykonywane są w ciele Galois GF(p) (na liczbach całkowitych ze zbioru {0,...,p-1}, gdzie p jest liczbą pierwszą). Program będący rozwiązaniem zadania powinien odczytać parametry kalkulatora, oraz kod programu w PPCALC-u, a następnie przeprowadzić symulację jego działania (należy przyjąć, że podany program jest poprawny). Kalkulator pozwala na wykonywanie pewnych operacji arytmetycznch oraz dysponuje pamięcią.

Zadanie składa się z części podstawowej oraz rozszerzonej.

Opis danych wejściowych

Najpierw podane są parametry kalkulatora:

• 2 <= p < 2³²,
• mem - liczba komórek pamięci kalkulatora (początkowo wartości we wszystkich komórkach pamięci są ustawione na 0).

Dla wersji podstawowej mem=4.

Następnie podany jest program w PPCALC-u. Program składa się z wierszy, a każdy wiersz może być:

• instrukcją przypisania
• instrukcją PRINT
• deklaracją etykiety (tylko wersja rozszerzona)
• instrukcją skoku (tylko wersja rozszerzona)

Ostatnim wierszem każdego programu jest:
END

Instrukcja przypisania ma postać:
$[numer komórki pamięci] [operator] [liczba]

lub:
$[numer komórki pamięci] [operator] $[numer komórki pamięci]

Instrukcja PRINT ma postać:
PRINT $[numer komórki pamięci]

Deklaracja etykiety ma postać:
:[label name]

Instrukcja skoku ma postać:
JMPNZ $[numer komórki pamięci] [label name]
skok następje tylko w przypadku, gdy wartość we wskazanej komórce pamięci jest różna od zera.

[numer komórki pamięci] - to liczba num, że 0 <= num < mem.

[label name] - to nazwa etykiety składająca się z nie więcej niż 8 liter.

[operator] - oznacza jeden z dostępnych operatorów:

• += działanie w grupie addytywnej (suma modulo p - w komórce docelowej powinna znaleźć się reszta z dzielenia przez p sumy zawartości komórki docelowej i drugiego argumentu),
• *= działanie w grupie multiplikatywnej (iloczyn modulo p - w komórce docelowej powinna znaleźć się reszta z dzielenia przez p iloczynu zawartości komórki docelowej i drugiego argumentu),
• ^= potęgowanie (wielokrotne działanie grupy multiplikatywnej) - w komórce docelowej powinna znaleźć się reszta z dzielenia przez p zawartości komórki docelowej podniesiona do drugiego argumentu,
• -= działanie odwrotne w grupie addytywnej (różnica modulo p - - w komórce docelowej powinna znaleźć się reszta z dzielenia przez p różnicy zawartości komórki docelowej i drugiego argumentu),
• /= działanie odwrotne w grupie multiplikatywnej (tylko wersja rozszerzona).

Opis danych wyjściowych

Dla każdej instrukcji PRINT powinna zostać wyświetlona jedna liczba, która znajduje się w żądanej komórce pamięci.

Przykład 1

Input:
7 4
$1 += 1
$1 *= 2
$1 *= 3
PRINT $1
$1 *= 4
PRINT $1
$2 -= 2
PRINT $2
$1 ^= $2
PRINT $1
END

Output:
6
3
5
5

Przykład 2 (dla wersji rozszerzonej)

Input:
7 4
$1 += 1
$2 += 1
$3 += 5
:next
$0 -= $0
$0 += $1
$1 -= $1
$1 += $2
$2 += $0
$3 -= 1
JMPNZ $3 next
PRINT $2
END

Output:
6

Punktacja

Jest 15 testów wartych po 1 punkt każdy. Pierwsze 10 testów odpowiada poziomowi podstawowemu. Pierwszy test zawiera tylko operacje dodawawania dla p < 100 . Kolejne testy zawierają dodatkowe elementy.

Fast Modular Exponentiation - kalkulator (może być pomocny).

Powodzenia!