Crypto
Национална Олимпиада по Информатика 2010, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
След като получиха забележка в дневника „№5 и №13 отказват да седят отделно” и учителката неколкократно хвана кореспонденцията им и я прочете пред целия клас, Ели и Крис решиха да криптират съобщенията си.

Както при повечето шифри, Ели реши да кодират информацията си в числа. За целта тя дефинира k-нечетните числа. Едно число тя определя като k-нечетно, ако при деление на 2 (закръгляйки надолу) до достигане на 1 се получи последователност от k или повече поредни нечетни числа. Примерно числото 29 е 3-нечетно, тъй като редицата, която се образува при деление на 2 е {29, 14, 7, 3, 1}, а последователните числа 7, 3 и 1 са нечетни. Друг пример е 94, което образува редицата {94, 47, 23, 11, 5, 2, 1}. Забележете, че тук имаме не 3 а цели 4 поредни нечетни числа. Въпреки това 94 е както 4-нечетно, така и 3-нечетно (тъй като имаме 3 последователни нечетни). От друга страна 13 не е 3-нечетно, тъй като в редицата {13, 6, 3, 1} няма три последователни нечетни числа.

Важна характеристика за крипто-системата на двете приятелки е колко кодови числа има в даден интервал. Примерно в интервала [7, 42] има 9 3-нечетни числа, а именно 7, 14, 15, 23, 28, 29, 30, 31 и 39. Помогнете на Ели и Крис като напишете програма, която при даден интервал [A, B] и число K намира колко K-нечетни числа има между A и B, включително.
Вход
На първия ред на стандартния вход ще бъде дадено числото K. На следващия ред ще бъдат зададени съответно A и B, разделени с интервал.
Изход
На стандартния изход изведете едно единствено число – броя k-нечетни числа в интервала [A, B].
Ограничения
  • 1 ≤ K ≤ 100,000
  • 1 ≤ AB ≤ 10100
Примерен Вход Примерен Изход
3 7 42 9
2 1337 123456789 122941444
Мрън!