Algorithm


Problem Name: beecrowd | 3348

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/3348

Game of Spiders

 

By Leandro Zatesko, Federal University of Technology of Paraná BR Brazil

Timelimit: 1

Through all the South of Brazil it is possible to find many species of spiders belonging to the genus Loxosceles, popularly known as recluse spiders, or brown spiders. Despite not being aggressive, these spiders inoculate a strong venom, being responsible for the greatest amount of accidents with spiders in Brazil. Accidents with recluse spiders usually occur when they hide inside shoes and clothes or under bed linen.

Some people mistake recluse spiders for spiders of the genus Nesticodes, popularly known as red house spiders, also very common in the South of Brazil. Harmless to humans, red house spiders are natural predators of recluse spiders and should not be eliminated.

Lady Lady

To the left, a recluse spider. To the right, a red house spider.

Arthur and Merlin decided to play a dangerous game with spiders, which you shouldn't try at home. Arthur begins collecting N ≥ 1 spiders of the genus Nesticodes and N spiders of the genus Loxosceles, arranging the 2 × N spiders in a circle in a manner that the harmless spiders occupy the first N positions and the recluse spiders occupy the last N positions. Then, Merlin tells a positive integer K to Arthur, who enters a process of killing every K-th still living spider in the circle until exactly N spiders have been killed. Merlin's goal is that only recluse spiders are killed. For example, if N = 3 and K = 5, the spiders in positions 5, 4, 6 are eliminated, in this order, and Merlin reaches his goal, winning the game. If N = 2 and K = 7, the spiders in positions 3, 4 are eliminated, in this order, and Merlin also wins the game. However, if N = 3 and K = 10, the spiders in positions 4, 3, 6 are eliminated, in this order, and thus Arthur wins the game.

 

Input

 

The input consists only of the number N (N ≤ 19), a positive integer.

 

Output

 

Print a positive integer K < 1016 that leads Merlin to win the game.

 

 

 

Input Sample Output Sample

1

2

 

 

 

1

4

 

 

 

2

7

 

 

 

2

12

 

 

 

3

5

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming


l = ['2', '7', '5', '30', '169', '441', '1872', '7632', '1740', '93313', '459901', '1358657', '2504881', '13482720', '25779600', '68468401', '610346880', '1271932200', '327280800']
print(l[int(input())-1])
Copy The Code & Try With Live Editor

Input

x
+
cmd
1

Output

x
+
cmd
2
Advertisements

Demonstration


Previous
#3346 Beecrowd Online Judge Solution 3346 GDP Fluctuation Solution in C, C++, Java, Js and Python
Next
#2502 Beecrowd Online Judge Solution 2502 Deciphering the Encrypted Card Solution in C, C++, Java, Js and Python