LCC '22 Contest 6 S1 - Same Patrick's Day

View as PDF

Submit solution

Points: 5
Time limit: 1.5s
Memory limit: 256M

Author:
Problem type

Patrick Lin (The Ultimate Overlord of WLMAC) recently hired Patrick Bian to be part of the Project Metropolis team. Since this school isn't big enough for two Patricks, on St. Patrick's day, the two will engage in the ultimate battle of the Patricks to determine which is the one true Patrick.

The battle consists of multiple rounds in which they will play best of N rounds, meaning the first person to win \lceil\dfrac{N}{2}\rceil rounds will win the tournament. In each round, there is always a winner and a loser. This means they will always play at most N rounds.

Patrick Lin really wants to win this battle so he will try to list all the possible sequences of outcomes in which he wins the battle. Given an odd integer N\,(3 \le N \le 21), how many different sequences of wins and losses are possible such that Patrick Lin wins the tournament?

Note: you will require 64-bit integers to solve this problem (e.g. long in Java or long long in C++).

Input Specification

A single odd integer N.

Output Specification

The number of different sequences of wins and losses are possible such that Patrick Lin wins the tournament.

Sample Input 1

3

Output for Sample Input 1

3
Explanation for Sample Case 1

Here are all the possible sequences of rounds in which Patrick Lin wins the tournement (W denotes a round where Patrick Lin wins, and L denotes a round where Patrick Lin loses):

  1. WW
  2. WLW
  3. LWW

Sample Input 2

9

Output for Sample Input 1

126

Comments

There are no comments at the moment.