Codeforces Round 677 (Div.3)

A. Boring Apartments

입력되는 $x$가 1일때, boring apartments는 1, 11, 111, 1111이므로 1이 등장하는 횟수는 1+2+3+4 = 10이다.

따라서, $x-1$까지 등장하는 숫자의 횟수는 10의 배수임을 알 수 있다.

이때, $len$을 $x$의 길이라고 한다면 우리가 구해야할 정답은 다음의 식을 만족해야 한다.

$answer = 10\cdot(dig-1)+\frac{len(len+1)}{2}$, ($dig$은 입력된 $x$의 반복되는 숫자)

#include <iostream>
#define endl '\n'
using namespace std;

void solve() {
  string x;
  cin>>x;
  int dig=x[0]-'0'-1;
  int len=x.size();
  cout<<dig*10+len*(len-1)/2<<endl;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

B. Yet Another Bookself

간단하게 1과 1사이의 0의 수를 세어주면 된다.

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];

  while(a.back()==0) a.pop_back(); // 뒤의 0제거

  reverse(a.begin(),a.end());
  while(a.back()==0) a.pop_back(); // 앞의 0제거

  cout<<count(a.begin(),a.end(), 0)<<endl;
  return;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

C. Dominant Piranha

이 문제의 경우 모든 피라냐들이 같은 사이즈일 경우 -1이 정답이 된다. 그리고 적어도 피라냐 두 마리가 사이즈가 다르다면 정답은 반드시 존재한다. 그 이유는 다음과 같다.

1. 가장 큰 사이즈를 가진 피라냐는 반드시 정답이 된다. 다른 피라냐를 모두 먹을 수 있기 때문이다.
2. 만약 가장 큰 사이즈가 1, 가장 작은 사이즈를 0이라 하면 01-페어 또는 10-페어는 반드시 존재한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve() {
  int n;
  cin>>n;
  vector<int> a(n);
  int mx=0;

  for(int i=0;i<n;i++) {
    cin>>a[i];
    mx=max(mx,a[i]);
  }

  int idx=-1;
  for(int i=0;i<n;i++) {
    if(a[i]!=mx) continue;
    // 왼쪽과 오른쪽에 가장 큰 사이즈의 피라냐가 없다면
    if(i>0 && a[i-1]!=mx) idx=i+1;
    if(i<n-1 && a[i+1]!=mx) idx=i+1;
  }

  cout<<idx<<endl;
}

int main() {
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

D. Districts Connection

문제는 다음과 같다.

마을에 $n$구역이 있고 $i$번째 구역은 $a_i$번째 도적 구역에 속한다.

구역 사이에 $n-1$개의 양방향 도로를 설치하여 모든 구역을 연결하고 싶지만 같은 도적 구역에 속한 구역이 연결되면 반란을 일으킨다.

그래서 모든 구역을 연결할 수 있고 연결된 구역은 다른 도적 구역에 속하도록 도로를 건설하려고 한다.

만약, $n-1$개의 도로를 설치하지 못할경우 불가능하다고 판단

먼저, 모든 구역이 같은 갱에 속하면 불가능하다. 그외의 경우 항상 가능하다. 그 이유는 다음과 같다.

• root가 1이라고 가정하자. 그리고 $a_i$≠$a_1$인 모든 $i$ 구역을 1과 연결하자. 그러면 1과 연결된 모든 구역은 $a_1$과 다른 갱의 구역이 된다.
• $a_i$가 $a_1$이 아닌 어떠한 $i$ 구역에 $a_1$인 모든 구역을 연결하게 되면 모든 구역을 연결시킬 수 있다.
• 따라서 위의 조건은 항상 참이다.

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &it : a) cin >> it;
  vector<pair<int, int> > res;
  int idx = -1;
  for (int i = 1; i < n; ++i) { // 1과 다른 갱의 구역 연결
    if (a[i] != a[0]) {
      idx = i;
      res.push_back(make_pair(1, i + 1));
    }
  }
  if (idx == -1) { // 모두 같은 갱이라면 연결 불가능
    cout << "NO" << endl;
    return;
  }
  for (int i = 1; i < n; ++i) { // 다른 갱과 1번 갱의 구역 연결
    if (a[i] == a[0]) {
      res.push_back(make_pair(idx + 1, i + 1));
    }
  }
  cout << "YES" << endl;
  for (auto it : res) cout << it.first << " " << it.second << endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt", "r", stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}