TopCoder SRM 453.5 (??) Div 1

지난번에 스름 453 이 중간에 취소되는 바람에 오늘 새벽에 453.5 가 열렸다..
이번에도 무려 488 등.. rating 은 또 하락했다..
이러다가 올해안에 div2 가는거 아닌지 모르겠네..

rating 한번 화끈하게 올려본게 언제인지 가물가물하다..

Level1 - MazeMaker

Problem Statement
     
Mike Mazemeister has recently built a large maze in his backyard. The j-th character of the i-th element of maze is 'X' if the square is an impassable bush; otherwise, it is a '.'. Mike wants his friend, Jumping Jim, to solve the maze. Jim will start in row startRow in column startCol.
Unlike typical maze solvers, Jim has the ability to jump through the maze, rather than simply walking. Jim's possible moves are described in moveRow and moveCol. The i-th element corresponds to a move Jim can make in which his current row is changed by moveRow[i], and his current column is changed by moveCol[i]. For example, if moveRow = {1, 0, -1} and moveCol = {3, -2, 5}, Jim's legal moves are (1,3), (0, -2), and (-1, 5). However, Jim cannot move outside the boundary of the maze, and he cannot land on an impassable bush.
Mike wants to make the maze impossible for Jim to exit, and can place the exit in any cell containing a '.' in the maze. If this turns out to be impossible, then Mike wants to make Jim's trip take as long as possible. Jim is smart, and he will always exit the maze in the minimum number of jumps that he can. Return the maximum number of jumps that Jim will make to exit the maze; if it is impossible for him to exit the maze, return -1 instead.
Definition
    
Class:
MazeMaker
Method:
longestPath
Parameters:
vector <string>, int, int, vector <int>, vector <int>
Returns:
int
Method signature:
int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)
(be sure your method is public)
    
 
Constraints
-
maze will contain between 1 and 50 elements, inclusive.
-
Each element of maze will contain between 1 and 50 characters, inclusive.
-
Each element of maze will contain the same number of characters.
-
Each character of maze will be either 'X' or '.'.
-
maze will contain at least 2 '.' characters.
-
startRow will be between 0 and N-1, inclusive, where N is the number of elements in maze.
-
startCol will be between 0 and M-1, inclusive, where M is the number of characters in each element of maze.
-
maze[startRow][startCol] will be '.'.
-
moveRow will contain between 1 and 50 elements, inclusive.
-
moveCol will contain the same number of elements as moveRow.
-
Each element of moveRow and moveCol will be between -50 and 50, inclusive.
Examples
0)
 
    
{"...",
 "...",
 "..."}
0
1
{1,0,-1,0}
{0,1,0,-1}
Returns: 3
Here Jim can move up, down, left and right. Mike will set the exit in one of the bottom corners, which take Jim 3 steps to reach.
1)
 
    
{"...",
 "...",
 "..."}
0
1
{1, 0, -1, 0, 1, 1, -1, -1}
{0, 1, 0, -1, 1, -1, 1, -1}
Returns: 2
This is the same problem, but now Jim can move diagonally. With this, he can reach any section in at most two steps.
2)
 
    
{"X.X",
 "...",
 "XXX",
 "X.X"}
0
1
{1, 0, -1, 0}
{0, 1, 0, -1}
Returns: -1
Here Mike can place the exit in the empty section of the bottom row; Jim can never reach it.
3)
 
    
{".......",
 "X.X.X..",
 "XXX...X",
 "....X..",
 "X....X.",
 "......."}
5
0
{1, 0, -1, 0,-2, 1}
{0, -1, 0, 1, 3, 0}
Returns: 7
 
4)
 
    
{"......."}
0
0
{1, 0, 1, 0, 1, 0}
{0, 1, 0, 1, 0, 1}
Returns: 6
 
