[editorial] Online Round 1C

  • Toivoa
    Toivoa

    [A - Rope Intranet]
    양 건물을 잇는 rope들이 주어질 때 rope의 교차점 수를 세는 문제입니다. 세 개 이상의 rope가 한 점에서 만나지 않는다는 조건이 있습니다.
    (Ai, Bi) pair를 Ai 기준으로 소트한 후에 교차하는지 세어보는 식으로 풀었습니다. 시간상 소트하지 않고 다 세어봐도 충분히 나올 것이라고 봅니다.

    #include <algorithm>
#include <cstdio> 
using namespace std;
struct wire
{
 int s, e;
 bool operator < (const wire& rhs) const
 {
  return s < rhs.s;
 }
};
int main()
{
 int t, cases = 0;
 scanf("%d", &t);
 while (t--)
 {
  int n;
  wire w[1000];
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
   scanf("%d%d", &w[i].s, &w[i].e);
  sort(w, w + n);
  int res = 0;
  for (int i = 0; i < n; ++i)
  {
   for (int j = i + 1; j < n; ++j)
   {
    if (i == j) continue;
    if (w[i].e > w[j].e)
     ++res;
   }
  }
  printf("Case #%d: %d\n", ++cases, res);
 }
}

    [B - Load Testing]
    문제 이해하기가 힘든데, 문제 설명을 하는것도 어렵네요. 문제 한번 읽어보신 후에 보세요.
    문제에 대해서 간단히 써보면 적어도 L명이 (a time without any errors) 사용가능하고, P명이 사용할 수 없다는 것을 알고 있습니다.
    만약 적어도 a명이 문제 없이 (a time without any errors) 사용가능하다면, a * C명은 사용할 수 없다고 합니다. (문제를 이해해보면 a * C - 1명까지는 사용 가능합니다.)
    load test를 통해서 최대 몇명까지 사용가능한지 알아보려고 합니다. load test를 optimal하게 한다고 할 때 최대의 load test 회수는 몇번인지 구하는 문제입니다.
    문제 이해하기는 어렵지만, 풀이는 쉽습니다. 모두 통과한다고 가정하고, L * C 부터 차례대로 load test를 해나갈 때의 값들이 optimal하게 load test를 했을 때 (모든 경우를 포함하는) load test와 같아집니다.
    optimal한 전략은 이 load test를 tree 구조를 그리듯이 가운데부터 해나가는 것이 됩니다. :)

    #include <cstdio>
#include <algorithm> 
using namespace std;
typedef long long ll;
ll s2[60];
int main()
{
 s2[0] = 1;
 for (int i = 1; i < 60; ++i)
  s2[i] = s2[i - 1] << 1;
 int t, cases = 0;
 scanf("%d", &t);
 while (t--)
 {
  ll l, p, c;
  scanf("%I64d%I64d%I64d", &l, &p, &c);
  int x = 0;
  while (l * c < p)
  {
   l *= c;
   ++x;
  }
  int res = upper_bound(s2, s2 + 60, ll(x)) - s2;
  printf("Case #%d: %d\n", ++cases, res);
 }
}

    [C - Making Chess Boards]
    체스판이 주어질 때 가능한 최대의 체스판부터 잘라내는 것이 문제입니다. 만약 같은 크기의 체스판이 여러개 있다면 가장 위(topmost)에 있는 것부터 자르며, 이 것이 여러 개 있다면 가장 왼쪽(leftmost) 것부터 자릅니다. 문제의 그림을 보시면 한눈에 이해하실 수 있습니다. :)
    일단 체스판의 특정 위치에서 시작해서 임의의 크기로 잘라낼 수 있는지를 계산해야 합니다.
    체스판이 array A에 있고,
    T[K, X, Y]: K의 크기로 왼쪽 위의 좌표가 (X, Y)일 때 자를 수 있는가? 로 정의할 때,
    T[1, x, y] 는 항상 가능하며, T[2, x, y]는 (A[x, y] == A[x + 1, y + 1] && A[x, y] != A[x + 1, y] && A[x, y] != A[x, y + 1]) 임을 쉽게 알 수 있습니다.
    T[k, x, y] = T[k - 1, x, y] && T[k - 1, x + 1, y] && T[k - 1, x, y + 1] && Tk - 1, x + 1, y + 1 이 됩니다. 이는 조금만 생각해보시면 알 수 있으니 생략합니다.
    이렇게 만들 수 있는 체스판을 구한 후에 큰 것부터 잘라내는데, 잘라내다 보면 이미 잘라낸 체스판과 겹치는지 체크가 필요합니다. 이 것은 체스판을 자르는 시점에서 자르려는 체스판의 네 모서리가 이미 잘려나갔는지 체크해보시면 됩니다. (이미 잘려 나간 체스판은 항상 현재 자르려는 체스판의 크기보다 더 크거나 같기 때문에 네 모서리만 봐도 됩니다.)
    아래 소스코드는 초기화에 들어가는 시간을 절약하기 위해서 초기화를 하지 않아도 동작하도록 작성하였습니다.

    #include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int table[513][512][512];
int ans[513];
int res;
int a[512][512];
int t2[512][512];
int main()
{
 int t, cases = 0;
 scanf("%d", &t);
 while (t--)
 {
  scanf("%d%d", &n, &m);
  ++cases;
  memset(&ans[0], 0, sizeof(ans));
  for (int i = 0; i < n; ++i)
  {
   char cc[513];
   scanf("%s", cc);
   for (int j = 0; j < m; j += 4)
   {
    int x = -1;
    if (cc[j / 4] < 58)
     x = cc[j / 4] - 48;
    else
     x = cc[j / 4] - 55;
    for (int k = 3; k >= 0; --k)
    {
     a[i][j + k] = (x % 2);
     x /= 2;
    }
   }
  }
  // fill 1
  for (int i = 0; i < n; ++i)
   for (int j = 0; j < m; ++j)
    table[1][i][j] = cases;
  // fill 2
  for (int i = 0; i < n - 1; ++i)
   for (int j = 0; j < m - 1; ++j)
    table[2][i][j] = ((a[i][j] == a[i + 1][j + 1]) && (a[i][j] != a[i + 1][j]) && (a[i][j] != a[i][j + 1])) ? cases : 0;
  // fill 3 to n
  for (int k = 3; k <= n; ++k)
   for (int i = 0; i < n - k + 1; ++i)
    for (int j = 0; j < m - k + 1; ++j)
     table[k][i][j] = ((table[k - 1][i][j] == cases) && (table[k - 1][i + 1][j] == cases) && (table[k - 1][i][j + 1] == cases) && (table[k - 1][i + 1][j + 1] == cases)) ? cases : 0;
  res = 0;
  for (int k = n; k >= 1; --k)
  {
   for (int i = 0; i < n - k + 1; ++i)
    for (int j =  0; j < m - k + 1; ++j)
     if (table[k][i][j] == cases)
     {
      if (t2[i][j] != cases && t2[i + k - 1][j] != cases && t2[i][j + k - 1] != cases && t2[i + k - 1][j + k - 1] != cases)
      {
       ans[k]++;
       for (int q = i; q < i + k; ++q)
        for (int w = j; w < j + k; ++w)
         t2[q][w] = cases;
      }
     }
   if (ans[k] != 0) ++res;
  }
  printf("Case #%d: %d\n", cases, res);
  for (int k = n; k >= 1; --k)
   if (ans[k] != 0)
    printf("%d %d\n", k, ans[k]);
 }
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.