Задача 4. Трапеза для героев Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
После очередной победы над пришельцами K героев одного известного фильма собрались вместе
в кафе. Среди героев есть правши и левши. Они хотят сесть за длинным прямоугольным столом с
одной стороны этого стола так им лучше наблюдать за происходящим в кафе. Места за столом
последовательно пронумерованы, всего за столом N мест. Герои могут садиться не рядом друг с
другом. За столом могут остаться свободные (незанятые) места. Если на соседних (расположенных
последовательно друг за другом) местах по правую руку от правши оказывается левша именно в
таком порядке, то им будет неудобно есть. Грут обеспокоен такой ситуаций и хочет узнать много
ли пар героев сидят неудобно.
Форматвходныхданных
В первой строке записано целое число N (1 6N 6106) количество мест за столом.
Во второй строке записано целое число K (1 6K 63 ·105) количество героев.
Далее следуют K строк, к каждой из которых содержится информация о соответствующем герое:
номер места, и 0 если герой - правша, или 1 если герой - левша.
Гарантируется, что номера мест всех героев попарно различны.
Форматвыходныхданных
Выведите одно целое число количество пар героев, которым неудобно сидеть за столом.
Системаоценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Ограничения
Подзадача K Дополнительные
ограничения
Необходимые
подзадачи
Информация о
проверке
0 0 Тесты из условия полная
1 20 1 6K 65 000 полная
2 20 1 6K 63 ·105 Количество левшей
не превосходит 100 первая ошибка
3 60 1 6K 63 ·105 1, 2 первая ошибка

Для начала давайте определим сколько памяти требуется для хранения одного символа. Для этого вспомним главную формулу информатики

Здесь i — количество бит на 1 символ, а N — количество различных символов. По условию задачи у нас всего 26 символов, значит подставим вместо N число 26 и получим

Теперь нужно понять чему равно i. Если i = 4, то 2 4 = 16. Т. е. 4 бита на 1 символ позволит закодировать 16 символов, а у нас их 26. Маловато будет.

Если i=5, то 2 5 = 32. На наши 26 символов этого хватит. Значит на 1 символ у нас будет приходится 5 бит информации.

Так как в пароле у нас 7 символов, то на 1 пароль потребуется 7*5 =35 бит памяти. В байтах это будет 35/8 = 4,375. Округлим в большую сторону (так как по условию «для

каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт») и получим, что на хранение пароля пользователя требуется 5 байт памяти.

Так как на 30 пользователей отводится 600 байт памяти, то на одного пользователя требуется 600/30 = 20 байт памяти. Из них 5 байт отводится для пароля. Следовательно для дополнительных сведений остается 20 — 5 = 15 байт.

Тема: «Системы программирования и прикладное программное обеспечение»

Тип урока: изучение нового материала.    

Цели урока:

1.     Образовательная – дать преставление о назначении программ, которые относятся к прикладному ПО; назначение систем программирования.

2.     Развивающая – развить информационную культуру и умения определять, к какому программному обеспечению относится конкретная программа.

3.     Воспитательная – воспитывать культуру работы в группе; воспитывать информационную культуру.

После изучения темы учащиеся должны

·       знать:

-         структуру программного обеспечения компьютера;

-         понятие и термины: программное обеспечение (ПО), базовое ПО, системное ПО, операционная система, интерфейс, драйвер, утилиты, прикладное ПО, системы программирования;

·       уметь:

-         отделять задачи системного характера от задач прикладного характера;

-         понимать с каких программных средств какие информационные задачи можно решать.

Объяснение: