TopCoder SRM375 DIV2 (Complete)

The problem set was good.. and fairly easy but with my poor skills.. I lost many points.. ㅠ_ㅠ I always feel lost after each SRM.. It was 2:00 AM and I was trying to concentrate on it.. but it was hard.. and I made many mistakes during the coding phase consequently I counldn't solve 950 problem..

10th place in my room and 204th in div2

Even 204th place is the highest record in my recent matches.. Oh my..;;

Only a few points up and failed to get my green back..



[250] MixtureDensity

Problem Statement
     
A pharmacist is making a mixture of several ingredients. She needs to know the density of the resulting mixture. Density is defined as the mass of the mixture divided by its volume.
You're given a vector <string> ingredients, each element of which describes a single ingredient and is formatted "<Volume> ml of <Name>, weighing <Mass> g" (quotes for clarity). <Volume> and <Mass> are integers representing the volume in milliliters and mass in grams, respectively. <Name> is the name of the ingredient.
Return the density of the resulting mixture in grams per milliliters.
Definition
     
Class:
MixtureDensity
Method:
getDensity
Parameters:
vector <string>
Returns:
double
Method signature:
double getDensity(vector <string> ingredients)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
ingredients will contain between 1 and 50 elements, inclusive.
-
Each element of ingredients will contain between 23 and 50 characters, inclusive.
-
Each element of ingredients will be formatted as described in the statement.
-
Each <Volume> in ingredients will be an integer between 1 and 1000, inclusive, with no leading zeroes.
-
Each <Mass> in ingredients will be an integer between 1 and 1000, inclusive, with no leading zeroes.
-
Each <Name> in ingredients will contain only lowercase letters ('a'-'z') and spaces (' ').
-
Each <Name> in ingredients will begin and end with a lowercase letter.
Examples
0)
 
     
{"200 ml of oil, weighing 180 g"}
Returns: 0.9
The density is mass/volume = 180g/200ml = 0.9g/ml, the answer is 0.9.
1)
 
     
{"100 ml of dichloromethane, weighing 130 g", "100 ml of sea water, weighing 103 g"}
Returns: 1.165
The volume of the resulting mixture is 200 ml and the mass is 233 g. Therefore, the density is 233g/200ml = 1.165g/ml.
2)
 
   
{"1000 ml of water, weighing 1000 g", "500 ml of orange juice concentrate, weighing 566 g"}
Returns: 1.044
 
3)
 
   
{"1000 ml of something   l i g h t, weighing 1 g"}
Returns: 0.0010
 
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.

string이 여러개 들어오고 mass와 volume을 각각 파싱해서 총 밀도를 구하는 문제..

Simply an easy parsing problem.. but I did a crazy thing during the match..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class MixtureDensity {
      9 public:
     10
     11 double getDensity (vector<string> ingredients)
     12 {
     13     int size;
     14     int g, m;
     15     int a, b, i, j;
     16     char buf[1000], temp[1000];
     17     g = m = 0;
     18     size = ingredients.size();
     19     for (i = 0; i < size; i++) {
     20         strcpy(buf, ingredients[i].c_str());
     21         a = atoi(buf);
     22         for (j = 0; j < strlen(buf); j++) {
     23             if (buf[j] == ',')
     24                 break;
     25         }
     26         sscanf(&buf[j+1], "%s%d%s", temp, &b, temp);
     27         m += a;
     28         g += b;
     29 //printf("m = %d ,  g= %d\n", m, g);
     30     }
     31     return (double)g / (double)m;
     32 }
     33
     34 };

[550] DukeOnChessBoard

Problem Statement
     
