CrazyFunctions
SRM 700 · 2016-10-02 · by lg5293
Problem Statement
In this problem, a function is any function that maps integers from 1 to n to integers from 1 to n. For example, if n=3, one possible function is the function g defined as follows: g(1)=1, g(2)=3, and g(3)=1.
We will use the notation f^(j)(x) to denote applying a function f to the input x exactly j times in a row. Formally:
- for all valid x, f^(0)(x) = x
- for all valid x and j, f^(j+1)(x) = f^(j)(f(x))
We will now formally define several new notations.
- G(f,w) will be the set of all values f^(r)(x), where x is between 1 and n, inclusive, and r is greater than or equal to w.
- S(f,w) will be the size of G(f,w).
- Z(f) will be the minimum of S(f,w), taken over all nonnegative w.
- A(y) will be the set of all functions f such that Z(f) = y.
You are given the
Constraints
- n will be between 1 and 5,000, inclusive.
- k will be between 1 and n, inclusive.
2 1 Returns: 2
We have n = 2, which means that there are four different functions. Let's call them a, b, c, d as follows: a(1) = 1 and a(2) = 1 b(1) = 1 and b(2) = 2 c(1) = 2 and c(2) = 1 d(1) = 2 and d(2) = 2 Two of these functions (functions a and d) belong into the set A(1), so the correct return value is 2. The other two functions (b and c) belong into the set A(2).
2 2 Returns: 2
1 1 Returns: 1
3 1 Returns: 9
3 3 Returns: 6
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CrazyFunctions with a public method int count(int n, int k) · 42 test cases · 2 s / 256 MB per case