Codeforces Round #677 (Div.3)

A. Boring Apartments
入力したxxxが1の場合boringマンションは1,11,111,1111であるため,1出現回数は1+2+3+4=10である.
したがって,xから1 x−1 xから1までの数字の出現回数は10の倍数である.
この場合、lenlenlenをxxxの長さと呼ぶと、私たちが求めている正しい答えは以下の意識を満たさなければなりません.
答え=10⋅(dig-1)+len(len+1)2 answer=10cdot(dig-1)+frac{len(len+1)}{2}answer=10⋅(dig-1)+2 len+1),(digdigは入力したxxの重複数)

#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が正解ですそして、少なくとも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
問題は以下の通りです.
村にはnn区があり、第3区はaia iai第2盗賊区に属している.
区域間には双方向道路が設けられており、すべての区域を接続しようとしているが、同じ盗賊区域に属する区域が接続されると反乱を引き起こす.
だから私たちはすべての地域が接続できるように道路を建設し、接続された地域は別の盗賊区域に属します.
もし、n-1 n-1 n-道路を1本設置できない場合は、不可能とみなされます
まず、すべての地域が同じ鉱山に属しているわけにはいかない.他の状況はいつも可能だ.理由は以下の通り.

本が1であると仮定します.次にaia iai≠a 1 a 1 a 1 a 1 a 1のすべてのiii領域を1に接続する.すると、1に接続されたすべての領域がa 1 a 1 a 1 a 1 a 1 a 1 aおよび他のピットの領域となる.

aia iaiは、a 1 a 1 a 1 a 1 a 1 a 1の任意のiiii領域をa 1 a 1 a 1 a 1 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;
}