Обсуждение @ 1055. Сочетания @ Timus Online Judge

luckysundog tests [1] // Задача 1055. Сочетания 16 дек 2011 12:31

Ilya What answer if N<M ? [1] // Задача 1055. Сочетания 2 июн 2011 17:25

inatial_D the problem is not worth difficuity 349.. it's almost same as 1049. // Задача 1055. Сочетания 7 апр 2013 08:24

Abzal WA5 [2] // Задача 1055. Сочетания 22 авг 2011 15:46

nguyenductam Why WA in test 2. My code here. Please help me. [2] // Задача 1055. Сочетания 5 апр 2010 10:15

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

long int i,j,n,m,aa,bb,cc,lap,k,l;
int a[50001],sont;
int dem[50001];
long int kq;

void InitPrime();
long int Max(long int x,long int y);
long int Min(long int x,long int y);
void InitDem();
void Test();

int main()
{
    scanf("%ld %ld",&n,&m);
    aa=Max(n,m);
    bb=Min(n,m);
    cc=aa-bb;

    InitDem();
    InitPrime();
//   Test();

    lap=Max(bb,cc);
    i=lap+1;
    // tinh so nguyen to o tren tu
    while(i<=aa)
    {
           k=0;
           l=i;
           while(l!=1)
           {
            k++;
            while((l%a[k])==0)
            {
             l=l/a[k];
             dem[a[k]]++;
            }
           }
           i++;
    }

    // tinh so nguyen to duoi mau
    lap=Min(bb,cc);
    i=2;
    // tinh so nguyen to o tren tu
    while(i<=lap)
    {
           k=0;
           l=i;
           while(l!=1)
           {
            k++;
            while((l%a[k])==0)
            {
             l=l/a[k];
             dem[a[k]]--;
            }
           }
           i++;
    }

    //dem ket qua
    kq=0;
    i=2;
    while(i<=aa)
    {
     if(dem[i]!=0) kq+=dem[i];
     i++;
    }
    printf("%ld",kq);

    getch();
    return 0;
}

void InitDem()
{
i=1;
while(i<=aa)
{
dem[i]=0;
i++;
}
}

long int Max(long int x,long int y)
{
if(x<=y) return y;
return x;
}

long int Min(long int x,long int y)
{
if(x<=y) return x;
return y;
}

void InitPrime()
{
     int flag;
     long int x;
     a[1]=2;
     a[2]=3;
     a[3]=5;
     a[4]=7;
     i=4;
     x=11;
     while(x<aa+1)
     {
                   j=2;
                   flag=1;
                   while(j*j<x)
                   {
                    if(x%j==0)
                    {
                     flag=0;
                     break;
                    }
                    j++;
                   }
                   if(flag==1)
                   {
                     a[++i]=x;
                   }
                   x+=2;
     }
     sont=i;
}
void Test()
{
for(i=1;i<=sont;i++) printf("%d\n",a[i]);
// getch();
}

Varun Sharma Re: Why WA in test 2. My code here. Please help me. [1] // Задача 1055. Сочетания 6 апр 2010 14:23

Hi,

Try these test cases:

Test Cases

200000 40000
9011

100000 35000
6109

123456 12345
3892

987654 98765
25861

560011 12000
5255

340999 43560
11372

235000 34001
8723

89340 10000
3123

98112 23
35

4567 456
212

Varun

TheDreamCatcher Re: Why WA in test 2. My code here. Please help me. // Задача 1055. Сочетания 1 дек 2010 13:47

Varun Sharma писал(a) 6 апреля 2010 14:23

Hi,

Try these test cases:

Test Cases

200000 40000
9011

100000 35000
6109

123456 12345
3892

987654 98765
25861

560011 12000
5255

340999 43560
11372

235000 34001
8723

89340 10000
3123

98112 23
35

4567 456
212

Varun

N M between 1 & 50 000

And IV <TOP SECRET> 15 лет колоний и лагерей будет [2] // Задача 1055. Сочетания 29 июн 2007 21:05

