Ants
NOI.2012.K1.A.Ants
Time Limit: 0.5s, Memory Limit: 256MiB
Ели си има страхотен правоъгълен терариум в който гледа мравки. Тя го е разделила на N x M еднакви клетки, като първоначално в тях има KN * M мравки, разпроложени по такъв начин, че във всяка клетка има по не повече от една. Всяка клетка е свързана със съседните си по хоризонтала и вертикала (където има такива). Така вътрешните клетки са свързани с по 4 други, тези по краищата на терариума – с по 3, а тези в ъглите – по 2. Мравките се движат хаотично, като всяка минута всяка мравка избира някоя от съседните клетки и се премества там. Ако след преместването X мравки попаднат в една и съща клетка, то след сбиване и репродуциране в крайна сметка остават XX+1 % 8 мравки (остатъка на X на степен X+1 при деление на 8). Ако има две или повече мравки в една клетка, те могат да решат да се преместят в една и съща друга клетка. Забележете, че мравките винаги се местят, тоест никога не остават на място.

Ели прави живота на мравките дори по-труден. Всяка минута тя избира някой от крайните ненапръскани до сега редове или колони и го пръска с отрова. Мравките не са глупави животинки и успяват да избягат преди тя да ги е убила, като бягат само в клетки, които не са били пръскани до сега и не се пръскат в момента. Така те никога не умират от отровата, но почват да живеят във все по-стесняващ се регион, където, съответно, трябва да се бият с други мравки за територия. Ели продължава със забавната си игра докато не останат точно две клетки. Забележете, че тя не е чак толкова зла и никога не пръска ред, ако той е последният останал ред, или колона, ако тя е последната останала колона (в противен случай не биха останали 2 клетки).

Можем да си представим случващото се в терариума като игра в правоъгълник с N реда и М колони, в K от чиито клетки по случаен начин са разположени пионки. На всеки рунд се маркира за изтриване или най-горният ред, или най-долният ред, или най-лявата колона, или най-дясната колона. Всяка пионка се премества в някоя (случайна) съседна клетка, която не е маркирана за изтриване. След преместването на всички пионки, във всяка клетка се преброяват текущите такива, и ако техният брой е бил X, на тяхно място се поставят XX+1 % 8. След това се премахва маркираният за изтриване ред или колона. Това се повтаря докато не останат точно 2 клетки. Ели се пита какъв е очакваният брой мравки (пионки) в края на играта?
Вход
На първия ред на стандартния вход са зададени целите числа N, M и K. На втория ред чрез стринг с дължина N + M – 3 символа ще бъдат зададени редовете и колоните в реда, в който ги пръска Ели. Буква 'T' ще задава най-горен ред, 'B' ще задава най-долен ред, 'L' ще задава най-лява колона, а 'R' ще задава най-дясна колона.
Изход
На единствен ред на стандартния изход изведете едно реално число – очаквания брой мравки в края на играта. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N, M ≤ 50
  • 1 ≤ KN * M
  • 2 ≤ N * M
Примерен Вход Примерен Изход
1 5 2 LRR 1.2
6 3 2 LBLLTR 1.058823529
Мрън!