668 - Parliament
Moderator: Board moderators
668 - Parliament
I don't know what's wrong ?
This is my source:
[c]#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int n,i,j,result[50],temp[50],size,sizet,s;
double t,max;
scanf("%d",&n);
s=0;
t=0;
max=0;
for(j=2;j<(n+1)/2;j++)
{
for(i=j;s+i<=n;i++)
{
s+=i;
t+=log10(i);
temp[i-2]=i;
}
i-=3;
sizet=i+1;
while(s<n)
{
t-=log10(temp);
temp++;
s++;
t+=log10(temp);
i--;
if(i<0)i+=sizet;
}
if(t>max)
{
max=t;
size=sizet;
for(i=0;i<size;i++)
result=temp;
}
}
printf("%d",result[0]);
for(i=1;i<size;i++)
printf(" %d",result);
printf("\n");
exit(0);
}
[/c]
This is my source:
[c]#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int n,i,j,result[50],temp[50],size,sizet,s;
double t,max;
scanf("%d",&n);
s=0;
t=0;
max=0;
for(j=2;j<(n+1)/2;j++)
{
for(i=j;s+i<=n;i++)
{
s+=i;
t+=log10(i);
temp[i-2]=i;
}
i-=3;
sizet=i+1;
while(s<n)
{
t-=log10(temp);
temp++;
s++;
t+=log10(temp);
i--;
if(i<0)i+=sizet;
}
if(t>max)
{
max=t;
size=sizet;
for(i=0;i<size;i++)
result=temp;
}
}
printf("%d",result[0]);
for(i=1;i<size;i++)
printf(" %d",result);
printf("\n");
exit(0);
}
[/c]
668
I don't know what is wrong with it:
var
tab:array[1..50]of byte;
a,b,n:longint;
begin
assign(output,'bla.out');
rewrite(output);
while not eof do
begin
fillchar(tab,sizeof(tab),0);
readln(n);
a:=2;
b:=1;
while a<=n do
begin
tab:=a;
n:=n-a;
inc(a);
inc(b);
end;
if a=n+1 then
begin
inc(tab[b-1]);
dec(n);
end;
dec(b);
for n:=n downto 1 do
begin
inc(tab);
dec(b);
end;
b:=1;
while tab[b+1]<>0 do
begin
write(tab,' ');
inc(b);
end;
writeln(tab);
end;
close(output);
end.
[/pascal][/code]
var
tab:array[1..50]of byte;
a,b,n:longint;
begin
assign(output,'bla.out');
rewrite(output);
while not eof do
begin
fillchar(tab,sizeof(tab),0);
readln(n);
a:=2;
b:=1;
while a<=n do
begin
tab:=a;
n:=n-a;
inc(a);
inc(b);
end;
if a=n+1 then
begin
inc(tab[b-1]);
dec(n);
end;
dec(b);
for n:=n downto 1 do
begin
inc(tab);
dec(b);
end;
b:=1;
while tab[b+1]<>0 do
begin
write(tab,' ');
inc(b);
end;
writeln(tab);
end;
close(output);
end.
[/pascal][/code]
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
668 Parliament - Clarifications
I think I don't understand this problem. From what I see, there is no special checker for this problem, but for the sample input (31) why is the output 2 3 5 6 7 8? Can't it be 1 3 5 6 7 9 as well? I couldn't find anything in the problem that will make the solution unique.
Could someone who has solved this problem (or understands it), explain it to me?
Could someone who has solved this problem (or understands it), explain it to me?
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
Well first the number must count from 2.From what I see, there is no special checker for this problem, but for the sample input (31) why is the output 2 3 5 6 7 8? Can't it be 1 3 5 6 7 9 as well?
you may find the result 2*3*5*6*7*8 is bigger than 1*3*5*6*7*9
this is why should output 2 3 5 6 7 8
AC makes me feels good,
But WA makes me thinks hard.
But WA makes me thinks hard.
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
It has an very very easy way to solve,but needs prove.you need other methods to solve this problem (maths / smart brute force search / etc)?
It takes O(n) time.
hint:
write down several solution of the number.
like 5=2+3 and so on.
31=2+3+5+6+7+8;
try to find out what common they have.
AC makes me feels good,
But WA makes me thinks hard.
But WA makes me thinks hard.
-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 668 - Parliament
I think the DP solution only need O(n^2) time, maybe you can try to figure it out.junjieliang wrote:Hmm okay... now it doesn't seem as easy...![]()
I'm thinking of a O(n^3) DP solution, but I suppose that is too slow. Am I on the right track at all (like maybe I need to optimise the DP), or you need other methods to solve this problem (maths / smart brute force search / etc)?
Thanks.
![:wink:](./images/smilies/icon_wink.gif)
Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?