WPC4C - Shortcut

no tags 

Shortcut

Into the new level, a witch provides an option to Mario, so that he can avoid the intense battle ahead in this level. He needs to perform a task on a sheet of paper provided by the witch. He needs to cut a rectangular area out of them so that the ratio of height to width (i.e. the height/width quotient) can vary from 0.8 to 1.25 inclusively. Besides, at least one side of the cut area should have a size, equal to some power of number 2 (2^x for some integer x). If those rules don't indicate the size of the cut area clearly, then the way with which the cut part possesses the largest area is chosen. Of course, both sides of the cut area should be integer. If there are several answers to this problem, he must choose the answer with the maximal height.

Input
The first line contains number of test cases T (T <= 50)
The next lines contain a pair of integers x and y (1 <= x , y <= 10^9) which are the height and width of the sheet.

Output
T lines of two integers which are the height and width of the cut area.

Sample I/O

Input
2
2 1
2 2

Output
1 1
2 2

 

 


hide comments
pistachio: 2019-06-04 21:30:49

Another example
Input:
2
32 25
100 100

Output:
20 16
80 64

nadstratosfer: 2019-05-17 20:05:54

Badly written, ambiguous statement omitting key information, not helped by poor choice of sample cases.

Cut a largest possible rectangular area out of a x*y sheet such that at least one of its dimensions is a power of 2 and their ratio is in [0.8, 1.25] range.
- sides of the cut are parallel to sides of the original sheet
- output height is not necessarily the larger dimension, I got AC with "if h > x or w > y: h, w = w, h"

2
39 49
100 9

32 40
10 8

Last edit: 2019-05-17 20:13:37
joud zouzou: 2013-05-14 06:48:25

@ !@#$ :
no because the ratio would be 2.
it should be between 0.8 and 1.25

!@#$ : 2012-08-24 10:03:55

should not the output for 2 1 be 2 1 .plz explain

Walrus: 2012-02-06 06:56:59

@Mitch Schwartz: corrected the problem statement.

[Rampage] Blue.Mary: 2012-02-06 06:56:15

The cut rectangle's both sides must be parallel to the side of the paper?

Mitch Schwartz: 2012-02-06 06:56:15

There is something wrong with the constraint "1 <= x , y <= 110"; I produced NZEC with "if (x > 110 || y > 110 || x < 1 || y < 1) return 1;". Please fix the problem.

Edit: I got AC with long long.

Last edit: 2011-10-25 00:24:46
Kennard: 2012-02-06 06:56:15

what is 22?
is it 2 2?


Added by:Walrus
Date:2011-10-24
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local Contest: WPC 4