Editorial for VM 08 Bài 12 - Số 0 tận cùng


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const max=10000;
var a:array['a'..'z'] of longint;
    u2,u5:array[0..max] of longint;
    re,n:longint;

procedure rf;
var c:char;
begin
     fillchar(a,sizeof(a),0);
     n:=0;
     while not eoln do
     begin
          inc(n);
          read(c);
          inc(a[c]);
     end;
end;

procedure init;
var i,j:integer;
begin
     fillchar(u2,sizeof(u2),0);
     fillchar(u5,sizeof(u5),0);
     for i:=1 to max do
     begin
          j:=i;
          u2[j]:=u2[j-1];
          while j mod 2 = 0 do
          begin
               j:=j div 2;
               inc(u2[i]);
          end;
     end;
     for i:=1 to max do
     begin
          j:=i;
          u5[j]:=u5[j-1];
          while j mod 5 = 0 do
          begin
               j:=j div 5;
               inc(u5[i]);
          end;
     end;
end;

procedure pr;
var c:char; k,t2,t5:longint;
begin
     init;
     t2:=0; t5:=0; re:=0;
     for c:='a' to 'z' do
         if a[c]>0 then
         begin
              k:=a[c];
              t2:=t2+u2[n]-u2[k]-u2[n-k];
              t5:=t5+u5[n]-u5[k]-u5[n-k];
              n:=n-a[c];
         end;
     if t2>t5 then re:=t5 else re:=t2;
end;

procedure wf;
begin
     write(re);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

program digit0;
uses    math;
const   fi='';
var     mu:array[1..6] of longint;
        mu2:array[1..14] of longint;
        ch:array['a'..'z'] of longint;
        inp:text;
        c:char;
        n:longint;
        s:ansistring;
        res1,res2:int64;
procedure input;
var     c:char;
begin
        assign(inp,fi);
        reset(inp);
        n:=0;
        readln(inp,s);
        n:=length(s);
        close(inp);
end;

procedure init;
var     i:longint;
begin
        mu[1]:=5;
        for i:=2 to 6 do
        begin
                mu[i]:=mu[i-1]*5;
        end;
        mu2[1]:=2;
        for i:=2 to 14 do mu2[i]:=mu2[i-1]*2;
        for i:=1 to n do

                inc(ch[s[i]]);
end;

function calc(k:longint):longint;
var     i,t:longint;
begin
        i:=1;
        t:=0;
        while mu[i]<=k do
        begin
                inc(t,trunc(k/mu[i]));
                inc(i);
        end;
        exit(t);
end;


function calc2(k:longint):longint;
var     i,t:longint;
begin
        i:=1;
        t:=0;
        while mu2[i]<=k do
        begin
                inc(t,trunc(k/mu2[i]));
                inc(i);
        end;
        exit(t);
end;

begin
        input;
        init;
        res1:=calc(n);
        res2:=calc2(n);
        for c:='a' to 'z' do
        begin
                if ch[c]>=5 then
                dec(res1,calc(ch[c]));
                if ch[c]>=2 then dec(res2,calc2(ch[c]));
        end;
        write(min(res1,res2));
end.

Code mẫu của RR

uses math;
var
  a:ansistring;
  lt2,lt5,i,n:longint;
  c:char;
  cnt:array['a'..'z'] of longint;

function get(n,k:longint):longint;
    begin
      if n<k then exit(0);
      exit(n div k+get(n div k,k));
    end;

begin
  readln(a); n:=length(a);
  for i:=1 to n do
    inc(cnt[a[i]]);
  lt2:=get(n,2);
  for c:='a' to 'z' do
    lt2:=lt2-get(cnt[c],2);

  lt5:=get(n,5);
  for c:='a' to 'z' do
    lt5:=lt5-get(cnt[c],5);
  writeln(min(lt2,lt5));
end.

Code mẫu của hieult

#include <stdio.h>
#include <string.h>
//#include <conio.h>

