[Solution] Working Week solution codeforces

Working Week solution codeforces – Your working week consists of 𝑛n days numbered from 11 to 𝑛n, after day 𝑛n goes day 11 again. And 33 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.

Table of Contents

[Solution] Working Week solution codeforces

Choosing days off, you pursue two goals:

  • No two days should go one after the other. Note that you can’t make day 11 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 𝑙1l1𝑙2l2, and 𝑙3l3 days long, you want to maximize min(|𝑙1𝑙2|,|𝑙2𝑙3|,|𝑙3𝑙1|)min(|l1−l2|,|l2−l3|,|l3−l1|).

Output the maximum value of min(|𝑙1𝑙2|,|𝑙2𝑙3|,|𝑙3𝑙1|)min(|l1−l2|,|l2−l3|,|l3−l1|) that can be obtained.

Input

The first line of the input contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. The description of test cases follows.

The only line of each test case contains the integer 𝑛n (6𝑛1096≤n≤109).

[Solution] Working Week solution codeforces

Output one integer — the minimum possible obtained value.

Example
input

Copy
3
6
10
1033
output

Copy
0
1
342

[Solution] Working Week solution codeforces

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 11, the only options for days off are days 2233, and 44 (because 11 and 55 are next to day 𝑛n). So the only way to place them without selecting neighboring days is to choose days 22 and 44.

For test case 22, one possible way to choose days off is shown. The working segments have the lengths of 2211, and 44 days.

[Solution] Working Week solution codeforces

So the minimum difference is 1=min(1,3,2)=min(|21|,|14|,|42|)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.

 

For Solution

“Click Here”

Leave a Comment