668 - Parliament

[tec]

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]

[lowai]

it is a multiple input problem.

[Admus]

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]

[Admus]

Sorry there isn't
assign(output,'bla.out');
rewrite(output);
close(output);
but there is also WA

[Admus]

Please help me!!!!!!!!!!!!!!!!!!!!!!!!!!11

[Zhao Le]

I don't know Pascal a lot but I have successfully got 668 AC(PE)
If you still don't got AC or have some question just turn to me.

[Zhao Le]

it is a multiple input problem.

the input such like this
3(represents the number you should input)
5
8
13

the output(mine output may be wrong)
2 3
3 5
3 4 6

[junjieliang]

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?

[Red Scorpion]

Hi, junjieliang.

I have the same problem as you did. I don't understand exactly what's the want. Some one please help..

[Zhao Le]

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?

Well first the number must count from 2.

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

[junjieliang]

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.

[Zhao Le]

you need other methods to solve this problem (maths / smart brute force search / etc)?

It has an very very easy way to solve,but needs prove.
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.

[DD]

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.

I think the DP solution only need O(n^2) time, maybe you can try to figure it out.