QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100

#9962. 递减分数

Statistics

Daria 实现了一个用于有理数算术的程序。该程序可以计算由最多 $n$ 个分数组成的加减法表达式的结果,其中分数的分子和分母均为不超过 $n$ 的正整数。

Daria 很关心该程序在结果为一个非常大的数或一个非常接近零的正数时的效率。她已经通过输入表达式 $\frac{n}{1} + \frac{n}{1} + \dots + \frac{n}{1}$ 轻松测试了第一种情况。但如何得到一个非常小的正数呢?

给定 $t$ 组测试数据,每组数据包含一个 Daria 考虑的上限 $n$。对于每个给定的 $n$,请找出一个表达式,使其值为尽可能小的正数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$),表示测试用例的数量。 接下来的 $t$ 行,每行包含一个整数 $n$ ($1 \le n \le 50\,000$)。 所有 $n$ 的总和不超过 $4 \cdot 10^6 = 4\,000\,000$。

输出格式

对于每个测试用例,输出一行找到的表达式。如果存在多个解,输出其中任意一个即可。

表达式应包含 $1$ 到 $n$ 个形如 $a/b$ ($1 \le a, b \le n$) 的分数。分数之间应使用 “+” 或 “-” 符号分隔。“-” 符号可以出现在第一个分数之前,但 “+” 符号不能。

表达式不应包含空格或其他任何额外字符。

样例

样例输入 1

2
3
6

样例输出 1

1/2-1/3
-3/6+1/4+2/5-5/6+6/4-4/5

说明

在第一个测试用例中,我们有 $n = 3$,表达式 $1/2-1/3 = 1/6$。不可能得到比 $1/6$ 更小的正数。其他可能的解包括 $-1/3+1/2$、或 $2/3-1/2$、或 $-3/2+1/1+2/3$。

在第二个测试用例中,我们有 $-3/6+1/4+2/5-5/6+6/4-4/5 = 1/60$,其中 $n = 6$。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.