668 - Parliament

All about problems in Volume 6. 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
tec
New poster
Posts: 2
Joined: Thu Mar 13, 2003 10:07 pm

668 - Parliament

Post by tec » Mon Mar 17, 2003 7:07 pm

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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Tue Mar 18, 2003 12:04 pm

it is a multiple input problem.

Admus
New poster
Posts: 8
Joined: Mon Sep 29, 2003 3:13 pm

668

Post by Admus » Mon Sep 29, 2003 3:21 pm

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
New poster
Posts: 8
Joined: Mon Sep 29, 2003 3:13 pm

Post by Admus » Mon Sep 29, 2003 6:08 pm

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

Admus
New poster
Posts: 8
Joined: Mon Sep 29, 2003 3:13 pm

Post by Admus » Tue Sep 30, 2003 8:48 pm

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

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sat Dec 06, 2003 3:43 am

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.
AC makes me feels good,
But WA makes me thinks hard.

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Sat Dec 06, 2003 3:47 am

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
AC makes me feels good,
But WA makes me thinks hard.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

668 Parliament - Clarifications

Post by junjieliang » Sun Jan 04, 2004 5:16 am

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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Jan 05, 2004 1:54 pm

Hi, junjieliang.

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

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Wed Jan 28, 2004 9:38 am

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
AC makes me feels good,
But WA makes me thinks hard.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Jan 28, 2004 4:34 pm

Hmm okay... now it doesn't seem as easy... :D

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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by Zhao Le » Thu Jan 29, 2004 4:01 pm

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.
AC makes me feels good,
But WA makes me thinks hard.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 668 - Parliament

Post by DD » Sun Nov 09, 2008 8:52 am

junjieliang wrote:Hmm okay... now it doesn't seem as easy... :D

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. :wink:
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?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 6 (600-699)”