Cerinta completa

Consider the following pseudocode, run on an array of length :

rep := 0
while A not empty:
    B := []
    for x in A, y in A:
        if x != y: append absolute_value(x - y) to B
    A := B
    rep := rep + 1

Given the values of and array , compute and print the final value of after the pseudocode above terminates; if the loop will never terminate, print -1 instead.

Input Format

The first line contains a single integer, , denoting the length of array .
The second line contains space-separated integers describing the respective values of .

Constraints

Output Format

Print the final value of after the pseudocode terminates; if the loop will never terminate, print -1 instead.

Sample Input 0

3
1 3 4

Sample Output 0

4

Explanation 0

After the first loop, becomes . After the second loop, the array only contains ‘s and ‘s. After the third loop, the array only contains ‘s. After the fourth loop, the array is empty. Because the value of is incremented after each loop, at the time the loop terminates. Thus, we print 4 as our answer.

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
#pragma warning(disable : 4996)

using namespace std;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

int n, a[100009]; bool c[50009];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), c[a[i]] = true;
    int ret = 0;
    while (true) {
        vector<int> v;
        for (int i = 1; i <= 50000; i++) {
            if (c[i]) v.push_back(i), c[i] = false;
        }
        if (!v.size()) {
            break;
        }
        int g = v[0];
        for (int i = 1; i < v.size(); i++) {
            g = gcd(g, v[i]);
        } 
        for (int i = 0; i < v.size(); i++) {
            v[i] /= g;
        } 
        bool flag = true;
        for (int i = 0; i < v.size(); i++) {
            if (v[i] != i + 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ret += v.size();
            break;
        }
        for (int i = 0; i < v.size(); i++) {
            for (int j = i + 1; j < v.size(); j++) {
                c[v[j] - v[i]] = true;
            }
        }
        ret++;
    }
    printf("%d\n", ret);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647838

Link challenge: https://www.hackerrank.com/challenges/iterate-it/problem

Iterate It