rongyan why I get crash(access violation) at test 6? [5] // Задача 1055. Сочетания 13 сен 2006 18:15

Phan Hoài Nam - Đại học Ngoại ngữ Tin Học TP.HCM The algorithm for solving this problem. EASY TO UNDERSTAND ! [1] // Задача 1055. Сочетания 5 фев 2009 09:07

Rasul please give me some tests. [1] // Задача 1055. Сочетания 26 окт 2009 16:13

Shyu SeiMin WA#3 // Задача 1055. Сочетания 17 май 2009 11:55

Vasil Todorov I have a misstake pls help! // Задача 1055. Сочетания 19 фев 2009 02:06

Valentin Baltadjiev Need help. Solution too slow. Code included // Задача 1055. Сочетания 19 фев 2009 01:13

ooo help me!!!!!! // Задача 1055. Сочетания 14 дек 2008 16:08

ooo where is my mistake? // Задача 1055. Сочетания 8 дек 2008 21:10

Gerasim Petrov Velchev My Solution is SUPER! // Задача 1055. Сочетания 24 июл 2008 15:25

Vlad Ionescu How can I sol;ve this faster? [2] // Задача 1055. Сочетания 10 июн 2003 02:16

My program run in 0.741 seconds and i saw most people only needed
0.09s. How can i solve this any faster?

var d:array[1..50000] of integer;
    n,m,i,j,k:longint;
begin
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=m+1 to n do begin
      k:=i;
      for j:=2 to trunc(sqrt(k)) do
          while k mod j=0 do begin
                inc(d[j]); k:=k div j;
                end;
      if k<>1 then inc(d[k]);
      end;
for i:=1 to n-m do begin
      k:=i;
      for j:=2 to trunc(sqrt(k)) do
          while k mod j=0 do begin
                dec(d[j]); k:=k div j;
                end;
      if k<>1 then dec(d[k]);
      end;
k:=0;
for i:=2 to n do
      if d[i]>0 then inc(k);
writeln(k);
end.

Evil Cheater Re: How can I sol;ve this faster? [1] // Задача 1055. Сочетания 10 июн 2003 20:41

> My program run in 0.741 seconds and i saw most people only needed
> 0.09s. How can i solve this any faster?
>
> var d:array[1..50000] of integer;
>     n,m,i,j,k:longint;
> begin
>   fillchar(d,sizeof(d),0);
>   readln(n,m);
>   for i:=m+1 to n do begin
>       k:=i;
>       for j:=2 to trunc(sqrt(k)) do
>           while k mod j=0 do begin
>                 inc(d[j]); k:=k div j;
>                 end;
>       if k<>1 then inc(d[k]);
>       end;
>   for i:=1 to n-m do begin
>       k:=i;
>       for j:=2 to trunc(sqrt(k)) do
>           while k mod j=0 do begin
>                 dec(d[j]); k:=k div j;
>                 end;
>       if k<>1 then dec(d[k]);
>       end;
>   k:=0;
>   for i:=2 to n do
>       if d[i]>0 then inc(k);
>   writeln(k);
> end.
>

SkorKNURE Re: How can I sol;ve this faster? // Задача 1055. Сочетания 26 апр 2008 21:07

0.001s, 336kb.
Use following fact from the number theory:
Power of each prime in binomial coefficient's factorization equals to the number of borrows in the substraction n-k in base p. Iterate all primes less then N and count it if prime will greater then 0;

Viktor what is problem in my programmmmmmmmmmmmmmmmm // Задача 1055. Сочетания 4 янв 2008 17:13

Chojin My C code submited as C++ ,then got "complilation error"?why? // Задача 1055. Сочетания 5 окт 2007 09:40

Orshanskiy Sergey :) [3] // Задача 1055. Сочетания 4 ноя 2002 05:39

xcheng Hints for those who got TLE~ // Задача 1055. Сочетания 4 сен 2007 19:46

Обсуждение задачи 1055. Сочетания