Задача 4. Сокращение одночленов

Одночлен — это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом ‘*’ (ASCII 42), возведение в степень — символом ‘^’ (ASCII 94). Показатель степени состоит из одной десятичной цифры от 1 до 9. Примеры одночленов: t, a*b*c^2, y*d^1*y^9.

Требуется по данным N + M одночленам построить дробь, равную произведению первых N одночленов, делённому на произведение оставшихся M одночленов. При этом:

5. Числитель и знаменатель дроби должны быть одночленами.

6. Переменная не должна встречаться в дроби более одного раза (т. е. дробь необходимо сократить).

7. Степени переменных должны быть целыми числами большими или равными 2.

8. В числителе и знаменателе переменные должны быть отсортированы по алфавиту.

Входные и выходные данные

В первой строке входного файла содержатся числа N и M (1  N, M  999), разделённые пробелами.

Следующие N + M строк содержат по одному одночлену каждая. Длина каждой строки не превосходит 100 символов.

В выходном файле должны быть две строки, содержащие соответственно числитель и знаменатель результата. Если после сокращения в числителе и/или в знаменателе не остаётся ни одной переменной, вместо одночлена следует вывести число 1.

Пример

Input.txt	Output.txt
2 1 x*x^7*x x*y*z y^2*z	x^10 y

Program sokrashenie;

Var a:array[1..256] of longint;

b:array[1..256] of longint;

n,m:integer;

procedure init;

begin

assign(input,'input.txt');

reset(input);

readln(n,m);

end;

procedure solve;

var i,j:integer;

st:string;

begin

for i:=1 to n do

begin

readln(st); считываем строку

for j:=1 to length(st) do двигаемся по строке

if st[j] in ['a'..'z','A'..'Z'] если символ буква

then inc(a[ord(st[j])]) считаем ее

else

begin

if st[j]='^' then если символ ^

begin

inc(a[ord(st[j-1])],ord(st[j+1])-ord('0')-1); прибавляем показатель степени

inc(j); переходим к следующему

cимволу

end;

end;

end;

for i:=1 to m do то же самое делаем для

числителя

begin

readln(st);

for j:=1 to length(st) do

if st[j] in ['a'..'z','A'..'Z'] then inc(b[ord(st[j])]) else

begin

if st[j]='^' then

begin

inc(b[ord(st[j-1])],ord(st[j+1])-ord('0')-1);

inc(j);

end;

end;

end;

for i:=1 to 256 do сокращаем дроби

if a[i]>b[i] then

begin

a[i]:=a[i]-b[i];

b[i]:=0;

end else begin

b[i]:=b[i]-a[i];a[i]:=0;

end;

end;

procedure out;

var i:integer;

p:boolean;

begin

assign(output,'output.txt');

rewrite(output);

p:=false; по этой логической переменной узнаем

будет ли в числителе 1 или нет

for i:=1 to 256 do

if a[i]<>0 then если буква с кодом i есть в числителе

begin

if p then write('*');

p:=true;

write(chr(i)); выводим букву

if a[i]>1 then write('^',a[i]); если показатель степени >1 выводим

end; ^ и показатель степени

if not p then write('1'); если в числителе нет букв, то выводим 1

writeln;

p:=false; то же самое в знаменателе

for i:=1 to 256 do

if b[i]<>0 then

begin

if p then write('*');

p:=true;

write(chr(i));

if b[i]>1 then write('^',b[i]);

end;

close(output);

end;

begin

init;

solve;

out;

end.

строкизадачи

Задача 5 Распаковка строчки

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.

Формат входных данных

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

Формат выходных данных

В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).

Примеры

Input.txt	Output.txt
3A4B7D	AAABBBBDDDDDDD
22D7AC18FGD	DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF FFFFFFFFGD
95AB	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAB
40AB39A	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA