Чемпионат КРОК 2012 - Финал |
---|
Закончено |
Сенсация, сенсация в двумерном государстве! Был пойман особо опасный преступник — один из членов знаменитой банды «Пихстеры». Как сообщает отдел по борьбе с преступностью, задержанный ехал на своей машине из главного штаба банды в киоск с мороженым, где и был пойман. Каждый объект двумерного государства (киоск с мороженым, машина, штаб) представляет собой точку на плоскости.
Машина преступника была оборудована GPS передатчиком. Данные передатчика показали, что на пути от штаба до киоска с мороженым машина совершила ровно n перемещений. За одно перемещение машина из точки (x, y) может попасть в одну из четырех точек: перемещение в точку (x - 1, y) будем обозначать буквой «L», в точку (x + 1, y) — «R», в точку (x, y - 1) — «D», в точку (x, y + 1) — «U».
Из-за большой погрешности GPS передатчик, установленный на машине, не сохраняет точную последовательность перемещений машины. Вместо точных перемещений в журнал GPS записываются возможные перемещения в виде одной из строк: «UL», «UR», «DL», «DR» или «ULDR». Каждая такая строка обозначает, что было совершено ровно одно перемещение, соответствующее какому-то одному символу строки. Например, строка «UL» обозначает, что было совершено либо перемещение «U», либо перемещение «L».
Вам задан журнал возможных перемещений преступника от штаба банды до киоска в хронологическом порядке. Зная, что киоск с мороженым находится в точке с координатами (0, 0), определите в скольки различных точках может находиться штаб банды (то есть, требуется найти количество возможных позиций старта машины).
В первой строке записано единственное целое число n (1 ≤ n ≤ 2·105) — количество перемещений машины от штаба до киоска.
Каждая из следующих n строк обозначает возможное перемещение машины. Гарантируется, что каждое возможное перемещение это одна из строк: «UL», «UR», «DL», «DR» или «ULDR».
Все перемещения заданы в хронологическом порядке.
Выведите единственное целое число — количество различных возможных положений штаба банды.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
3
UR
UL
ULDR
9
2
DR
DL
4
Рисунок ниже показывает девять возможных положений штаба банды из первого примера:
Например, из точки (1, 0), машина может доехать до точки (0, 0), совершая следующие перемещения:
Название |
---|