5)
 
    
{"..X.X.X.X.X.X."}
0
0
{2,0,-2,0}
{0,2,0,-2}
Returns: -1
Since Jim can only jump (and can't move to the side), Mike can place the exit anywhere except the start to prevent Jim from winning.
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.

2차원 maze 에서 한번에 이동할 수 있는 방향 벡터셋이 주어진다.. 'X' 로 되어있거나 maze 밖으로는 못간다.. '.' 으로 되어있는 곳 중에 가장 도달하는데 오래걸리는 위치 구하기..

전형적인 BFS 문제이다.. start 지점에서 BFS 로 그냥 flooding 시켰음.. ㅎㅎ;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <queue>
  7 using namespace std;
  8 //#define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 #define INF 999999999
 11
 12 typedef struct _p {
 13     int x, y;
 14 } POINT;
 15
 16 int check[100][100];
 17
 18 class MazeMaker {
 19 public:
 20
 21 int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol)
 22 {
 23     int n;
 24     int x, y;
 25     int row, col;
 26     int max1;
 27     int i, j;
 28     int cur, temp_x, temp_y;
 29     POINT p1, p2;
 30     queue<POINT> q;
 31
 32     row = maze.size();
 33     col = maze[0].size();
 34     for (i = 0; i <row; i++) {
 35         for (j = 0; j < col; j++) {
 36             check[i][j] = INF;
 37         }
 38     }
 39
 40     n = moveRow.size();
 41
 42     p1.x = startRow;
 43     p1.y = startCol;
 44     check[p1.x][p1.y] = 0;
 45     q.push(p1);
 46
 47     while (!q.empty()) {
 48         p1 = q.front();
 49         q.pop();
 50         x = p1.x;
 51         y = p1.y;
 52         cur = check[x][y];
 53
 54         for (i = 0; i < n; i++) {
 55             temp_x = x+moveRow[i];
 56             temp_y = y+moveCol[i];
 57             if (temp_x >= 0 && temp_x < row && temp_y >= 0 && temp_y < col) {
 58                 if (check[temp_x][temp_y] == INF && maze[temp_x][temp_y] == '.') {
 59                     check[temp_x][temp_y] = cur + 1;
 60                     p2.x = temp_x;
 61                     p2.y = temp_y;
 62                     q.push(p2);
 63                 }
 64             }
 65         }
 66     }
 67
 68     max1 = -1;
 69     for (i = 0; i < row; i++) {
 70         for (j = 0; j < col; j++) {
 71             if (maze[i][j] == 'X')
 72                 continue;
 73             max1 = max(max1, check[i][j]);
 74         }
 75     }
 76     if (max1 == INF)
 77         return -1;
 78
 79     return max1;
 80 }
 81
 82 };

Level2 - PlanarGraphShop

Problem Statement
     
In the Kocurkovo village there is a shop that sells simple planar graphs. (See Notes for a definition.)
The cost of any graph with X vertices and Y edges is (X^3 + Y^2) gold coins.
Monika has N gold coins, and she wants to spend all of them on simple planar graphs.
Write a method that gets the value N and computes the minimum number of simple planar graphs Monika has to buy in order to spend exactly N gold coins. She is allowed to buy multiple graphs of the same type.
Definition
    
Class:
PlanarGraphShop
Method:
bestCount
Parameters:
int
Returns:
int
Method signature:
int bestCount(int N)
(be sure your method is public)
    
 
Notes
-
A simple graph is an ordered pair (V,E) where V is a finite non-empty set of objects called vertices, and E is a finite set of edges. Each edge is a two-element subset of V. (You can find drawings of several graphs in Example #3.)
-
Note that a simple graph does not contain any loops (edges that connect a vertex to itself) and any duplicate edges. In other words, each edge connects two different vertices, and each pair of vertices is connected by at most one edge.
-
A graph is called planar if it has a drawing in the plane such that no two edges intersect.
-
Note that a simple planar graph does not have to be connected.
Constraints
-
N will be between 1 and 50,000, inclusive.
Examples
0)
 
    
36
Returns: 1
For 36 gold coins she can buy a triangle: a simple planar graph with 3 vertices and 3 edges.
1)
 
    
7
Returns: 7
The only simple planar graph that costs 7 gold coins or less is the graph that consists of a single vertex (and no edges). This graph costs 1^3 + 0^2 = 1, so Monika has to buy 7 of them.
2)
 
    
72
Returns: 2
She can buy 2 triangles for 36 gold coins each. No simple planar graph costs exactly 72 gold coins, hence the optimal answer in this case is 2.
3)
 
    
46
Returns: 3
All the graphs Monika can afford are shown in the following picture:
 