int min(int a,int b)
{
    if(a>b) return b;
    return a;
}
main()
{
char s[10001];
int n,a[123],m=0,h=0;
gets(s);
n=strlen(s);
if(n==0)
    printf("1");
else
{
for(int i=97;i<=122;i++)
  {
  a[i]=0;
  for(int j=0;j<n;j++)
    if(s[j]==("%c",i))
      a[i]++;
  }

int k=n;
while(k!=0)
  {
  k=k/5;
  m+=k;
  }

for(int i=97;i<=122;i++)
{
   k = a[i];
  while(k!=0)
    {
    k=k/5;
    m=m-k;
    }
}
k = n;
while(k!=0)
  {
  k=k/2;
  h+=k;
  }

for(int i=97;i<=122;i++)
{
   k = a[i];
  while(k!=0)
    {
    k=k/2;
    h=h-k;
    }
}

printf("%d",min(m,h));
}
//getch();
}

Code mẫu của ll931110

Program DIGIT0;
        Const
                input  = '';
                output = '';
        Var
                F: array['a'..'z'] of longint;
                s: ansistring;
                n: longint;

Procedure init;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);

                        Readln(fi, s);
                        n:= length(s);
                        For i:= 1 to n do inc(F[s[i]]);

                Close(fi);
          End;

Function divsum(n,k: longint): longint;
         Var
                  t: longint;
                res: longint;
         Begin
                res:= 0;
                t:= 1;

                While t <= n do
                        Begin
                                t:= t * k;
                                res:= res + n div t;
                        End;

                divsum:= res;
         End;

Procedure solve;
          Var
                   fo: text;
                   ch: char;
                c2,c5: longint;
          Begin
                c2:= divsum(n,2);
                For ch:= 'a' to 'z' do c2:= c2 - divsum(F[ch],2);

                c5:= divsum(n,5);
                For ch:= 'a' to 'z' do c5:= c5 - divsum(F[ch],5);

                Assign(fo, output);
                        Rewrite(fo);
                        If c2 > c5 then writeln(fo, c5) else writeln(fo, c2);
                Close(fo);
          End;

Begin
        init;
        solve;
End.

Code mẫu của skyvn97

#include<stdio.h>
#include<string.h>
#define MAX   10101
int a[33];
int n;
int n2,n5;
int p2[MAX];
int p5[MAX];
char s[MAX];
void process(void)
{
    int i,j;
    scanf("%s",s);
    n=strlen(s);    
    for (i=1;i<=30;i=i+1) a[i]=0;
    n2=0;
    n5=0;
    for (i=1;i<=n;i=i+1)
        {
            a[s[i-1]-'a'+1]++;
            if (i%2==0) p2[i]=p2[i/2]+1;
            else p2[i]=0;
            if (i%5==0) p5[i]=p5[i/5]+1;
            else p5[i]=0;           
            n2=n2+p2[i];
            n5=n5+p5[i];
        }
    for (i=1;i<=30;i=i+1)
        for (j=1;j<=a[i];j=j+1)
            {
                n2=n2-p2[j];
                n5=n5-p5[j];
            }
    if (n2>n5) printf("%d",n5);
    else printf("%d",n2);
}
int main(void)
{
    process();
}

Code mẫu của khuc_tuan

#include <cstdio>
using namespace std;

char a[10010];
int dem[26], n;
int sl5[10010], sl2[10010];

int main() {
    gets(a);
    for(int i=0;a[i]!=0;++i) ++dem[a[i]-'a'], ++n;
    #define doit(A,B) { for(int i=1;B*i<=n;++i) A[B*i] = A[i] + 1; for(int i=1;i<=n;++i) A[i] += A[i-1]; }
    doit(sl5,5)
    doit(sl2,2)
    #define get(r,A) { r = A[n]; for(int i=0;i<26;++i) r -= A[dem[i]]; }
    int r2, r5;
    get(r2,sl2)
    get(r5,sl5)
    printf("%d\n", r2<r5?r2:r5);
    return 0;   
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.