Let's define a duke as a chess figure that is only allowed to move 1 cell up, down, left or right.
A duke is placed on an n×n board in the cell initPosition. In this problem, columns are marked 'a', 'b', etc. from left to right, and rows are marked '1', '2', etc. from bottom to top. Cells are notated as "cr" (quotes for clarity), where c is the column and r is the row.
Let's describe a duke's path as a dash-separated list of cells visited by the duke. For example, "c5-b5-b4" is a path consisting of two moves. The first move is one cell to the left (from c5 to b5), and the second is one cell down (from b5 to b4).
A path is called simple if it contains no repeated cells.
Return the lexicographically greatest simple path of a duke starting in initPosition. If the length of the path exceeds 40 characters, return only the first 20 and the last 20 characters, separated by three dots. (See Example #1).
Definition
   
Class:
DukeOnChessBoard
Method:
dukePath
Parameters:
int, string
Returns:
string
Method signature:
string dukePath(int n, string initPosition)
(be sure your method is public)
   
 
Notes
-
A string A is greater than a string B lexicographically if B is a proper prefix of A, or if A has a greater character at the first position where the strings differ.
Constraints
-
n will be between 2 and 8, inclusive.
-
initPosition will contain exactly 2 characters.
-
The first character of initPosition will be a lowercase letter between 'a' and 'h', inclusive.
-
The second character of initPosition will be a digit between '1' and '8', inclusive.
-
initPosition will denote a cell inside the n×n board.
Examples
0)
 
   
3
"b2"
Returns: "b2-c2-c3-b3-a3-a2-a1-b1-c1"
After the first move to the right, the duke will traverse the perimeter of the board in the counterclockwise direction.
1)
 
   
4
"d4"
Returns: "d4-d3-d2-d1-c1-c2-c3...b3-b2-b1-a1-a2-a3-a4"
The duke will move down three times, then left, then up three times and left, in a snake-like fashion. The lexicographically greatest path is 47 characters long, so its middle part is replaced by "...".
2)
 
   
3
"a2"
Returns: "a2-b2-c2-c3-b3-a3"

 
3)
 
   
4
"d3"
Returns: "d3-d4-c4-c3-c2-d2-d1...b2-b3-b4-a4-a3-a2-a1"
 

4)
 
   
8
"a8"
Returns: "a8-b8-c8-d8-e8-f8-g8...a1-a2-a3-a4-a5-a6-a7"
 
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.

n by n 보드가 있고 시작 점이 주어질때 갈수있는 path중에 lexy-greatest를 구하는 문제.. 단 한번 밟은 지점은 다시 갈 수 없다.. 행은 1 2 3.. 열은 a b c 로 표시됨..

I found the pattern and solved it with DFS.. It's pretty much easy..

1) go to the right if possible..
2) if 1) is not possible, then go up
3) if 1) and 2) are not possible, then go down
4) if 1) and 2) and 3) are not possible, then go left
5) if all above are not possible, we got the answer..

Btw, converting string to char* (vice versa) always bothering me.. I don't know C++ ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 char check[128][128];
      9 char path[10000][2];
     10 char str[10000];
     11 int N;
     12
     13 void dfs(int u, int v, int cnt)
     14 {
     15     int i, j;
     16     check[u][v] = 1;
     17     path[cnt][0] = u;
     18     path[cnt][1] = v;
     19 //printf("(%c, %c), cnt = %d \n", u, v, cnt);
     20     if (u+1 < 'a'+N && check[u+1][v] == 0) {
     21         dfs(u+1, v, cnt+1);
     22     }
     23     else if (v+1 <= N+'0' && check[u][v+1] == 0) {
     24         dfs(u, v+1, cnt+1);
     25     }
     26     else if (v-1 > '0' && check[u][v-1] == 0) {
     27         dfs(u, v-1, cnt+1);
     28     }
     29     else if (u-1 >= 'a' && check[u-1][v] == 0) {
     30         dfs(u-1, v, cnt+1);
     31     }
     32     else {
     33     j = 0;
     34     for (i = 0; i <= cnt; i++) {
     35         str[j++] = path[i][0];
     36         str[j++] = path[i][1];
     37         if (i < cnt) {
     38             str[j++] = '-';
     39         }
     40     }
     41     str[j] = 0;
     42     }
     43 }
     44
     45 class DukeOnChessBoard {
     46 public:
     47
     48 string dukePath(int n, string initPosition)
     49 {
     50     int i, j, k;
     51     int x, y, len;
     52     char buf[1000];
     53     string ret;
     54     N = n;
     55     memset(check, 0, sizeof(check));
     56     strcpy(buf, initPosition.c_str());
     57     x = *buf;
     58     y = buf[1];
     59     dfs(x, y, 0);
     60     len = strlen(str);
     61     if (len <= 40) {
     62         ret = str;
     63         return ret;
     64     }
     65     for (i = j = 0; i < 20; i++, j++) {
     66         buf[i] = str[j];
     67     }
     68     buf[i++] = '.';
     69     buf[i++] = '.';
     70     buf[i++] = '.';
     71     j = len-20;
     72     for (k = 0; k < 20; k++, j++) {
     73         buf[i++] = str[j];
     74     }
     75     buf[i] = 0;
     76     ret = buf;
     77     return ret;
     78 }
     79
     80 };

