Корова по имени Бесик красит забор Фермеру Арсену. Бесик начинает в позиции 0 и выполняет последовательность из N операции. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо. Бесик может уйти не далее чем на 109 единиц от исходной точки.
По имеющей инструкции Арсен хочет узнать область забора, которая покрашена как минимум двумя слоями краски.
Входные данные
В первой строке дается число N(1≤N≤105). Далее каждая из N строк описывает одну из N инструкций.
Выходные данные
Выведите ответ на задачу
Пример
входные данныеСкопировать
6
2 R
6 L
1 R
8 L
1 R
2 R
выходные данныеСкопировать
6
Любой язык
ответ:Доброго времени суток, уважаемые читатели Хабра!
Не так давно я написал свою первую статью на Хабр. В моей статье была одна неприятная шероховатость, которую моментально обнаружили, понимающие в сетевом администрировании, пользователи. Шероховатость заключается в том, что я указал неверные IP адреса в лабораторной работе. Сделал это я умышленно, так как посчитал что неопытному пользователю будет легче понять тему VLAN на более примере IP, но, как было, совершенно справедливо, замечено пользователями, нельзя выкладывать материал с ключевой ошибкой.
В самой статье я не стал править эту ошибку, так как убрав её будет бессмысленна вся наша дискуссия в 2 дня, но решил исправить её в отдельной статье с указание проблем и пояснением всей темы.
Для начала, стоит сказать о том, что такое IP адрес.
IP-адрес — уникальный сетевой адрес узла в компьютерной сети, построенной на основе стека протоколов TCP/IP (TCP/IP – это набор интернет-протоколов, о котором мы поговорим в дальнейших статьях). IP-адрес представляет собой серию из 32 двоичных бит (единиц и нулей). Так как человек невосприимчив к большому однородному ряду чисел, такому как этот 11100010101000100010101110011110 (здесь, к слову, 32 бита информации, так как 32 числа в двоичной системе), было решено разделить ряд на четыре 8-битных байта и получилась следующая последовательность: 11100010.10100010.00101011.10011110. Это не сильно облегчило жизнь и было решение перевести данную последовательность в, привычную нам, последовательность из четырёх чисел в десятичной системе, то есть 226.162.43.158. 4 разряда также называются октетами. Данный IP адрес определяется протоколом IPv4. По такой схеме адресации можно создать более 4 миллиардов IP-адресов.
Максимальным возможным числом в любом октете будет 255 (так как в двоичной системе это 8 единиц), а минимальным – 0.
Далее давайте разберёмся с тем, что называется классом IP (именно в этом моменте в лабораторной работе была неточность).
IP-адреса делятся на 5 классов (A, B, C, D, E). A, B и C — это классы коммерческой адресации. D – для многоадресных рассылок, а класс E – для экспериментов.
Класс А: 1.0.0.0 — 126.0.0.0, маска 255.0.0.0
Класс В: 128.0.0.0 — 191.255.0.0, маска 255.255.0.0
Класс С: 192.0.0.0 — 223.255.255.0, маска 255.255.255.0
Класс D: 224.0.0.0 — 239.255.255.255, маска 255.255.255.255
Класс Е: 240.0.0.0 — 247.255.255.255, маска 255.255.255.255
Теперь о «цвете» IP. IP бывают белые и серые (или публичные и частные). Публичным IP адресом называется IP адрес, который используется для выхода в Интернет. Адреса, используемые в локальных сетях, относят к частным. Частные IP не маршрутизируются в Интернете.
Публичные адреса назначаются публичным веб-серверам для того, чтобы человек смог попасть на этот сервер, вне зависимости от его местоположения, то есть через Интернет. Например, игровые сервера являются публичными, как и сервера Хабра и многих других веб-ресурсов.
Большое отличие частных и публичных IP адресов заключается в том, что используя частный IP адрес мы можем назначить компьютеру любой номер (главное, чтобы не было совпадающих номеров), а с публичными адресами всё не так Выдача публичных адресов контролируется различными организациями.
Допустим, Вы молодой сетевой инженер и хотите дать доступ к своему серверу всем пользователям Интернета. Для этого Вам нужно получить публичный IP адрес. Чтобы его получить Вы обращаетесь к своему интернет провайдеру, и он выдаёт Вам публичный IP адрес, но из рукава он его взять не может, поэтому он обращается к локальному Интернет регистратору (LIR – Local Internet Registry), который выдаёт пачку IP адресов Вашему провайдеру, а провайдер из этой пачки выдаёт Вам один адрес. Локальный Интернет регистратор не может выдать пачку адресов из неоткуда, поэтому он обращается к региональному Интернет регистратору (RIR – Regional Internet Registry). В свою очередь региональный Интернет регистратор обращается к международной некоммерческой организации IANA (Internet Assigned Numbers Authority). Контролирует действие организации IANA компания ICANN (Internet Corporation for Assigned Names and Numbers). Такой сложный процесс необходим для того, чтобы не было путаницы в публичных IP адресах.
Объяснение: