310293: CF1810H. Last Number
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
H. Last Numbertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
You are given a multiset $S$. Initially, $S = \{1,2,3, \ldots, n\}$.
You will perform the following operation $n-1$ times.
- Choose the largest number $S_{\text{max}}$ in $S$ and the smallest number $S_{\text{min}}$ in $S$. Remove the two numbers from $S$, and add $S_{\text{max}} - S_{\text{min}}$ into $S$.
It's easy to show that there will be exactly one number left after $n-1$ operations. Output that number.
InputEach test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Their description follows.
For each test case, one single line contains a single integer $n$ ($2 \le n \le 10^9$) — the initial size of the multiset $S$.
OutputFor each test case, output an integer denoting the only number left after $n-1$ operations.
ExampleInput5 2 4 7 15 177567Output
1 2 2 4 33914Note
We show how the multiset $S$ changes for $n=4$.
- Operation $1$: $S=\{1,2,3,4\}$, remove $4$, $1$, add $3$.
- Operation $2$: $S=\{2,3,3\}$, remove $3$, $2$, add $1$.
- Operation $3$: $S=\{1,3\}$, remove $3$, $1$, add $2$.
- Final: $S = \{2\}$.
Thus, the answer for $n = 4$ is $2$.
Input
题意翻译
## 题目描述 有一个集合 $S$，$\mathbf{S}=\{1,2,3,\dots,n\}$，请执行以下操作 $n-1$ 次： - 删除 $S$ 中最大的数字和最小的数字（$S_{\max}$ 和 $S_{\min}$） - 在 $S$ 中添加 $S_{\max}-S_{\min}$ 最后，$S$ 中只有一个数字，输出这个数字。 ## 输入 第一行为一个数字 $T$（$1\leq T \leq 10^5$），表示测试点数据个数 从第二行到 $T+1$ 行，每一行包含一个整数 $n$（$1\le n\le10^9$），表示 $S$ 的长度。 ## 输出 对于每一个测试样例，每一个数字表示执行 $n-1$ 次后剩下来的数字。Output
题目大意：
给定一个多重集合 S，最初 S = {1,2,3,...,n}。将执行以下操作 n-1 次：
- 在 S 中选择最大的数 S_max 和最小的数 S_min，从 S 中移除这两个数，并将 S_max - S_min 添加到 S 中。
可以证明，经过 n-1 次操作后，将正好剩下一个数。输出这个数。
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 10^5）——测试用例的数量。接下来是每个测试用例的描述。
对于每个测试用例，单行包含一个整数 n（2 ≤ n ≤ 10^9）——多重集合 S 的初始大小。
输出数据格式：
对于每个测试用例，输出一个整数，表示经过 n-1 次操作后剩下的唯一数字。
示例：
输入
```
5
2
4
7
15
177567
```
输出
```
1
2
2
4
33914
```
注意：
题目中给出了 n=4 时多重集合 S 的变化过程：
- 操作 1：S={1,2,3,4}，移除 4, 1，添加 3。
- 操作 2：S={2,3,3}，移除 3, 2，添加 1。
- 操作 3：S={1,3}，移除 3, 1，添加 2。
- 最终：S = {2}。
因此，n = 4 的答案是 2。题目大意： 给定一个多重集合 S，最初 S = {1,2,3,...,n}。将执行以下操作 n-1 次： - 在 S 中选择最大的数 S_max 和最小的数 S_min，从 S 中移除这两个数，并将 S_max - S_min 添加到 S 中。 可以证明，经过 n-1 次操作后，将正好剩下一个数。输出这个数。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 10^5）——测试用例的数量。接下来是每个测试用例的描述。 对于每个测试用例，单行包含一个整数 n（2 ≤ n ≤ 10^9）——多重集合 S 的初始大小。 输出数据格式： 对于每个测试用例，输出一个整数，表示经过 n-1 次操作后剩下的唯一数字。 示例： 输入 ``` 5 2 4 7 15 177567 ``` 输出 ``` 1 2 2 4 33914 ``` 注意： 题目中给出了 n=4 时多重集合 S 的变化过程： - 操作 1：S={1,2,3,4}，移除 4, 1，添加 3。 - 操作 2：S={2,3,3}，移除 3, 2，添加 1。 - 操作 3：S={1,3}，移除 3, 1，添加 2。 - 最终：S = {2}。 因此，n = 4 的答案是 2。
给定一个多重集合 S，最初 S = {1,2,3,...,n}。将执行以下操作 n-1 次：
- 在 S 中选择最大的数 S_max 和最小的数 S_min，从 S 中移除这两个数，并将 S_max - S_min 添加到 S 中。
可以证明，经过 n-1 次操作后，将正好剩下一个数。输出这个数。
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 10^5）——测试用例的数量。接下来是每个测试用例的描述。
对于每个测试用例，单行包含一个整数 n（2 ≤ n ≤ 10^9）——多重集合 S 的初始大小。
输出数据格式：
对于每个测试用例，输出一个整数，表示经过 n-1 次操作后剩下的唯一数字。
示例：
输入
```
5
2
4
7
15
177567
```
输出
```
1
2
2
4
33914
```
注意：
题目中给出了 n=4 时多重集合 S 的变化过程：
- 操作 1：S={1,2,3,4}，移除 4, 1，添加 3。
- 操作 2：S={2,3,3}，移除 3, 2，添加 1。
- 操作 3：S={1,3}，移除 3, 1，添加 2。
- 最终：S = {2}。
因此，n = 4 的答案是 2。题目大意： 给定一个多重集合 S，最初 S = {1,2,3,...,n}。将执行以下操作 n-1 次： - 在 S 中选择最大的数 S_max 和最小的数 S_min，从 S 中移除这两个数，并将 S_max - S_min 添加到 S 中。 可以证明，经过 n-1 次操作后，将正好剩下一个数。输出这个数。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 10^5）——测试用例的数量。接下来是每个测试用例的描述。 对于每个测试用例，单行包含一个整数 n（2 ≤ n ≤ 10^9）——多重集合 S 的初始大小。 输出数据格式： 对于每个测试用例，输出一个整数，表示经过 n-1 次操作后剩下的唯一数字。 示例： 输入 ``` 5 2 4 7 15 177567 ``` 输出 ``` 1 2 2 4 33914 ``` 注意： 题目中给出了 n=4 时多重集合 S 的变化过程： - 操作 1：S={1,2,3,4}，移除 4, 1，添加 3。 - 操作 2：S={2,3,3}，移除 3, 2，添加 1。 - 操作 3：S={1,3}，移除 3, 1，添加 2。 - 最终：S = {2}。 因此，n = 4 的答案是 2。