TopCoder SRM 425 Div 2 (완료)

어제 새벽 1시에 열린 매치.. -_-;;
미국 day light saving time이 끝나면서 시간이 죄다 1시간 뒤로 밀렸다.. ㅠ_ㅠ
이거.. 아침에 출근해야되는데.. 밤새 머하는건지.. ㅠ_ㅠ;;

이번에는 div2에서 했는데.. 좀 아쉬운감이 있지만.. 나름 성적이 좋았다..
250은 잽싸게 코딩완료하고 서밋했는데.. 아무래도 찜찜해서.. 문제를 다시읽어보니..
내가 문제를 잘못 이해하고있었다.. 덕분에 또 리서밋..;; 요즘 매번 리서밋때문에 고전한다.. ㅠ_ㅠ
500은 좀 읽다가 어려운거같아서 포기하고 1000을 열었는데..
솔루션이 잘 안떠오르는 500과 코딩이 좀 짜증나는 1000중에 뭘 풀까 하다가.. 그냥 1000을 노렸다..
나중에 1000도 서밋하고 시간이 좀 남길래 500도 대충 풀어서 서밋했는데..
심혈을 기울인 1000은 fail하고 대충 푼 500이 pass해버렸다.. 이거 멍미..;;

250을 처음에 나처럼 문제를 잘못이해한 사람이 많아서 챌로만 무려 225점을 얻었다..
덕분에 낮은 코딩점수에도 불구하고 괜찮은 성적을 올렸다..

흠.. 1000점짜리는 backtracking으로 풀었는데.. 왜 WA가 났을까.. ?.?

Level1 - InverseFactoring

Problem Statement
     
A positive integer a is a proper factor of n if and only if n is a multiple of a and a does not equal 1 or n. You are given a int[] factors containing all the proper factors of some integer n. Return n.
Definition
   
Class:
InverseFactoring
Method:
getTheNumber
Parameters:
vector <int>
Returns:
int
Method signature:
int getTheNumber(vector <int> factors)
(be sure your method is public)
   
 
Constraints
-
factors will contain between 1 and 50 elements, inclusive.
-
factors will be a valid set of proper factors of some number n, where n is between 2 and 1,000,000, inclusive.
-
All elements in factors will be distinct.
Examples
0)
 
   
{2}
Returns: 4
The factors of 4 are 1, 2 and 4. Among them, only 2 is a proper factor.
1)
 
   
{4,2}
Returns: 8
The factors of 8 are 1, 2, 4, and 8. Among them, 2 and 4 are proper factors.
2)
 
   
{3,4,2,12,6,8}
Returns: 24
The proper factors of 24 are 2, 3, 4, 6, 8 and 12.
3)
 
   
{14,26456,2,28,13228,3307,7,23149,8,6614,46298,56,4,92596}
Returns: 185192
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

input으로 어떤수 N의 proper factor가 들어온다.. proper factor란 1과 N을 제외한 N의 약수이다.. 이 factor들을 이용하여 N을 구하기..

나는 주어진 factor의 모든 lcm을 구한다음 그게 factor중 가장 큰 수와 같다면 가장 작은 factor를 한번 더 곱해서 구했다.. input이 1가 N을 제외한 factor이므로.. 나중에 다른 사람 코드를 보니.. 간단히 factors 중에서 가장 작은수와 가장 큰수를 곱하면 되는거였다.. 음.. 왜그렇지.. -_-

많은 사람들이 문제를 잘못 이해해서 마구 fail 했다.. 예를들어 input이 {3} 인 경우 답은 9가 되어야하는데 6으로 출력한 사람이 많았다.. 6이 답이 되려면 input은 {2, 3} 이 되어야하는데..;; 덕분에 코드중에 *2 를 시도한 사람을 몽땅 챌해버렸다.. ㅋ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int gcd(int a, int b)
  9 {
 10     if (b == 0)
 11         return a;
 12     return gcd(b, a % b);
 13 }
 14
 15 int lcm(int a, int b)
 16 {
 17     return (int)((long long)a * b / gcd(a, b));
 18 }
 19
 20 class InverseFactoring {
 21 public:
 22
 23 int getTheNumber(vector <int> factors)
 24 {
 25     int size;
 26     int i;
 27     int res;
 28     int max1, min1;
 29     size = factors.size();
 30     res = 1;
 31     max1 = 1;
 32     min1 = 2000000000;
 33     for (i = 0; i < size; i++) {
 34         if (factors[i] > max1)
 35             max1 = factors[i];
 36         if (factors[i] < min1)
 37             min1 = factors[i];
 38         res = lcm(res, factors[i]);
 39     }
 40     if (max1 == res)
 41         return res * min1;
 42     return res;
 43 }
 44
 45 };

Level2 - CrazyBot

Problem Statement
     
An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.
The robot's path is considered simple if it never visits the same point more than once. (The robot's starting point is always the first visited point.) Return a double containing the probability that the robot's path is simple. For example, "EENE" and "ENW" are simple, but "ENWS" and "WWWWSNE" are not ('E', 'W', 'N' and 'S' represent east, west, north and south, respectively).
Definition
   
Class:
CrazyBot
Method:
getProbability
Parameters:
int, int, int, int, int
Returns:
double
Method signature:
double getProbability(int n, int east, int west, int south, int north)
(be sure your method is public)
   
 
Notes
-
Your return must have relative or absolute error less than 1E-9.
Constraints
-
n will be between 1 and 14, inclusive.
-
east will be between 0 and 100, inclusive.
-
west will be between 0 and 100, inclusive.
-
south will be between 0 and 100, inclusive.
-
north will be between 0 and 100, inclusive.
-
The sum of east, west, south and north will be 100.
Examples
0)
 
   
1
25
25
25
25
Returns: 1.0
The robot only takes one step, so it never visits a point more than once.
1)
 
   
2
25
25
25
25
Returns: 0.75
The robot will visit its starting point twice only if the two moves are in opposite directions.
2)
 
   
7
50
0
0
50
Returns: 1.0
Here, the only possible directions are north and east, so the robot will never visit the same point twice.
3)
 
   
14
50
50
0
0
Returns: 1.220703125E-4
Here, the only possible directions are east and west. The only two available paths are "EEEEEEEEEEEEEE" and "WWWWWWWWWWWWWW". The probability is equal to 2 / (2^14).
4)
 
   
14
25
25
25
25
Returns: 0.008845493197441101
The probability is quite small for n=14.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

어떤 로봇이 동, 서, 남, 북으로 각각 이동할 확률이 percentage로 주어진다.. N칸을 이동할 경우 로봇이 지났던 지점을 다시 지나지 않고 N칸을 다 이동할 확률 구하기..

backtracking으로 풀었다.. -_-;; 우선 중앙에서 시작해서 한번 갔던곳을 다시 지나지 않도록 해서 모든 방향으로 다 이동해보았다.. 그리고 N step 이동했을때 그동안의 path를 이용해서 확률을 구했다.. -_- N이 14라서 좀 망설이긴 했지만.. 한번 지난 곳은 다시 안지나므로.. 답은 14! 보다 훨씬 작을거라고 믿고.. 그냥 몽땅 다구했다.. ㅋㅋ 1000점 문제도 backtracking으로 접근했는데.. 오늘 backtracking 날인가..;;

사실 이문제는 처음에 잘 생각을 못했는데.. 1000점짜리 코딩하고나니 해결방법이 떠오른 문제..;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 char check[100][100];
  9 int path[100];
 10 double p[5];
 11 double sum;
 12 int n;
 13
 14 void dfs(int u, int v, int cnt, int di)
 15 {
 16     int i;
 17     double temp;
 18     path[cnt] = di;
 19     if (cnt == n) {
 20         temp = 1.0;
 21         for (i = 1; i <= cnt; i++) {
 22             temp *= p[path[i]];
 23         }
 24         sum += temp;
 25         return ;
 26     }
 27     if (check[u+1][v] == 0) {
 28         check[u+1][v] = 1;
 29         dfs(u+1, v, cnt+1, 1);
 30         check[u+1][v] = 0;
 31     }
 32     if (check[u][v+1] == 0) {
 33         check[u][v+1] = 1;
 34         dfs(u, v+1, cnt+1, 2);
 35         check[u][v+1] = 0;
 36     }
 37     if (check[u-1][v] == 0) {
 38         check[u-1][v] = 1;
 39         dfs(u-1, v, cnt+1, 3);
 40         check[u-1][v] = 0;
 41     }
 42     if (check[u][v-1] == 0) {
 43         check[u][v-1] = 1;
 44         dfs(u, v-1, cnt+1, 4);
 45         check[u][v-1] = 0;
 46     }
 47 }
 48
 49 class CrazyBot {
 50 public:
 51
 52 double getProbability(int N, int east, int west, int south, int north)
 53 {
 54     p[1] = (double)east / 100.0;
 55     p[2] = (double)north / 100.0;
 56     p[3] = (double)west/ 100.0;
 57     p[4] = (double)south/ 100.0;
 58     n = N;
 59
 60     sum = 0;
 61     memset(check, 0, sizeof(check));
 62     check[50][50] = 1;
 63     check[51][50] = 1;
 64     dfs(51, 50, 1, 1);
 65     check[51][50] = 0;
 66
 67     check[50][51] = 1;
 68     dfs(50, 51, 1, 2);
 69     check[50][51] = 0;
 70
 71     check[49][50] = 1;
 72     dfs(49, 50, 1, 3);
 73     check[49][50] = 0;
 74
 75     check[50][49] = 1;
 76     dfs(50, 49, 1, 4);
 77     check[50][49] = 0;
 78 printf("sum = %lf\n", sum);
 79     return sum;
 80 }
 81
 82 };

Level3 - PiecesMover

Problem Statement
     
You are given a 5x5 board containing at most 5 pieces. Your task is to move the pieces so that the cells occupied by them form a connected component. A connected component is a set of cells where each pair of cells is connected by at least one path. Consecutive cells in a path must all be adjacent. Two cells are called adjacent if they share a common edge.
You are given a String[] board, where the j-th character of the i-th element is '*' if cell (i, j) is occupied by a piece and '.' otherwise. Return the minimum number of moves required to achieve your goal. Each move consists of moving one piece to an adjacent empty cell.
Definition
   
Class:
PiecesMover
Method:
getMinimumMoves
Parameters:
vector <string>
Returns:
int
Method signature:
int getMinimumMoves(vector <string> board)
(be sure your method is public)
   
 
Constraints
-
board will contain exactly 5 elements.
-
Each element of board will contain exactly 5 characters.
-
Each character in board will be either '.' or '*'.
-
board will contain between 1 and 5 '*' characters, inclusive.
Examples
0)
 
   
{".....",
 "..**.",
 ".....",
 "...*.",
 "....."}
Returns: 1
 + + + + +
         
 + + O O +
         
 + + + O +
       | 
 + + + . +
         
 + + + + +
1)
 
   
{".....",
 ".....",
 ".**..",
 ".*...",
 "**..."}
Returns: 0
The cells occupied by pieces have already formed a connected component.
2)
 
   
{"*...*",
 ".....",
 ".....",
 ".....",
 "*...*"}
Returns: 12
 . + +-+-.
 |   |   
 + + + + +
 |   |   
 +-O O O-+
         |
 + O + + +
   |     |
 .-+ + + .
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

5 by 5 board에 N개의 * 이 있다.. 이 * 들을 이동시켜서 모두 connected 된 상태로 만들고 싶다.. connected는 서로 위 아래 양옆 중 하나의 방향으로 이웃한 경우.. *들의 최소 이동 거리 구하기

우선 backtracking으로 모든 가능한 connected component를 다 구하고.. 현재 놓여있는 점들을 구한 CC에 매칭을 시킨다.. 어떤 매칭이 최적인지 모르므로 이 경우에도 모든 경우를 다 해본다.. 2중 backtracking이 될수도 있겠지만.. -_-; next_permutation이란 편리한 함수가 있으므로 이를 이용하면 쉽다..

실제 매치때 WA받은 이유는.. 다음 상태공간을 탐색할 때, 가장 마지막에 넘어왔던 위치에서의 이웃한 4방향만 구했기 때문이다.. 지금까지 놓여진 모든 piece의 이웃을 다 탐색해야 한다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 typedef struct _p {
  9     int x, y;
 10 } POINT;
 11
 12 POINT pt[5], pt2[5];
 13 int r[10][10];
 14 int min1, sum;
 15 int n;
 16
 17 void dfs(int u, int v, int cnt)
 18 {
 19     int idx[5];
 20     int i, j, k;
 21
 22     if (cnt == n) {
 23         for (i = 0; i < n; i++) {
 24             idx[i] = i;
 25         }
 26         k = 0;
 27         for (i = 0; i < 5; i++) {
 28         for (j = 0; j < 5; j++) {
 29             if (r[i][j] == 1) {
 30                 pt2[k].x = i;
 31                 pt2[k].y = j;
 32                 k++;
 33             }
 34         }
 35         }
 36         do {
 37             sum = 0;
 38             for (i = 0; i < n; i++) {
 39                 sum += abs(pt[idx[i]].x-pt2[i].x) + abs(pt[idx[i]].y-pt2[i].y);
 40             }
 41             if (sum < min1)
 42                 min1 = sum;
 43         } while (next_permutation(idx, idx+n));
 44         return ;
 45     }
 46     for (u = 0; u < 5; u++) {
 47     for (v = 0; v < 5; v++) {
 48     if (r[u][v]) {
 49     if (u+1 < 5 && r[u+1][v] == 0) {
 50         r[u+1][v] = 1;
 51         dfs(u+1, v, cnt+1);
 52         r[u+1][v] = 0;
 53     }
 54     if (v+1 < 5 && r[u][v+1] == 0) {
 55         r[u][v+1] = 1;
 56         dfs(u, v+1, cnt+1);
 57         r[u][v+1] = 0;
 58     }
 59     if (v-1 >= 0 && r[u][v-1] == 0) {
 60         r[u][v-1] = 1;
 61         dfs(u, v-1, cnt+1);
 62         r[u][v-1] = 0;
 63     }
 64     if (u-1 >= 0 && r[u-1][v] == 0) {
 65         r[u-1][v] = 1;
 66         dfs(u-1, v, cnt+1);
 67         r[u-1][v] = 0;
 68     }
 69     }
 70     }
 71     }
 72 }
 73
 74 class PiecesMover {
 75 public:
 76
 77 int getMinimumMoves(vector <string> board)
 78 {
 79     char map[10][10];
 80     int i, j, k;
 81     for (i = 0; i < 5; i++) {
 82         strcpy(map[i], board[i].c_str());
 83     }
 84     k = 0;
 85     for (i = 0; i < 5; i++) {
 86         for (j = 0; j < 5; j++) {
 87             if (map[i][j] == '*') {
 88                 pt[k].x = i;
 89                 pt[k].y = j;
 90                 k++;
 91             }
 92         }
 93     }
 94     n = k;
 95     memset(r, 0, sizeof(r));
 96     min1 = 2000000000;
 97     for (i = 0; i < 5; i++) {
 98         for (j = 0; j < 5; j++) {
 99             if (r[i][j] == 0) {
100                 r[i][j] = 1;
101                 dfs(i, j, 1);
102                 r[i][j] = 0;
103             }
104         }
105     }
106 printf("ret = %d\n", min1);
107     return min1;
108 }
109
110 };