Algorithm

A. Fox and Number Game
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/389/problem/A
input
standard input
output
standard output

Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x1, x2, ..., xn. She can do the following operation as many times as needed: select two different indexes i and j such that xi > xj hold, and then apply assignment xi = xi - xj. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input

The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x1, x2, ..., xn (1 ≤ xi ≤ 100).

Output

Output a single integer — the required minimal sum.

Examples
input
Copy
2
1 2
output
Copy
2
input
Copy
3
2 4 6
output
Copy
6
input
Copy
2
12 18
output
Copy
12
input
Copy
5
45 12 27 30 18
output
Copy
15
Note

In the first example the optimal way is to do the assignment: x2 = x2 - x1.

In the second example the optimal sequence of operations is: x3 = x3 - x2, x2 = x2 - x1.



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 1;
int n, a[N];

int get_min() {
  int ret = -1, mn = 1e9;
  for(int i = 0; i < n; ++i)
    if(mn > a[i])
      mn = a[i], ret = i;
  return ret;
}

int get_max() {
  int ret = -1, mx = -1;
  for(int i = 0; i < n; ++i)
    if(a[i] > mx)
      mx = a[i], ret = i;
  return ret;
}

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i);

  for(int i = 0, mn, mx; i < 100000; ++i) {
    mn = get_min();
    mx = get_max();
    if(mn != mx)
      a[mx] -= a[mn];
  }

  int sum = 0;
  for(int i = 0; i < n; ++i)
    sum += a[i];

  printf("%d\n", sum);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
1 2

Output

x
–
+
cmd
2
Advertisements

Demonstration

Codeforces Solution-Fox and Number Game-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+