One optimal solution is to buy graphs worth 1 + 9 + 36 gold coins.
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.

어떤 planar graph (V, E) 의 value가 V^3 * E^2 이라고 하자.. 정확히 N 을 만들기 위해서 필요한 planar graph 의 최소 개수 구하기..

graph 이론과 DP 가 짬뽕된 좋은 문제..
이 문제는 planar graph 에서 edge 의 개수를 잘못 세는 바람에 챌 당했다.. 젠장
vertex 의 개수가 v (v >= 3) 일때, planar graph 가 되기 위해선 e <= 3 * v - 6 을 만족해야 한다.. -_-
흠.. 이 사실을 우리방에서 나 빼고 다 알고있었다.. -_-;; 뭥미

뭐 어쨋든.. 이런식으로 나올수 있는 planar graph 의 cost 를 다 구하고..
그 다음부터는 아주 고전적인 DP 문제인 동전교환 문제가 된다..

아.. 이문제땜에 또 잠이 안오는구만..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8 #define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10 #define INF 999999999
 11
 12
 13 class PlanarGraphShop {
 14 public:
 15
 16 int bestCount(int N)
 17 {
 18     int i, j, x;
 19     int a, b;
 20     int res;
 21     int dp[50001];
 22     vector<int> item;
 23
 24     item.push_back(1);
 25     item.push_back(8);
 26     item.push_back(8);
 27     item.push_back(9);
 28     for (i = 1; i <= N; i++) {
 29         a = (long long)i*i*i;
 30         if (a > N)
 31             break;
 32         for (j = 0; j <= 3*i-6; j++) {
 33             b = (long long)j*j;
 34             if (a+b > N)
 35                 break;
 36             item.push_back(a+b);
 37         }
 38     }
 39
 40     memset(dp, -1, sizeof(dp));
 41     dp[0] = 0;
 42     for (i = 1; i <= N; i++) {
 43         for (j = 0; j < item.size(); j++) {
 44             x = item[j];
 45             if (i < x)
 46                 continue;
 47             if (dp[i] == -1)
 48                 dp[i] = dp[(int)(i-x)]+1;
 49             else
 50                 dp[i] = min(dp[i], dp[i-x]+1);
 51         }
 52     }
 53     res = dp[N];
 54 printf("res = %d\n", res);
 55     return res;
 56 }
 57
 58 };

Level3 - TheAlmostLuckyNumbers

Problem Statement
     
A lucky number is a number whose decimal representation contains only the digits 4 and 7. An almost lucky number is a number that is divisible by a lucky number. For example, 14, 36 and 747 are almost lucky, but 2 and 17 are not. Note that a number can be both lucky and almost lucky at the same time (for example, 747).  You are given long longs a and b. Return the number of almost lucky numbers between a and b, inclusive.
Definition
    
Class:
TheAlmostLuckyNumbers
Method:
count
Parameters:
long long, long long
Returns:
long long
Method signature:
long long count(long long a, long long b)
(be sure your method is public)
    
 
Constraints
-
a will be between 1 and 10,000,000,000, inclusive.
-
b will be between a and 10,000,000,000, inclusive.
Examples
0)
 
    
1
10
Returns: 3
There are three almost lucky numbers less than or equal to ten - 4, 7 and 8.
1)
 
    
14
14
Returns: 1
14 is an almost lucky number.
2)
 
    
1
100
Returns: 39
 
3)
 
    
1234
4321
Returns: 1178
 
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.

4 또는 7 로 이루어진 수를 lucky number 라고 한다.. lucky number 로 나누어 떨어지는 수를 almost lucky number 라고 한다.. a 와 b 사이에 almost lucky number 가 몇개 있겠는가?

to be updated..