algospot.com :: 과거 게시판: [editorial] Onlind Round 1B

[editorial] Onlind Round 1B

R1A에서 999/1000 으로 올라간 기념으로 연습 삼아 R1B 풀어봤습니다. :)
[A. File Fix-it]
현재 디렉토리의 상태가 주어지고, 추가할 디렉토리들이 주어질 때 mkdir 명령을 최소 몇 번 수행해야 하는지 묻는 문제입니다. 코드잼의 특성상 실제로 mkdir을 하는 코드를 작성한 분도 있는데...
C++로 푼다면 다음과 같이 적절히 string parsing을 해서 directory를 구성해주시면 됩니다.

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <cstring> 
using namespace std;
struct dir
{
 map<string, dir*> childs;
 int add(char *c)
 {
  char cc[1000];
  int pt = 0;
  int ret = 0;
  while (*c != 0 && *c != '/')
  {
   cc[pt++] = *c;
   c++;
  }
  cc[pt] = 0;
  map<string, dir*>::iterator it = childs.find(cc);
  dir* child = NULL;
  if (it == childs.end())
  {
   child = new dir;
   childs.insert(make_pair(string(cc), child));
   ++ret;
  }
  else
   child = it->second;
  if (*c == '/')
   ret += child->add(c + 1);
  return ret;
 }
 ~dir()
 {
  map<string, dir*>::iterator it;
  for (it = childs.begin(); it != childs.end(); ++it)
  {
   delete it->second;
  }
 }
};
int main()
{
 dir* root = NULL;
 int t, cases = 0;
 int n, m;
 int res;
 char cc[10000];
 scanf("%d", &t);
 while (t--)
 {
  root = new dir();
  scanf("%d%d", &n, &m);
  res = 0;
  for (int i = 0; i < n; ++i)
  {
   scanf("%s", cc);
   root->add(cc + 1);
  }
  for (int i = 0; i < m; ++i)
  {
   scanf("%s", cc);
   res += root->add(cc + 1);
  }
  printf("Case #%d: %d\n", ++cases, res);
  delete root;
 }
}

[B. Picking Up Chicks]
문제 읽기가 더 힘들었던 문제인데, 간단히 설명하면 병아리들이 한 쪽으로 이동하고 있을 때 시간 T까지 B의 위치에 최소한 K 마리의 병아리가 도착할 수 있는지, 그 때에 필요한 최소의 swap 회수를 묻는 문제입니다.
swap에 대해서는 문제에서는 두 병아리가 만났을 때 한 병아리를 집어서 앞으로 넘겨준다. 라는 식으로 설명되어 있습니다. swap에 걸리는 시간이 0이기 때문에 문제에서 세 병아리가 한번에 만나면 하나씩 넘긴다는 말은 무시하셔도 문제 푸시는데 아무 지장이 없습니다.
간단히 설명하면, 가장 멀리(B에 가장 가까이) 있는 병아리부터 보면서 시간 T 안에 B에 도달할 수 있는지를 보고, 도달할 수 있다면 앞에 있는 병아리들 중에 B까지 도달할 수 없는 병아리들만 swap해서 넘어가면 됩니다. (B에 도달할 수 있는 병아리들은 swap하지 않아도 됩니다! 이유는 생략.)
이렇게 해서 K마리까지 B 위치에 도달할 수 있게 되면 됩니다. :)

#include <cstdio> 
int main()
{
 int t, cases = 0;
 scanf("%d", &t);
 while (t--)
 {
  int n, k, b, t;
  int x[50], v[50];
  scanf("%d%d%d%d", &n, &k, &b, &t);
  for (int i = 0; i < n; ++i)
   scanf("%d", &x[i]);
  for (int i = 0; i < n; ++i)
   scanf("%d", &v[i]);
  int arrival = 0, res = 0, jmp = 0;
  for (int i = n - 1; i >= 0; --i)
   if (x[i] >= b - t * v[i])
   {
    arrival++;
    res += jmp;
    if (arrival == k) break;
   }
   else
    ++jmp;
  printf("Case #%d: ", ++cases);
  if (arrival == k)
   printf("%d\n", res);
  else
   printf("IMPOSSIBLE\n");
 }
}

[C. Your Rank is Pure]
문제는 {2, ..., N} 까지의 숫자의 subset을 선택했을 때 N이 pure인 subset의 가지 수를 세는 문제입니다. N이 pure라는 것은 문제의 도입 부분에서와 같이 소수의 집합에서 127은 31번째 소수이고, 31은 11번째 소수이고, 11은 5번째 소수이고, 5는 3번째 소수이고, 3은 2번째 소수, 2는 첫번째 소수 와 같은 식으로 1이 나올 때까지 그 집합 내에서 벗어나지 않는 경우를 말합니다.
저는 다음과 같은 table을 만들어서 풀었습니다.
T[x, y]: x를 subset의 y번째 두었을 때의 가지 수.
T[i, 1] = 1 // trivial.
T[i, j] = sum(T[j, k] * C[i - j - 1, j - 1 - k]) // (1 <= k < j). C는 조합입니다.
-> i를 j번째 놓는다면 j는 반드시 그 subset에 있어야 합니다. (j를 k번째에 놓을 때의 가지 수) * ([k + 1 ... i - 1]의 빈 공간을 채울 수 있는 경우의 수) 들의 합이 됩니다.
소스코드는 다음과 같습니다.

#include <iostream> 
using namespace std;
typedef long long ll;
ll c[501][501];
ll a[501][501];
int main()
{
 int t, n;
 int cases = 0;
 c[0][0] = 1;
 for (int i = 1; i < 501; ++i)
 {
  for (int j = 0; j <= i; ++j)
  {
   if (j == 0 || j == i)
    c[i][j] = 1;
   else
    c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 100003;
  }
 }
 for (int i = 2; i < 501; ++i)
 {
  a[i][1] = 1;
  for (int j = 2; j < i; ++j)
  {
   ll x = 0;
   for (int k = 1; k < j; ++k)
   {
    x += a[j][k] * c[i - j - 1][j - 1 - k];
    x %= 100003;
   }
   a[i][j] = x;
  }
 }
 scanf("%d", &t);
 while (t--)
 {
  scanf("%d", &n);
  int r = 0;
  for (int i = 0; i < n; ++i)
  {
   r += a[n][i];
   r %= 100003;
  }
  printf("Case #%d: %d\n", ++cases, r);
 }
}

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

14년 전

1개의 댓글이 있습니다.

Being

제가 짜 본 A 코드: http://ideone.com/DnhCq

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

SINCE 2007

다가오는 이벤트들

[editorial] Onlind Round 1B

1개의 댓글이 있습니다.