Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Робот-пылесос

(Время: 2 сек. Память: 128 Мб Сложность: 54%)

Рассмотрим координатную плоскость, которую планируется очищать с использованием робота-пылесоса. Робот-пылесос представляет собой квадрат размером k×k со сторонами, параллельными осям координат. Изначально левый нижний угол робота находится в точке (0, 0), а правый верхний, соответственно – в точке (k, k).

Вам дана последовательность из n перемещений робота по плоскости, i-е перемещение характеризуется направлением di, принимающим значения 'N' (вверх, увеличение координаты Y ), 'S' (вниз, уменьшение координаты Y ), 'W' (влево, уменьшение координаты X) или 'E' (вправо, увеличение координаты X), и целым числом ai – расстоянием, на которое робот перемещается.


На рисунке приведены примеры возможных перемещений робота в каждом направлении.

Робот в каждый момент времени убирает всю площадь под собой. Иными словами, точка считается убранной тогда и только тогда, когда она в какой-то момент времени принадлежала квадрату размера k×k, на котором находился робот.

По заданным перемещениям робота посчитайте суммарную площадь всей убранной поверхности.

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

В первой строке входного файла INPUT.TXT через пробел даны два целых числа: размер робота k и количество команд n (1 ≤ k ≤ 104; 1 ≤ n ≤ 105).

В i-й из следующих n строк через пробел даны направление i-го перемещения di и его расстояние ai (di – буква 'N', 'S', 'W' или 'E'; 1 ≤ ai ≤ 109).

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

В выходной файл OUTPUT.TXT выведите суммарную площадь убранной роботом поверхности.

Примеры

INPUT.TXTOUTPUT.TXT
11 5
E 2
N 2
W 4
S 4
E 4
17
23 4
W 2
N 1
W 1
N 2
27

Пояснения к примерам

Ниже приведены иллюстрации к перемещениям робота согласно примерам из условия. Клетки, которые робот посетил за время своих перемещений, затемнены.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Разделение прямоугольника
 B. Произведение Фибоначчи
 C. Робот-пылесос
 D. Разноцветные точки
 E. Метрострой
 F. Красивые последовательности
 G. Камни
 H. Обыкновенная задача про строки

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru