USACO 2021 January Contest - Silver

1. Searching for Soulmates

$a_i$를 $b_i$로 바꾸기 위한 연산의 최소 횟수를 구하라.

연산에는 3가지 종류가 있다.

• $a_i\leftarrow a_i \times 2$
• $a_i\leftarrow a_i / 2\ (\text{when}\ 2|a_i)$
• $a_i\leftarrow a_i+1$

$1\le N\le 10, 1\le a_i,b_i\le 10^{18}$

      

      

      

    
    

      <c++ />
    
#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std; using ll = long long;

const int N = 11;
int n;
pair<ll,ll> p[N];

int make_to(ll a, ll b) {
    if (a == 0) {
        if (b == 0) return 0;
        return __builtin_popcountll(b)+63-__builtin_clzll(b);
    }
    if (b < a) return 1e9;
    int mv = __builtin_clzll(a)-__builtin_clzll(b);
    ll ret = 1e9;
    for (int k = 0; k <= mv; k++) {
        if ((b>>k) >= a) {
            ret = min(ret,
                (b>>k)-a+k+__builtin_popcountll(b)-__builtin_popcountll((b>>k)<<k)
            );
        }
    }
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) cin >> p[i].first >> p[i].second;
    REP(i,1,n) {
        int answer = 1e9;
        for (int carry = 0; p[i].first >= 1; carry++, p[i].first >>= 1) {
            answer = min(answer,make_to(p[i].first,p[i].second)+carry);
            if (p[i].first == 1) break;
            if (p[i].first&1) p[i].first++, carry++;
        }
        cout << answer << '\n';
    }
}

2. Cow Frisbee

프리스비를 주고받을 수 있는 쌍들에 대한 거리들의 총 합을 구하라.

$h_i<h_j$에 대해, $\displaystyle \max_{i< k< j}h_k < \min (h_i,h_j)$를 만족하면 프리스비를 주고받을 수 있다. 물론 $|i-j|=1$이여도 가능하다.

단, $h$는 $1,2,\cdots,n$의 순열이다.

거리는 $j-i+1$로 계산한다.

$1\le N\le 3\cdot 10^5$

      

      

      

    
    

      <c++ />
    
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
using ll = long long;

const int N = 3e5+3;
int n;
int h[N];
int idx[N];
set<int> s;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) {
        cin >> h[i];
        idx[i] = i;
        s.insert(i);
    }
    sort(idx+1,idx+n+1,[](int x, int y){return h[x] < h[y];});
    ll answer = 0;
    REP(i,1,n-1) {
        if (not (*s.begin() == idx[i])) {
            answer += abs(*(--s.lower_bound(idx[i]))-idx[i])+1;
        }
        if (not (*(--s.end()) == idx[i])) {
            answer += abs(*(++s.lower_bound(idx[i]))-idx[i])+1;
        }
        s.erase(idx[i]);
    }
    cout << answer;
}

3. Cereal 2

$N$마리의 각 $i$ 소가 각각 제일 좋아하는 시리얼 $f_i$와 $s_i$가 있다. 각 소들은 줄을 서서 다음의 규칙을 시행한다.

• $f_i$가 남았으면 가져간다.
• $f_i$는 없는데, $s_i$가 있으면 $s_i$라도 가져간다.
• 둘 다 없으면 운다.

우는 소의 수의 최솟값과 우는 소의 수를 최소화 시키는 줄의 순서를 구하라.(여러개라면 그중 하나)

시리얼의 종류는 $1,2,\cdots,M$이 있다.

$1\le N, M\le 10^5$