Дистанционная подготовка: Задача на бинарный поиск с acm.timus.ru
Задача на бинарный поиск с acm.timus.ru
от Роман Захаров - Вторник 13 Ноябрь 2007, 11:09
  Вот собственно сама задача она из тимуса
http://acm.timus.ru/problem.aspx?space=1&num=1564
вот сам текст условия:
Петя захотел подняться на верхний этаж небоскрёба Антей по лестнице и ради интереса стал считать единицы в табличках с номером этажа. Добраться до конечной цели Пете не удалось, так как по пути на одном из лестничных пролётов его хватил удар. Когда он очнулся в больнице, то помнил только количество посчитанных единиц. Теперь ему хочется узнать, до какого этажа он успел дойти перед тем как попасть в больницу. Но поскольку точно это определить невозможно, его устроит этаж, на котором он успел сосчитать последнюю единицу.

Исходные данные

В первой строке записано количество единиц, которое насчитал Петя, — целое число от 1 до 1018.

Результат

Выведите номер этажа, на котором Петя сосчитал последнюю единицу. Если названное им количество единиц некорректно, то выведите «Petr lies».

Примеры


исходные данные
результат
4 
11 
3 
Petr lies 

теперь раскажу как я понимаю её
вроде бы садача простая и решается бинарным поиском следущим образом
[code]
min=0;max=10^18+1;f=false;
while(min<=max)and not f do begin
mid:=(min+max) div 2;
if fun(mid)=n then f:=true
else if fun(mid)<n then min:=mid
else max:=mid;
end;
if not f then writeln('Petr lies')
else writeln(mid);
[/code]
это всё ясно не понятно для меня одно как написать функцию fun(mid) которая подсчитывает количество ед. в числах из интервала 1-mid как её написать я затрудняюсь плиз подскажите!

(Редактировал(а) Владимир Гуровиц, Понедельник 12 Ноябрь 2007, 22:16)

Re: Задача на бинарный поиск с acm.timus.ru
от Владимир М. Гуровиц - Вторник 13 Ноябрь 2007, 11:10
 

Ничего совсем уж простого я не знаю, с ходу приходят два способа.

1. Подсчитаем, сколько раз единица встречается на i-й позиции во всех числах от 1 до mid и сложим. Например, единица на первой справа позиции встречается в кажом 10-м числе, единица на второй позиции встречается в каждых 10 из 100 чисел (грубо, точнее надо над этим аккуратно подумать и написать формулу).

2. Подсчитаем, сколько раз встречается единица в числах от 000..00 до 999..99 (нули слева дописываем для однородности): ясно, сколько цифр всего в этих числах. а единиц - ровно 1/10 от них, потому что каждая цифра встречается одинаковое количество раз.

А дальше режем наш отрезок на подобные куски, и считаем на каждом куске. Скажем, если mid=1234, то отрезки будут такие: 0..999, 1000-1099,1100..1199, 1200..1209, 1210..1219, 1220..1229, ну и отдельно - хвостик 1230..1234

Подумайте над одной их эти идей, если ничего не получится, я напишу подробнее.

Re: Задача на бинарный поиск с acm.timus.ru
от Роман Захаров - Четверг 15 Ноябрь 2007, 01:19
  Разобрался спасибо!!!Улыбка