Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.05.2008, 21:16
ZRCsoll

 
Сообщений: n/a

Количество нулей
Решаю задачу в что-то не получается( помогите пожалуйста
она из Саратовского сайта виртуальные контесты школьный четверть финал 2002г.
приведу на русском языке
на вход подаётся единственное число q это количество нулей в факториале
на выход надо вывести факториал числа имеющий столько нулей т.е
факториалом числа n называется N!=1*2*3*...(N-1)*N;
5!=120;если решения нет вывести No solution
ввод
1
2
вывод
5
10
я рассуждал так. количество нулей в факториале зависит от количества 5 в нём тогда
Код:
var i,q,cnt:int64;
    Ok:boolean;

function num(i:int64):int64;
begin
  result:=0;
  while i>0 do begin
    result:=result+integer(boolean((i mod 5)<>0));
    i:=i div 5;
  end;
end;

begin
  readln(q);
  i:=0;cnt:=0;ok:=False;
  while true do begin
    i:=i+1;
    cnt:=cnt+num(i);
    if cnt=q then begin ok:=true;break;end;
    if cnt>1 then break;
  end;
  if ok then writeln(i)
  else writeln('No solution');
  { TODO -oUser -cConsole Main : Insert code here }
end.
  #2  
Старый 24.05.2008, 22:00
ZRCsoll

 
Сообщений: n/a

при копировании кода я нечай но нажал на 1 и вместо = поставил <> вот правильный код, ну не правильный а мой который я придумал он валится на 4-ом тесте не пойму в чём дело(
Код:
var i,q,cnt:int64;
    Ok:boolean;

function num(i:int64):int64;
begin
  result:=0;
  if i mod 5 <>0 then exit;
  while i>0 do begin
    result:=result+integer(boolean((i mod 5)=0));
    i:=i div 5;
  end;
end;

begin
  readln(q);
  i:=0;cnt:=0;ok:=False;
  while true do begin
    i:=i+1;
    cnt:=cnt+num(i);
    if cnt=q then begin ok:=true;break;end;
    if cnt>q then break;
  end;
  if ok then writeln(i)
  else writeln('No solution');
end.
  #3  
Старый 24.05.2008, 23:55
гость

 
Сообщений: n/a

Количесвто нулей в конце десятичной записи факториала - число пятерок в его разложении на простые числа, здеcь все правильно. Вот только ваша фукнция num() считает что-то совершенно другое. По-моему, правильнее будет так:
Код:
function num(i:int64):int64;
begin
  result:=0;
  while (i mod 5) = 0 do inc(result);
end;
И в следующий раз не забывайте приводите ссылку на задачу.
  #4  
Старый 24.05.2008, 23:56
гость

 
Сообщений: n/a

Упс...

while (i mod 5) = 0 do begin inc(result); i := i div 5; end;
  #5  
Старый 25.05.2008, 01:56
ZRCsoll

 
Сообщений: n/a

http://acm.sgu.ru/problem.php?contest=0&problem=154
это ссылка
да про код вы правы у меня он реализован менее эфф. чем это сделали вы.
что-то не понятно про 5-ки это я знаю, но вот если это реализовать то по времени не пройдёт
  #6  
Старый 25.05.2008, 03:11
гость

 
Сообщений: n/a

ok, с такими ограничениями тебе нужен двоичный поиск и такая формула для числа пятерок в n!:
(n div 5) + ((n div 5) div 5) + (((n div 5) div 5) div 5) + ... (до тех пор по не дойдешь до нюля)
  #7  
Старый 25.05.2008, 03:13
гость

 
Сообщений: n/a

Сообщение от ZRCsoll Посмотреть сообщение
да про код вы правы у меня он реализован менее эфф. чем это сделали вы.
речь была не об эффективности (он все равно бы не прошел по времени на следующих тестах), а о корректности. Ваш вариант не работает.
  #8  
Старый 25.05.2008, 07:07
ZRCsoll

 
Сообщений: n/a

не совсем понял как же мне уту формулу записать поясните пожалуйста подробней а то я что-то не совсем понимаю(
  #9  
Старый 25.05.2008, 07:26
гость

 
Сообщений: n/a

Ну да хотя бы так:
Код:
function f(n: int64): int64;
begin
  if n = 0 then f := 0 else f := n div 5 + f(n div 5);
end;
или эквивалентным циклом, разница невелика.

f(n) возращает число нулей в конце n!

Тебе остается только найти с помощью двоичного поиска где f(n) принимает заданное значение. Двоичный поиск применим т.к. f(n) монотонно возрастает.
  #10  
Старый 25.05.2008, 16:30
ZRCsoll

 
Сообщений: n/a

Да я думал над этим бинарный поиск мне тоже показалось самым оптимальным только мне не совсем ясно как сделать оценку правого числа ну для бин. поиска L:=0; R:=...; вот тут я не сообразил можно конечно поставить число какое-нить заведомо во много раз больше но считать тогда будет дольше ну я например ставил 10^8, но у меня не прошла видимо из-за того что я функцию подсчёта не правильно реализовал это да
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
количество букв? гость Сортировка и поиск 5 20.05.2008 09:46
Без 2-х нулей гость Задачи 14 10.05.2008 12:16
количество вариантов размещения шаров в корзинах BreakPoint Математические алгоритмы (другое) 10 11.07.2007 12:24
разместить максимальное количество кругов в прямоугольнике ibobak Задачи 2 01.03.2007 00:28
разместить максимальное количество кругов в прямоугольнике ibobak Вычислительная геометрия 1 25.02.2007 18:05