294 - Divisors

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower » Thu Jan 24, 2002 4:16 am

man, i solved that problem, i tested it with all the possible numbers, and i got a program of a friend of mine, we have the same results, but MY PROGRAM isnt being accepted, and his prg is being accepted, we dont know why!! i am posting my code here, can u guys help me seeing any problem at it??






#include <math.h>
#include <stdio.h>

main()
{
long int max,k, i, q, j, maior , maior_n,fim[900],inicio[900];
float raiz;

maior_n = maior = q = 0;

scanf("%d",&max);

for(k = 0; k < max ; k++)
scanf("%d %d",&inicio[k],&fim[k]);

for(k = 0; k < max ; k++)
{
for(j=inicio[k] ; j < (fim[k] + 1) ; j++)
{
raiz = sqrt(j);
for(i=1 ; i < raiz ; i++)
if ((j % i) == 0)
q = q + 2;
if ((raiz * raiz) == j)
q++;
if (q > maior)
{
maior = q;
maior_n = j;
}
q = 0;
}
printf("Between %d and %d, %d has a maximum of %d divisors.n",inicio[k],fim[k],maior_n,maior);
maior = maior_n = q = 0;
}
}

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jan 24, 2002 11:52 am

> long int max,k, i, q, j, maior , maior_n,fim[900],inicio[900];

What if N > 900? Test your solution with input like:
901
1 1
2 2
...
901 901

and you'll see that it's wrong.

Cut out these arrays. Just read, compute and output one pair by another.

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower » Thu Jan 24, 2002 12:33 pm

bro, ok, i will use a dynamic allocation array... however, i dont think that this is the problem... :smile:)

thanks for the idea...

[[]]'s Necropower

ps:did u see any other problem?



<font size=-1>[ This Message was edited by: necropower on 2002-01-24 11:43 ]</font>

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower » Thu Jan 24, 2002 12:41 pm

can i do it to every problem? read a input and already put the output??
because i remmember a program[the 3n+1,100] that i had to read ALL the inputs first AND after read them all, put all the outputs.

like, i couldnt read on number then output the answer, then read another number then output the answer... u know?

[[]]'s Necropower

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jan 24, 2002 3:20 pm

>bro, ok, i will use a dynamic allocation array... however, i dont think that this is the problem... :smile:)

Insert assert(max <= 900) after scanf(). If you'll get SIGABRT than that's a problem.

>ps:did u see any other problem?

Other code looks OK except this:
if ((raiz * raiz) == j)
strict comparation of the float and integer may not work sometimes. Also your solution a bit slow.

>can i do it to every problem? read a input and already put the output??

Of course you can (in fact, you need to).

>because i remmember a program[the 3n+1,100] that i had to read ALL the inputs first AND after read them all, put all the outputs.

Why do so? Nobody will steal your input file while you computing answer :wink:

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower » Fri Jan 25, 2002 1:53 am

this program now should work, but it doenst... any idea?
:sad:
ps: BTW, i am getting WRONG ANSWER not other thing... :sad:

#include <math.h>
#include <stdio.h>

main()
{
int max,k, i, q, j, maior , maior_n,inicio,fim;

maior_n = maior = q = 0;


scanf("%d",&max);

for(k = 0; k < max ; k++)
{
scanf("%d %d",&inicio,&fim);
for(j=inicio ; j < (fim + 1) ; j++)
{
for(i=1 ; i <= sqrt(j) ; i++)
if ((j % i) == 0)
q++;
if ( ( sqrt(j)* sqrt(j) ) == j)
q = 2*q-1;
else
q = 2*q;
if (q > maior)
{
maior = q;
maior_n = j;
}
q = 0;
}
printf("Between %d and %d, %d has a maximum of %d divisors.n",inicio,fim,maior_n,maior);
maior = maior_n = q = 0;
}
}


<font size=-1>[ This Message was edited by: necropower on 2002-01-25 10:04 ]</font>

necropower
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower » Sun Jan 27, 2002 4:13 am

