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

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

HotLog


 

Обработка больших данных

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

В научной лаборатории разрабатывается новая архитектура суперкомпьютера, позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i. Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6] и [7, 7].

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

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые с1 ячеек памяти необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее, последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:

  • STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
  • STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
  • STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1], как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.

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

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

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30, 1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).

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

Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Пример

INPUT.TXTOUTPUT.TXT
13 3 2
1 1
2 2
5 1
3

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

 Язык программирования 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
 A. Улучшение успеваемости
 B. Квадраты и кубы
 C. Лифт
 D. Мониторинг труб
 E. Удаление чисел
 F. Старая книга
 G. Красота фейерверка
 H. Обработка больших данных

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483