Soluție HackerRank pentru Long Permutation, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Long Permutation
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: Long Permutation
Subdomeniu: Number Theory (number-theory)
Scor cont: 50.0 / 50
Submission status: Accepted
Submission score: 1.0
Submission ID: 464754841
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/long-permutation/problem
Cerință
Consider an inifite array, a, of positive numbers, a_1, a_2, …, where each a_i = i. You can apply a permutation, p, of size n (i.e., n different numbers 1 ≤ p_1, …, p_n ≤ n) to the n-element subset of your array from a_1 through a_n in the following way:
(a_1, …, a_n) rightarrow (a_{p_1}, …, a_{p_n}).
To get infinite array b, you must apply permutation p to the first n elements (a_1 to a_n), then to elements a_2 through a_n+1, then to elements a_3 through a_n+2, and so on, infinitely many times.
Given the values of n, m, and p, find and print the value of b_m. See the *Explanation* section below for more detail.
Note: This challenge uses 1-based array indexing.
Input Format
The first line contains 2 space-separated integers, n and m, respectively.
The second line contains n space-separated integers describing the respective values of p_1, p_2, …, p_n.
Output Format
Print a single integer denoting the value of b_m.
Sample Input 0
2 10
2 1
Sample Output 0
11
Sample Input 1
3 1
2 3 1
Sample Output 1
2
Sample Input 2
3 10
2 3 1
Sample Output 2
10
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ m ≤ 10^18
- 1 ≤ p_1, p_2, …, p_n ≤ n, and each p_i is unique.
Cod sursă
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long m;
if (!(cin >> n >> m)) return 0;
vector<int> p(n + 1);
for (int i = 1; i <= n; ++i) cin >> p[i];
int s = p[1];
if (s == n) {
cout << (m + (long long)n - 1) << '\n';
return 0;
}
// g(i) = p[i+1] for i in [1..n-1]
vector<int> g(n + 1, 0);
for (int i = 1; i <= n - 1; ++i) g[i] = p[i + 1];
vector<int> path;
path.reserve(n);
int x = s;
path.push_back(x);
while (x != n) {
x = g[x];
path.push_back(x);
}
long long r = (long long)path.size() - 1; // distance from s to n in the g-graph
if (m <= (long long)path.size()) {
cout << path[(size_t)m - 1] << '\n';
} else {
cout << (m + (long long)n - 1 - r) << '\n';
}
return 0;
}