i am becoming crazy with this prb.. i dont know where is my error... :sad:(

Ustaad
New poster
Posts: 4
Joined: Tue Feb 05, 2002 2:00 am

Post by Ustaad » Tue Feb 05, 2002 11:54 am

Hi..

Just wondered if its problem with printing. Some mailers cut down your print statement to two lines. Try printing in two lines.

Best Regards,
Ustaad
In theory, there is no difference between theory and practice. But in practice, there is !

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

294: Please, help me!

Post by Revenger » Mon May 20, 2002 5:02 pm

I tested my program many times, but get WA. Why? Please, help me.

[pascal]
Program p294;

Var N,U,L,t,i,max,j,k : Integer;

Function GetD(NN : Integer) : Integer;
Var i,j,k,l : Integer;
begin
l:=round(sqrt(NN)+1);
k:=0;
for i:=1 to l do
if NN mod i=0 then begin
j:=NN div i;
if j>=i then inc(k);
if j<=i then Break;
inc(k);
end;
GetD:=k;
end;

begin
Read(N);
for t:=1 to N do begin
Read(L,U);
max:=-1;
for i:=L to U do begin
k:=GetD(i);
if k>max then begin
max:=k;
j:=i;
end;
end;
Writeln('Between ',L:0,' and ',U:0,', ',j:0,' has a maximum of ',max:0,' divisors.');
end;
end.[/pascal]

galois_godel
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

294 WR why??

Post by galois_godel » Thu Aug 22, 2002 8:19 am

the problem is easy?but I can't pass.Can u help me?

program a294(input,output);
var
n,casei,fin,i:integer;
di:integer;
inf,sup:integer;
max,maxdiv,temp:integer;
function getdiv(n,supmax:integer):integer;
var
i:integer;re:integer;
begin
i:=2;re:=1;
while n<>1 do
begin

di:=0;
//if i>trunc(sqrt(n))+1 then begin getdiv:=re*2;exit;end;
if (n mod i)=0 then
begin

di:=1;
n:=n div i;
while (n mod i)=0 do
begin
di:=di+1;
n:=n div i;
end;

end
else
begin
if (i>trunc(exp(ln(n)/3))+1)and(supmax>(re*4)) then begin getdiv:=re*4;exit;end;
end;
re:=re*(di+1);

i:=i+1;
end;

getdiv:=re;
end;

begin
// Insert user code here

readln(n);
for casei:=1 to n do
begin
readln(inf,sup);
max:=1;maxdiv:=inf;
for i:=inf to sup do
begin
temp:=getdiv(i,max);
if temp>max then
begin
max:=temp;
maxdiv:=i;
end;

end;
writeln('Between ',inf,' and ',sup,', ',maxdiv,' has a maximum of ',max,' divisors.');
end;


end.

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

294 Accepted but not as I want...

Post by pc5971 » Sat Nov 16, 2002 11:26 am

I solved the problem 294 and I was accepted but I'm not satisfied because it runs in 1.473 sec. so it's far away from 0.000 or something like this. The idea that I used is that for every number i (from L to H) I calculated the numbers of divisors like this:
[c]
k=0;
t=sqrt(i);
for (l=1;l<=t;l++)
if (!(i%l))
k+=2;
if (t*t==i)
k--;
[/c]

I don't know how can I improve this result... Can I use some Dinamic Programming ? ? ? How ? ? ?

I know that the numbers of divisors for

Code: Select all

  n=p1^e1 * p2^e2 * ... * pm^em 
is

Code: Select all

  (e1+1)*(e2+1)*...*(em+1)
but how can I obtain an dinamic programm using this....

Please help me...

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Wed Dec 11, 2002 12:41 am

Hi
I don't know how to solve this problem in 0.000s
my currect best solution is 0.193 s

hint: use prime numbers

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by pc5971 » Wed Dec 11, 2002 3:26 pm

You mean that you memorize the prime numbers before you calculate the numbers of divisors???

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Wed Dec 11, 2002 4:21 pm

yes, I calculate all prime numbers from 2 to sqrt(1000*1000*1000) + 1000, before even reading input data

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat Dec 14, 2002 5:22 pm

*CUT*
Last edited by deddy one on Sun Oct 05, 2003 5:17 pm, edited 1 time in total.

Post Reply

Return to “Volume 2 (200-299)”