Однажды Боба изобрел странную машину времени, которая могла перемещаться назад во времени не более чем на x часов. Спустя некоторое время некая организация услышала об изобретении и похитила Бобу, чтобы он изобрел для них полноценную машину времени. Пупа, друг Бобы, решил вернуться в момент изобретения машины времени, чтобы товарища. До своего похищения Боба успел улучшить машину времени три раза. К сожалению, Пупа не умеет считать, поэтому просит вас подсчитать минимальное количество перемещений во времени, которое ему потребуется для предотвращения похищения друга.
Входные данные
Первая строка содержит единственное целое число x(1≤x≤106−3) — максимальное количество часов, на которое можно осуществить перемещения во времени на момент изобретения машины времени.
Вторая строка содержит две даты s и e (01.01.1950≤s
Следующие три строки содержат информацию об улучшениях, которая включает дату улучшения qi (s
Все даты даны в формате «DD.MM.», где DD — день, MM — месяц, — год. Во вселенной Бобы и Пупы в любом году 12 месяцев, в любом месяце 30 дней, в любом дне 24 часа.
Считать, что изобретение машины времени и все события ее улучшения происходили в полдень.
Считать, что свой первый прыжок Пупа делает в полдень.
Для лучшего понимания хронологии событий смотрите примечание.
Выходные данные
Выведите одно целое число — минимальное количество перемещений во времени, которое необходимо сделать, чтобы вернуться в момент изобретения машины времени.
Система оценки
Максимальный за задачу: 100.
Пример
входные данные
24
23.10.2020 23.12.2020
29.10.2020 28
23.11.2020 64
12.12.2020 85
выходные данные
36
Примечание
Пояснение ко входным данным примера.
Пупа должен отправиться в в 12:00 23.12.2020 года. Он за некоторое количество прыжков должен попасть в 12:00 23.10.2020 года.
На интервале с 12:00 23.10.2020 года до 12:00 23.12.2020 года машина времени была улучшена три раза.
Первое улучшение было сделано в 12:00 29.10.2020 года.
Второе улучшение было сделано в 12:00 23.11.2020 года.
Третье улучшение было сделано в 12:00 12.12.2020 года.
Это означает, что любой прыжок из точки времени между 12:00 23.10.2020 года и 11:59 29.10.2020 года может быть выполнен на 24 и менее часов назад. Любой прыжок из точки времени между 12:00 29.10.2020 года и 11:59 23.11.2020 года может быть выполнен на 28 и менее часов назад. Любой прыжок из точки времени между 12:00 23.11.2020 года и 11:59 12.12.2020 года может быть выполнен на 64 и менее часов назад. Любой прыжок из точки времени после 12:00 12.12.2020 года может быть выполнен на 85 и менее часов назад.
Месяц находим методом половинного деления.
Двоичная запись числа 366 размещается в 9 битах (в 8 битах размещается только 256 чисел , а в 9 битах - уже 512).
То есть , понадобится задать 8 вопросов и девятой фразой будет ответ.
В году 365 (366) дней. Пусть 366, для 365 рассуждение то же.
Рассмотрим самый худший вариант
Середина года - день номер 366/2=183. Это 1 июля.
Первый вопрос: День рождения в первой половине года?
Допустим, да.
Второй вопрос: День рождения в первом квартале?
Допустим, нет. Следовательно во втором.
Второй квартал - это дни с номерами от 92 до 182. Середина - среднее арифметическое. (92+182)/2=137. Это дата 17 мая.
Третий вопрос: День рождения позднее 17 мая?
Допустим, нет.
Следовательно, интервал дат 1 апреля - 17 мая, 91 день. Опять делим на 2, сужая интервал до 22 дней. Это дата 22 апреля.
Четвертый вопрос: День рождения позднее 22 апреля?
Допустим, нет.
Новый диапазон поиска - 23 апреля - 17 мая. Половиним его.
Пятый вопрос: День рождения позднее 29 апреля?
Допустим, нет.
Поиск сузился до 23 - 29 апреля. Снова берем половину.
Шестой вопрос: День рождения позднее 26 апреля?
Допустим, нет.
Интервал дат 23-26 апреля. Половиним.
Седьмой вопрос: День рождения позднее 24 апреля?
Допустим, да.
Интервал дат 25-26 апреля.
Восьмой вопрос: День рождения 25 апреля?
Допустим, нет
Девятая фраза: Ваш день рождения 26 апреля.
#include <cstdlib>
#include <ctime>
int main()
{
using namespace std;
cout << "Enter size of array: ";
int N;
cin >> N;
int * ARR = new int[N];
srand(time(0));
int i;
for (i = 0; i < N; ++i)
ARR[i] = rand() % 100 + 1;
cout << "Here is an original array:\n";
for (i = 0; i < N; ++i)
cout << ARR[i] << " ";
cout << endl;
int temp = ARR[N - 1];
for (i = N - 1; i > 0; --i)
ARR[i] = ARR[i - 1];
ARR[0] = temp;
cout << "\nHere is a new array:\n";
for (i = 0; i < N; ++i)
cout << ARR[i] << " ";
cout << endl;
return 0;
}