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 »

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 »

> 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 »

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 »

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 »

>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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

*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)”