10053 - Envelopes

All about problems in Volume 100. 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
cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

10053 - Envelopes

Post by cyfra »

Hi!

I am not sure whether I understand the task correctly....

Could you tell me whet is the output for this test case :
2 2
10 10
10 10
10 10 3
1 1 1
Thanks in advance :wink:

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

[incorrect comment deleted]
Last edited by gvcormac on Fri Sep 05, 2003 4:51 am, edited 1 time in total.

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

10053

Post by ram »

I dont think I understood the problem correctly. Can anybody help me???

For this input:

2 4
105 9
99 149
110 10 10
100 50 5
150 100 7
90 140 15

How can the output be:
2
3

How can greeting with dimensions 105 9 fit into the envelope with dimensions 100 50. Does this make sense?????

And are there infinite number of envelopes of each given size????

Thanks for the help

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Got the same question..

Post by Whinii F. »

I'm confused about it too. How can a card of dimension 105 x 9 fit in an envelope of size 100 x 50? Can the envelopes distorted?? What's the trick in this?

ps. ram, trying a search will notify you that there are infinite envelopes of each kind..

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

it will fit in diagonally

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Oh!! @_@

Post by Whinii F. »

That was the way..

I was so silly :(

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

Is there anybody who solved this problem by numerical method (i.e. binary searching) ?

I was around this problem for months and there seems to be no way to get me accepted using binary search. I tried everything I could think of and failed every way.

I attach my most recently written code using long doubles.. anybody got an advice please reply.

[c]#include <stdio.h>
#include <math.h>

#define INF 999999999
#define eps 0.000000001
#define abs(x) ((x) < 0 ? -(x) : (x))
#define equal(a, b) (abs((a)-(b)) < eps)

int m, n;
long double e_w[10], e_h[10], c_w[5], c_h[5];
long double pi = 2.0 * acos(0);
long double halfpi;
int e_c[10];

int fits(long double cw, long double ch, long double ew, long double eh)
{
long double l = 0.0, r = halfpi, m;
long double wp, hp;
if(cw < ew + eps)
{
l = r = 0.0;
}
else
{
/* meaningless */
if(ch > ew)
return 0;
while(1)
{
m = (l+r) * 0.5;
wp = cos(halfpi - m) * ch + cos(m) * cw;
if(equal(wp, ew))
break;
if(wp > ew)
l = m;
else
r = m;
}
}
m = (l+r) * 0.5;
wp = cos(halfpi - m) * ch + cos(m) * cw;
hp = sin(halfpi - m) * ch + sin(m) * cw;
return (wp <= ew + eps) && (hp <= eh + eps);
}

void solve(void)
{
int i, j, min;
int mincost;
for(i = 0; i < m; i++)
{
mincost = INF;
for(j = 0; j < n; j++)
{
if(e_c[j] < mincost && (fits(c_w, c_h, e_w[j], e_h[j])||fits(c_h, c_w, e_w[j], e_h[j])))
{
mincost = e_c[j];
min = j;
}
}
if(mincost == INF)
printf("cannot buy\n");
else
printf("%d\n", min+1);
}
}

int main(void)
{
int i, c = 0;
halfpi = pi * 0.5;
while(scanf("%d %d", &m, &n) == 2)
{
if(m == 0 && n == 0)
break;
for(i = 0; i < m; i++)
scanf("%llf %llf", &c_w, &c_h);
for(i = 0; i < n; i++)
scanf("%llf %llf %d", &e_w, &e_h, &e_c);
if(c++) printf("\n");
printf("Case #%d\n", c);
solve();
}
return 0;
}[/c]

Thanks in advance,
JongMan @ Yonsei

coolbila
New poster
Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm

Post by coolbila »

one envelope can appear just one time

my AC program for this input is

Case #1
cannot buy

this is a matching problem but no need to use maximum flow
Last edited by coolbila on Fri Sep 05, 2003 8:05 am, edited 1 time in total.
Oh my God ... Wrong Answer

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

coolbila wrote:No, one envelope can appear just one time
my AC program for this input is
Case #1
cannot buy
this is a matching problem but no need to use maximum flow
Yes, I found that for problem says N >= M.
But I have a question, that we can determine if an answer exists or not by maximum flow.
Besides that, how can we derive the best answer without brute-force search?
Or it's an NP problem?
p.s. thanks for gvcormac :wink:

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac »

LittleJohn wrote:
coolbila wrote:No, one envelope can appear just one time
my AC program for this input is
Case #1
cannot buy
this is a matching problem but no need to use maximum flow
Yes, I found that for problem says N >= M.
But I have a question, that we can determine if an answer exists or not by maximum flow.
Besides that, how can we derive the best answer without brute-force search?
Or it's an NP problem?
p.s. thanks for gvcormac :wink:
You can use max flow or bipartite match but you don't need to. Since N <= 5 and M <= 10
you can try all possibilities.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

two points:

firstly only one card can go in one envelope, which the above program is not doing.

secondly i finally passed this through formulating an inequality in the lengths and widths of the card and the envelope and evaluated it with multi-precision arithmetic. maybe its not necessary but i couldnt get ac normally.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

Wow! :) I got AC! Thanks!
It seems you don't need any extensive precision calculation, I just used long double with bsearch.
JongMan @ Yonsei

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie »

At first glance, m = 5 n = 10,

i use brute force to get the answer but the judge said TLE. So i change the algorithm to backTrace and it got AC in 0.002 sec. :)

it's a little difficult to decide whether a rectangle can put in anther one. be patient to caculate every cases .

BTW i use double for the precison

Post Reply

Return to “Volume 100 (10000-10099)”