[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]);
     }
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

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