[950] DivisibleByDigits

Problem Statement
     
Given an integer n, find the smallest integer that starts with n and is divisible by every non-zero digit of n (all in decimal notation).
Definition
   
Class:
DivisibleByDigits
Method:
getContinuation
Parameters:
int
Returns:
long
Method signature:
long getContinuation(int n)
(be sure your method is public)
   
 
Notes
-
An integer A starts with an integer B if the string representation of B is a prefix of the string representation of A (both in decimal notation with no leading zeroes).
Constraints
-
n will be between 1 and 1000000000, inclusive.
Examples
0)
 
   
13
Returns: 132
We need a number that starts with 13 and is divisible by 1 (always true) and by 3. The smallest one is 132.
1)
 
   
648
Returns: 648
If n is divisible by all its non-zero digits, the answer to the problem is n itself.
2)
 
   
566
Returns: 56610
The resulting number must be divisible by 5, so it should end either with 0 or with 5. But a number ending with 5 is odd and can't be divisible by 6. So the last digit of the answer must be 0. In order to make the number divisible by 6, we need to put something before this 0, and the smallest appropriate digit is 1.
3)
 
   
1000000000
Returns: 1000000000
 
4)
 
   
987654321
Returns: 987654321360
 
5)
 
   
83
Returns: 8304
 
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.

주어진 수자로 시작하면서 처음 주어진 수의 모든 digit으로 나눠질수 있는 최소의 수 구하기..

This is a kind of easy problem.. I knew the solution but I was struggling with previous 2 problems and I didn't get enough time.. Within 10 minutes I give it a shot.. but I couldn't find my bug (which was "lld" which should be "%lld" -_-) and couldn't submit.. My condition is almost zero.. ㅠ_ㅠ

This kind of problem is well known and can be solved by BFS.. UVa-10993 is a similar problem..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 #include <queue>
      7 #include <set>
      8 using namespace std;
      9
     10 long long gcd(long long a, long long b)
     11 {
     12     if (b == 0)
     13         return a;
     14     return gcd(b, a % b);
     15 }
     16
     17 long long lcm(long long a, long long b)
     18 {
     19     return (a*b / gcd(a, b));
     20 }
     21
     22
     23 class DivisibleByDigits {
     24 public:
     25
     26 long long getContinuation(int n)
     27 {
     28     char buf[100];
     29     int i, len;
     30     long long l, c, p;
     31     sprintf(buf, "%d", n);
     32     l = 1;
     33     for (i = 0; i < strlen(buf); i++) {
     34         if (buf[i]-'0' == 0)
     35             continue;
     36         l = lcm(l, buf[i]-'0');
     37     }
     38     set<long long> s;
     39     s.insert(n % l);
     40
     41     queue<long long> q;
     42     q.push(n);
     43     while (!q.empty()) {
     44         c = q.front();
     45         q.pop();
     46 printf("c = %lld...\n", c);
     47         if (c % l == 0) {
     48             return c;
     49         }
     50         sprintf(buf, "%lld", c);
     51         len = strlen(buf);
     52         for (i = 0; i < 10; i++) {
     53             buf[len] = i+'0';
     54             buf[len+1] = 0;
     55             sscanf(buf, "%lld", &p);
     56             if (p % l == 0)
     57                 return p;
     58             if (s.find(p%l) == s.end()) {
     59                 q.push(p);
     60                 s.insert(p%l);
     61             }
     62         }
     63     }
     64     return c;
     65 }
     66
     67 };

Or I think we can just put digits (starting at 1) after the original number in bruteforce manner.. Worst case we only have to put 4 digits.. The reason is explained here.. (the LCM of 1 through 9 is 2520 and pigeonhole principle can be applied..) But I don't get it.. ;;; What is Pigeonhole Principle ?!