Problem B. Pluses and asterisks – 2

Problem A. Permugame

Input: standard input
Output: standard output
Memory limit: 256 Mb
Time limit: 0.5 sec

Ksyusha got a great present for her birthday - a “Permugame”. Gear for “Permugame” consists of the two permutations of size N: P_i, Q_i and a square board N×N cells. According to the rules cells (i, j) and (a, b) are connected to each other by a tunnel if and only if either (a = i and b = P_j) or (a = P_i and b = j). The only goal of the game is to find such a minimal integer k (k > 0), that every cell of the board can be painted in one of the k colors. The only restriction is that any two connected cells should have different colors. Ksyusha is too lazy to play “Permugame” so she asked you to figure out the answer.

Input

In the first line you are given a single integer N (1 ≤ N ≤ 100000) ­­- size of the board and permutations P and Q. In the next line permutation P_i (1 ≤ P_i ≤ N) is given as a list of integers separated by spaces. In the third line permutation Q_i (1 ≤ Q_i ≤ N) is given in the same format. It is guaranteed that P_i ≠ i and Q_i ≠ i for each i in [1, N].

Output

Print the minimal integer k (k > 0) such that every cell of the N×N board can be painted in one of the k colors.

Problem B. Pluses and asterisks – 2

Input: standard input
Output: standard output
Memory limit: 256 Mb
Time Limit: 1 sec

Given a sequence of integers a₁? a₂? a₃? …? a_N one may replace each? with either + or *. After that, the expression is evaluated according to arithmetic rules, where + denotes addition, * denotes multiplication. Multiplication’s precedence is higher than addition’s, i.e. 2+2*2 is 6, not 8. In how many ways it is possible to make result equal to R?

Input

The 1^st line contains space-separated integers N and R, denoting quantity of values a_i and required result respectively. The 2^nd line contains space-separated values a₁, a₂, a₃, …, a_N. 3≤N≤36, 1≤R≤2⁴², 1≤a_k≤2¹⁷.

Output

Your program should write exactly one integer — the quantity of ways to obtain exactly R.

Note: The five ways are: 2+2+2+2; 2+2+2*2; 2+2*2+2; 2*2+2+2; 2*2+2*2.

Не нашли, что искали? Воспользуйтесь поиском: