CODE FESTIVAL 2016 Relay (Parallel)

F - 3分割ゲーム / Trichotomy


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 100

問題文

長さが正の整数の紐があります。以下の操作を紐の長さが 2 以下になるまで続けます。

  • 操作: 紐を 2 箇所で切り、長さが正の整数である紐 3 つに分ける。 この中で最長のもの 1 つと最短のもの 1 つを捨てる。

長さ N の紐からこの操作を始めたときに、この操作を続けることが出来る回数の最大値を f(N) とします。

正整数 X が与えられるので、f(N)=X となる最大の整数 N を求めてください。

制約

  • 1 \leq X \leq 40

入力

入力は以下の形式で標準入力から与えられる。

X

出力

f(N) = X となる最大の整数 N の値を出力せよ。


入力例 1

2

出力例 1

14

Score : 100 points

Problem Statement

We have a cord whose length is a positive integer. We will perform the following condition until the length of the cord becomes at most 2:

  • Operation: Cut the rope at two positions to obtain three cords, each with a length of a positive integer. Among these, discard one with the longest length and one with the shortest length, and keep the remaining one.

Let f(N) be the maximum possible number of times to perform this operation, starting with a cord with the length N.

You are given a positive integer X. Find the maximum integer N such that f(N)=X.

Constraints

  • 1 \leq X \leq 40

Input

The input is given from Standard Input in the following format:

X

Output

Print the value of the maximum integer N such that f(N)=X.


Sample Input 1

2

Sample Output 1

14

Submit提出する