HandsShaking
SRM 363 · 2007-08-11 · by mateuszek
SRM 363 · 2007-08-11 · by mateuszek · Advanced Math, Dynamic Programming
Problem Statement
Problem Statement
Consider a meeting of n businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other. Given an int n, return the number of perfect shakes that exist for n businessmen. See examples for further clarification.
Notes
- Businessmen are distinguishable. Rotating a perfect shake can yield a different perfect shake (see example 1).
Constraints
- n will be between 2 and 50, inclusive.
- n will be even.
Examples
0)
2 Returns: 1
Two businessmen have only one possibility - just to shake each other's hand.
1)
4 Returns: 2
Two out of three possible shakes are perfect.
2)
6 Returns: 5
3)
8 Returns: 14
4)
10 Returns: 42
Submissions are judged against all 25 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HandsShaking with a public method long long countPerfect(int n) · 25 test cases · 2 s / 256 MB per case