[코드포스 / Codeforces] Round #886 (Div. 4)

Codeforces Round #886 (Div. 4)

문제 세트는 여기서 확인할 수 있다.

---

문제

A. To My Critics (AC / 2 min)

a, b, c 중 두개의 합이 10 이상이면 yes 아니면 no를 출력하는 문제.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b >= 10 || a + c >= 10 || b + c >= 10)
      cout << "yes\n";
    else
      cout << "no\n";
  }
  return 0;
}

 

B.Ten Words of Wisdom (AC / 7 min)

n개의 a, b 입력 중 a가 10 이하이면서 b가 가장 큰 입력이 몇 번째 입력인지 출력하는 문제.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, t = 0, idx = -1;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int a, b;
      cin >> a >> b;
      if (a <= 10 && b > t) {
        t = b;
        idx = i + 1;
      }
    }
    cout << idx << '\n';
  }
  return 0;
}

 

C.Word on the Paper (AC / 17 min)

8×8 배열에서 가로 또는 세로로 쓰여있는 문자열이 무엇인지 출력하는 문제.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  int dx[] = {0, 0, 1, -1};
  int dy[] = {1, -1, 0, 0};
  while (t--) {
    string s[8];
    int visited[8][8] = {0};
    for (int i = 0; i < 8; i++)
      cin >> s[i];
    for (int i = 0; i < 8; i++)
      for (int j = 0; j < 8; j++) {
        if (s[i][j] != '.') {
          cout << s[i][j];
          visited[i][j] = 1;
          for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8)
              continue;
            if (s[nx][ny] == '.' || visited[nx][ny])
              continue;
            else {
              cout << s[nx][ny];
              visited[nx][ny] = 1;
              i = nx;
              j = ny;
            }
          }
        }
      }
    cout << '\n';
  }
  return 0;
}

 

F.We Were Both Children (AC+1 / 1 hour 4 min)

모든 개구리가 0에서 출발하고, i번째 개구리는 a[i] 씩 점프한다. 딱 한 군데 덫을 놓아 가장 많이 잡기 위해서 에라토스테네스의 체를 활용한다.

x번 index에 도착하는 개구리가 y마리라면 x + x × i (i ≥ 0) 인 곳에 도착하는 개구리도 y마리다.

위 과정을 반복하다보면 점프거리가 공배수인 위치에서 마리수가 늘어날 것이고, 이 위치에서 또 위 과정을 반복한다.

만들어진 체 배열에서 최댓값을 출력하는 문제.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 0, x; i < n; i++) {
      cin >> x;
      if (x <= n)
        a[x]++;
    }
    vector<int> sieve(n + 1, 0);
    for (int i = 1; i <= n; i++)
      if (a[i])
        for (int x = i; x <= n; x += i)
          sieve[x] += a[i];
    cout << *max_element(sieve.begin(), sieve.end()) << '\n';
  }
  return 0;
}

---

총평

7월 21일에 친구네 집에서 하루 지낼 때 참가했었다. 약 두달만에 참가한 콘테스트 치곤 지금 봐도 나름 잘 했던 것 같다. 쉬운 구현이 많아서 재밌게 했다.

참가한 후기를 꼭 다 써야겠다고 생각만 하고 하지 않았는데, 지금 다시 복기하면서 써보는 중이다. 생각보다 나쁘지 않은 복습인 것 같다.