Devious Deck Derangement
Statement
The <<riffle shuffle>> is a common method for rearranging a deck of cards, performed by splitting the deck into two "packets" (ideally of equal size) and interleaving the cards from each. It matters which packet contributes a card first, so we'll specifically use an <<in shuffle>> such that the top and bottom cards do not retain their locations (as they would with an out shuffle).
As an example, suppose we have a deck of six cards:
Top half: {{1}} {{2}} {{3}}
Bottom half: {{4}} {{5}} {{6}}
Since the cards come out of the bottom of the packets, "dealing" from the bottom half first would result in the bottom card retaining its position; we don't want that, so we deal from the top half first and the new bottom card is the {{3}}. The {{6}} goes on top of that, then the {{2}}, the {{5}}, and so on, resulting in the following order: {{4}} {{1}} {{5}} {{2}} {{6}} {{3}}.
After shuffling, it's common to <<cut>> the deck by swapping the top and bottom halves, which gives us: {{2}} {{6}} {{3}} {{4}} {{1}} {{5}}.
The <<"derangement">> of a sequence is a measure of how out of order it is; for this problem, we'll use each card's distance from its original location (for instance, the {{6}} is 4 away from where it started) and the total derangement of the deck is the sum of these distances. That value is 10 with the current example deck, but we can do better; performing the shuffle-and-cut procedure once more increases the total derangement to 16. That is indeed the greatest possible value when starting with a deck of {{6}} cards, so we only had to perform the procedure {{2}} times.
Given a deck of {{N}} distinct cards, how many times must it be <<shuffled-and-cut>> such that it is maximally deranged?
Input description
[[N]]: number of distinct cards in the deck
Output description
number of shuffle-and-cut procedures to perform such that the deck is as "out of order" as possible
Constraints
2 <= [[N]] <= 1000 (always even and with a unique solution)
Game modes
Test cases
Test 1 Test
Input
6
Output
2
Validator 1 Validator
Input
4
Output
1
Test 2 Test
Input
42
Output
10
Validator 2 Validator
Input
44
Output
7
Test 3 Test
Input
140
Output
69
Validator 3 Validator
Input
132
Output
65
Test 4 Test
Input
614
Output
306
Validator 4 Validator
Input
620
Output
309
Test 5 Test
Input
994
Output
15
Validator 5 Validator
Input
998
Output
166
Solution language
Solution
Stub generator input