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 » Fri Jun 28, 2002 3:29 pm

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 » Fri Jun 28, 2002 8:30 pm

[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 » Tue Jan 07, 2003 3:59 am

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. » Wed Jan 08, 2003 11:23 am

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 » Wed Jan 08, 2003 9:45 pm

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. » Thu Jan 09, 2003 11:42 am

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. » Mon Jul 07, 2003 4:01 am

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

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

Post by coolbila » Fri Sep 05, 2003 4:42 am

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 » Fri Sep 05, 2003 5:39 am

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 » Fri Sep 05, 2003 5:43 am

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 » Tue Dec 09, 2003 1:12 am

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. » Tue Dec 09, 2003 9:47 am

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 » Sat Jul 24, 2004 5:20 am

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