Back
Close

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