Hide

Problem F
Bracelet Making

You are a UCLA student braiding bracelets for charity.

There are $2$ colors of beads to choose from, $B$ blue beads and $G$ gold beads.

You have to use all beads provided.

How many unique bracelets can you make?

We define equivalence, and thus uniqueness, of bracelets below:

We represent a bracelet $b$ of length $n$ by a sequence $b_1$, $b_2$, $\dotsc $, $b_ n$ of colors.
The rotation of a bracelet $b$ is another bracelet $c$ such that $c_ i = b_{i+1}$ for $1\leq i<n$ and $c_ n=b_1$.
The reflection of a bracelet $b$ is another bracelet $c$ such that $c_ i = b_{n+1-i}$ for $1\leq i \leq n$.
Two bracelets are considered equivalent if there is a sequence of rotations and reflections that can be applied to the first bracelet to get the second one.

For example:

\includegraphics[width=0.5\textwidth ]{bracelet_figure_same.png}
Figure 1: These bracelets are identical.
\includegraphics[width=0.5\textwidth ]{bracelet_figure_diff.png}
Figure 2: These bracelets are unique, they cannot be recreated by rotating or reflecting.

Input

Two non-negative integers, $B$ and $G$, such that $B$ and $G$ sum up to a prime number less than $20$.

Output

Single integer representing the number of possible ways to make bracelets given $B$ and $G$.

Output Visualization

For a bracelet with $2$ gold and $5$ blue beads, these are the only possible unique bracelets you can have:

\includegraphics[width=0.5\textwidth ]{output_bracelet.png}
Figure 3: Total unique ways.
Sample Input 1 Sample Output 1
3 2
2
Sample Input 2 Sample Output 2
5 2
3
Sample Input 3 Sample Output 3
12 7
1368
CPU Time limit 1 second
Memory limit 1024 MB
Author
Ana Gu
Source CodeSprintLA 2020 (UCLA ACM-ICPC)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in