309782: CF1735A. Working Week
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Working Week
题意翻译
假设一周有 $n$ 天，第 $n$ 天的下一天是第 $1$ 天，有三天休息，其中第 $n$ 天一定休息。现需要安排剩下的两个休息日，要求： - 不能使得休息日相邻，很明显第 $1$ 天不能作为休息日。 - 这两个休息日将 $n-1$ 天分成三段，记每段天数分别为 $l1,l2,l3$。 求最大的 $\min(\ |l1-l2|\ ,\ |l2-l3|\ ,\ |l1-l3|\ )$。题目描述
Your working week consists of $ n $ days numbered from $ 1 $ to $ n $ , after day $ n $ goes day $ 1 $ again. And $ 3 $ of them are days off. One of the days off is the last day, day $ n $ . You have to decide when the other two are. Choosing days off, you pursue two goals: - No two days should go one after the other. Note that you can't make day $ 1 $ a day off because it follows day $ n $ . - Working segments framed by days off should be as dissimilar as possible in duration. More specifically, if the segments are of size $ l_1 $ , $ l_2 $ , and $ l_3 $ days long, you want to maximize $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ . Output the maximum value of $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ that can be obtained.输入输出格式
输入格式
The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of test cases follows. The only line of each test case contains the integer $ n $ ( $ 6 \le n \le 10^9 $ ).
输出格式
For each test case, output one integer — the maximum possible obtained value.
输入输出样例
输入样例 #1
3
6
10
1033输出样例 #1
0
1
342说明
In the image below you can see the example solutions for the first two test cases. Chosen days off are shown in purple. Working segments are underlined in green. In test case $ 1 $ , the only options for days off are days $ 2 $ , $ 3 $ , and $ 4 $ (because $ 1 $ and $ 5 $ are next to day $ n $ ). So the only way to place them without selecting neighboring days is to choose days $ 2 $ and $ 4 $ . Thus, $ l_1 = l_2 = l_3 = 1 $ , and the answer $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0 $ . For test case $ 2 $ , one possible way to choose days off is shown. The working segments have the lengths of $ 2 $ , $ 1 $ , and $ 4 $ days. So the minimum difference is $ 1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|) $ . It can be shown that there is no way to make it larger. Input
题意翻译
假设一周有 $n$ 天，第 $n$ 天的下一天是第 $1$ 天，有三天休息，其中第 $n$ 天一定休息。现需要安排剩下的两个休息日，要求： - 不能使得休息日相邻，很明显第 $1$ 天不能作为休息日。 - 这两个休息日将 $n-1$ 天分成三段，记每段天数分别为 $l1,l2,l3$。 求最大的 $\min(\ |l1-l2|\ ,\ |l2-l3|\ ,\ |l1-l3|\ )$。Output
**工作周**
**题意翻译**
假设一周有 $ n $ 天，第 $ n $ 天的下一天是第 $ 1 $ 天，有三天休息，其中第 $ n $ 天一定休息。现需要安排剩下的两个休息日，要求：
- 不能使得休息日相邻，很明显第 $ 1 $ 天不能作为休息日。
- 这两个休息日将 $ n-1 $ 天分成三段，记每段天数分别为 $ l1, l2, l3 $。
求最大的 $ \min(|l1-l2|, |l2-l3|, |l1-l3|) $。
**题目描述**
你的工作周包含 $ n $ 天，从 $ 1 $ 到 $ n $ 编号，过了第 $ n $ 天又是第 $ 1 $ 天。其中 $ 3 $ 天是休息日。休息日之一是最后一天，即第 $ n $ 天。你需要决定另外两天休息日是哪两天。
在选择休息日时，你追求两个目标：
- 任何两天休息日不能连续。注意你不能让第 $ 1 $ 天成为休息日，因为它紧接着第 $ n $ 天。
- 由休息日划分的工作段时长应尽可能不同。更具体地说，如果工作段的长度分别为 $ l_1 $, $ l_2 $, 和 $ l_3 $ 天，你希望最大化 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $。
输出可以获得的 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ 的最大值。
**输入输出格式**
**输入格式**
输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 1000 $ ) —— 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例仅包含一行，整数 $ n $ ( $ 6 \le n \le 10^9 $ )。
**输出格式**
对于每个测试用例，输出一个整数 —— 可以获得的最大可能值。
**输入输出样例**
**输入样例 #1**
```
3
6
10
1033
```
**输出样例 #1**
```
0
1
342
```
**说明**
在下面的图片中，你可以看到前两个测试用例的示例解决方案。选定的休息日以紫色显示，工作段以绿色下划线表示。
在测试用例 $ 1 $ 中，休息日的唯一选择是第 $ 2 $, $ 3 $, 和 $ 4 $ 天（因为 $ 1 $ 和 $ 5 $ 天紧挨着第 $ n $ 天）。因此，为了避免选择相邻的日子，只能选择第 $ 2 $ 和 $ 4 $ 天。这样，$ l_1 = l_2 = l_3 = 1 $，答案 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0 $。
在测试用例 $ 2 $ 中，展示了一种选择休息日的方式。工作段的长度分别为 $ 2 $, $ 1 $, 和 $ 4 $ 天。所以最小差值是 $ 1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|) $。可以证明没有方法使其更大。
（注：图片内容无法显示，但文字描述了图片中的内容。）**工作周** **题意翻译** 假设一周有 $ n $ 天，第 $ n $ 天的下一天是第 $ 1 $ 天，有三天休息，其中第 $ n $ 天一定休息。现需要安排剩下的两个休息日，要求： - 不能使得休息日相邻，很明显第 $ 1 $ 天不能作为休息日。 - 这两个休息日将 $ n-1 $ 天分成三段，记每段天数分别为 $ l1, l2, l3 $。 求最大的 $ \min(|l1-l2|, |l2-l3|, |l1-l3|) $。 **题目描述** 你的工作周包含 $ n $ 天，从 $ 1 $ 到 $ n $ 编号，过了第 $ n $ 天又是第 $ 1 $ 天。其中 $ 3 $ 天是休息日。休息日之一是最后一天，即第 $ n $ 天。你需要决定另外两天休息日是哪两天。 在选择休息日时，你追求两个目标： - 任何两天休息日不能连续。注意你不能让第 $ 1 $ 天成为休息日，因为它紧接着第 $ n $ 天。 - 由休息日划分的工作段时长应尽可能不同。更具体地说，如果工作段的长度分别为 $ l_1 $, $ l_2 $, 和 $ l_3 $ 天，你希望最大化 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $。 输出可以获得的 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ 的最大值。 **输入输出格式** **输入格式** 输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 1000 $ ) —— 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例仅包含一行，整数 $ n $ ( $ 6 \le n \le 10^9 $ )。 **输出格式** 对于每个测试用例，输出一个整数 —— 可以获得的最大可能值。 **输入输出样例** **输入样例 #1** ``` 3 6 10 1033 ``` **输出样例 #1** ``` 0 1 342 ``` **说明** 在下面的图片中，你可以看到前两个测试用例的示例解决方案。选定的休息日以紫色显示，工作段以绿色下划线表示。 在测试用例 $ 1 $ 中，休息日的唯一选择是第 $ 2 $, $ 3 $, 和 $ 4 $ 天（因为 $ 1 $ 和 $ 5 $ 天紧挨着第 $ n $ 天）。因此，为了避免选择相邻的日子，只能选择第 $ 2 $ 和 $ 4 $ 天。这样，$ l_1 = l_2 = l_3 = 1 $，答案 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0 $。 在测试用例 $ 2 $ 中，展示了一种选择休息日的方式。工作段的长度分别为 $ 2 $, $ 1 $, 和 $ 4 $ 天。所以最小差值是 $ 1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|) $。可以证明没有方法使其更大。 （注：图片内容无法显示，但文字描述了图片中的内容。）
**题意翻译**
假设一周有 $ n $ 天，第 $ n $ 天的下一天是第 $ 1 $ 天，有三天休息，其中第 $ n $ 天一定休息。现需要安排剩下的两个休息日，要求：
- 不能使得休息日相邻，很明显第 $ 1 $ 天不能作为休息日。
- 这两个休息日将 $ n-1 $ 天分成三段，记每段天数分别为 $ l1, l2, l3 $。
求最大的 $ \min(|l1-l2|, |l2-l3|, |l1-l3|) $。
**题目描述**
你的工作周包含 $ n $ 天，从 $ 1 $ 到 $ n $ 编号，过了第 $ n $ 天又是第 $ 1 $ 天。其中 $ 3 $ 天是休息日。休息日之一是最后一天，即第 $ n $ 天。你需要决定另外两天休息日是哪两天。
在选择休息日时，你追求两个目标：
- 任何两天休息日不能连续。注意你不能让第 $ 1 $ 天成为休息日，因为它紧接着第 $ n $ 天。
- 由休息日划分的工作段时长应尽可能不同。更具体地说，如果工作段的长度分别为 $ l_1 $, $ l_2 $, 和 $ l_3 $ 天，你希望最大化 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $。
输出可以获得的 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ 的最大值。
**输入输出格式**
**输入格式**
输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 1000 $ ) —— 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例仅包含一行，整数 $ n $ ( $ 6 \le n \le 10^9 $ )。
**输出格式**
对于每个测试用例，输出一个整数 —— 可以获得的最大可能值。
**输入输出样例**
**输入样例 #1**
```
3
6
10
1033
```
**输出样例 #1**
```
0
1
342
```
**说明**
在下面的图片中，你可以看到前两个测试用例的示例解决方案。选定的休息日以紫色显示，工作段以绿色下划线表示。
在测试用例 $ 1 $ 中，休息日的唯一选择是第 $ 2 $, $ 3 $, 和 $ 4 $ 天（因为 $ 1 $ 和 $ 5 $ 天紧挨着第 $ n $ 天）。因此，为了避免选择相邻的日子，只能选择第 $ 2 $ 和 $ 4 $ 天。这样，$ l_1 = l_2 = l_3 = 1 $，答案 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0 $。
在测试用例 $ 2 $ 中，展示了一种选择休息日的方式。工作段的长度分别为 $ 2 $, $ 1 $, 和 $ 4 $ 天。所以最小差值是 $ 1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|) $。可以证明没有方法使其更大。
（注：图片内容无法显示，但文字描述了图片中的内容。）**工作周** **题意翻译** 假设一周有 $ n $ 天，第 $ n $ 天的下一天是第 $ 1 $ 天，有三天休息，其中第 $ n $ 天一定休息。现需要安排剩下的两个休息日，要求： - 不能使得休息日相邻，很明显第 $ 1 $ 天不能作为休息日。 - 这两个休息日将 $ n-1 $ 天分成三段，记每段天数分别为 $ l1, l2, l3 $。 求最大的 $ \min(|l1-l2|, |l2-l3|, |l1-l3|) $。 **题目描述** 你的工作周包含 $ n $ 天，从 $ 1 $ 到 $ n $ 编号，过了第 $ n $ 天又是第 $ 1 $ 天。其中 $ 3 $ 天是休息日。休息日之一是最后一天，即第 $ n $ 天。你需要决定另外两天休息日是哪两天。 在选择休息日时，你追求两个目标： - 任何两天休息日不能连续。注意你不能让第 $ 1 $ 天成为休息日，因为它紧接着第 $ n $ 天。 - 由休息日划分的工作段时长应尽可能不同。更具体地说，如果工作段的长度分别为 $ l_1 $, $ l_2 $, 和 $ l_3 $ 天，你希望最大化 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $。 输出可以获得的 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) $ 的最大值。 **输入输出格式** **输入格式** 输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 1000 $ ) —— 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例仅包含一行，整数 $ n $ ( $ 6 \le n \le 10^9 $ )。 **输出格式** 对于每个测试用例，输出一个整数 —— 可以获得的最大可能值。 **输入输出样例** **输入样例 #1** ``` 3 6 10 1033 ``` **输出样例 #1** ``` 0 1 342 ``` **说明** 在下面的图片中，你可以看到前两个测试用例的示例解决方案。选定的休息日以紫色显示，工作段以绿色下划线表示。 在测试用例 $ 1 $ 中，休息日的唯一选择是第 $ 2 $, $ 3 $, 和 $ 4 $ 天（因为 $ 1 $ 和 $ 5 $ 天紧挨着第 $ n $ 天）。因此，为了避免选择相邻的日子，只能选择第 $ 2 $ 和 $ 4 $ 天。这样，$ l_1 = l_2 = l_3 = 1 $，答案 $ \min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = 0 $。 在测试用例 $ 2 $ 中，展示了一种选择休息日的方式。工作段的长度分别为 $ 2 $, $ 1 $, 和 $ 4 $ 天。所以最小差值是 $ 1 = \min(1, 3, 2) = \min(|2 - 1|, |1 - 4|, |4 - 2|) $。可以证明没有方法使其更大。 （注：图片内容无法显示，但文字描述了图片中的内容。）