同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10293_RealPhobia

2022-5-16 18:16| 发布者: Hocassian| 查看: 57| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504737184700-Problem List-采集的数据-后羿采集器.html

Pro.ID

10293

Title

RealPhobia

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10293

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Bert is a programmer with a real fear of floating point arithmetic. Bert has quite successfully used rational numbers to write his programs but he does not like it when the denominator grows large.

Your task is to help Bert by writing a program that decreases the denominator of a rational number, whilst introducing the smallest error possible. For a rational number A/B, where B > 2 and 0 < A < B, your program needs to identify a rational number C/D such that:

1. 0 < C < D < B, and

2. the error |A/B - C/D| is the minimum over all possible values of C and D, and

3. D is the smallest such positive integer.

输入

The input starts with an integer K (1 ≤ K ≤ 1000) that represents the number of cases on a line by itself. Each of the following K lines describes one of the cases and consists of a fraction formatted as two integers, A and B, separated by "/" such that:

1. B is a 32 bit integer strictly greater than 2, and

2. 0 < A < B

输出

Description

Bert is a programmer with a real fear of floating point arithmetic. Bert has quite successfully used rational numbers to write his programs but he does not like it when the denominator grows large.

1. 0 < C < D < B, and

2. the error |A/B - C/D| is the minimum over all possible values of C and D, and

3. D is the smallest such positive integer.

Input

1. B is a 32 bit integer strictly greater than 2, and

2. 0 < A < B

Output

For each case, the output consists of a fraction on a line by itself. The fraction should be formatted as two integers separated by "/".

Sample Input

3
1/4
2/3
13/21

Sample Output

1/3
1/2
8/13