Codeforces Round #730 (Div. 2) AB 풀이

A. Exciting Bets

 

문제 설명 + 풀이

a, b가 주어집니다. 이때 움직임 : (a, b를 1 증가 or a, b가 0이 아니면 1을 감소)해서 gcd(a, b)의 최대값과 gcd(a, b)를 만들 수 있는 최소의 움직임 횟수를 출력하시오. 만약 gcd(a, b)가 무한대라면 0 0을 출력

1. a == b라면 0 0을 출력 (gcd(a, b)가 무한대 일 때)

2. gcd(a, b)의 최대는 (a > b)일때 a - b가 최대가 된다.

3. 최소 움직임 : (a > b)일 때 b % (a - b)가 (a - b) / 2보다 작거나 같다면 움직임의 최소는 b % (a - b)이고, 크다면     (a - b) - b % (a - b)가 된다.

소스 코드(. cpp)

#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
 
typedef long long ll;
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
 
    int t; cin >> t;
    while (t--) {
        ll a, b; cin >> a >> b;
 
        if (a == b)
            cout << 0 << " " << 0 << "\n";
        else {
            if (a < b)
                swap(a, b);
 
            ll ret = a - b, cnt = 0;
            if (b % ret <= ret / 2)
                cnt = b % ret;
            else
                cnt = ret - b % ret;
 
            cout << ret << " " << cnt << "\n";
        }
    }
}

 

 

B. Plus and Multiply

문제 설명 + 풀이

n개의 숫자가 주어지고, Ai에서 Aj로 숫자를 움직일 수 있다. 이때

위의 식이 가장 최소가 되는 값을 찾으시오.

ai의 숫자에서 a(i+1~n)까지 뺀 값의 절대값이 최소가 되려면 숫자의 차이가 작거나 같아야 됩니다. 만약 8 3 6 11 5 2 1 7 10 4가 입력 되면 이것을 5 5 5 6 6 6 6 6 6 6으로 바꿔야 최소가 됩니다.

소스 코드(. cpp)

#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
 
typedef long long ll;
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        
        ll a = 0;
        for (int i = 0; i < n; i++) {
            ll tmp; cin >> tmp;
            a += tmp;
        }
 
        ll cnt = a % n;
        cout << (n - cnt) * cnt << "\n";
    }
}