URI Online Judge | 2972

Less Coin Tosses

By Maratona SBC de Programação BR Brazil

Timelimit: 1

Carla and Daniel have decided to play heads or tails to decide who will wash the dishes today. They will play with one of the old coins from Carla’s collection. This makes Daniel worried, because these coins are crooked and unbalanced: when tossing a coin, the odds of getting heads and tails are not necessarily equal.

Carla knows her coins well, and can choose one that maximizes her chances of winning. Therefore, Daniel devised a scheme to make the game completely fair, regardless of the chosen coin. First, each will be assigned a nonempty set of binary strings of size N. No string can belong to both, and some strings may not be included in either set. For example, for N = 3, a valid way to distribute the strings would be:

• “010” and “110” for Carla;

• “001” and “011” for Daniel;

• “000”, “100”, “101” and “111” for neither.

After distributing the strings, Carla and Daniel will toss the same coin N times and write down the sequence of results, where each head equals 0 and each tail equals 1. If the resulting binary string belongs to Carla’s set, she is the winner. If it belongs to Daniel’s set, he is the winner. If the string does not belong to either of them, the coin is tossed another N times to generate a new string. The process is repeated as many times as necessary until they get a winner.

The proper functioning of this scheme depends on the distribution of the strings between Carla and Daniel: the probability of generating a string of the Carla’s set must be equal to the probability of generating a string of Daniel’s set. In other words, let P(S) be the probability that a binary string S of length N will be generated by a sequence of N tosses of the same coin, possibly unbalanced. The total of P for all strings in Carla’s set must be the same as the total of P for all the strings in Daniel’s set.

In addition to distributing the strings fairly, Carla and Daniel want to avoid having to repeat the coin tosses as much as possible, so they want to minimize the number of strings that do not belong to either set. Given N, determine the minimum possible number of unassigned binary strings.


The input consists of a single line, which contains contains an integer number N, the number of coin tosses and binary strings size (2 ≤ N ≤ 10¹⁸).


Your program must output a single line, containing an integer, representing the minimum possible number of unassigned binary strings.

Input Samples Output Samples