TopCoder SRM 392 Div2

저녁 9시에 열린 상금매치였다.. 이전 매치에서 삽질하는바람에 div2로 강등됐는데.. 바로 상금매치라니.. 오히려 나한텐 잘된일이었다..;; 이번 셋은 easy는 너무너무 쉽고.. med가 상당히 tricky했다.. 흠.. 그래도 med는 풀줄알았는데.. 끝내 submit을 못했다.. ㅠ_ㅠ;; 아.. 나의 코딩실력이 이거밖에 안되다니.. ㅠ_ㅠ med 문제의 경우 sample이 test case를 제대로 커버하지 못해서 챌린지의 향연이었다.. 결국 챌 덕분에 방 1등 차지.. 음.. 정말 쑥쓰럽군..;;

방 1등 전체 43등..

한문제풀고 1등이라니.. 완전 막장이군.. 빨리 실력을 쌓아야겠다..;; 그래도 다시 div1로 복귀.. 이거 당분간 div1과 div2를 왔다리갔다리 할것같다..



[250] AverageCandyLifetime

Problem Statement
     
On January 1, 2007, a confectioner made several candies.
On the last day of each month she allows her children to eat several of those candies.
The lifetime of a candy is the number of days between January 1 and the day the candy is eaten, inclusive. For example, the lifetime of a candy eaten on January 31 is 31, and the lifetime of a candy eaten on December 31 is 365 (note that 2007 wasn't a leap year).
You are given a vector <int> eatenCandies, the i-th element of which is the number of candies eaten on the last day of the i-th month of 2007 (January is month 0, February is month 1, etc.). Return the average lifetime of the candies.
Definition
   
Class:
AverageCandyLifetime
Method:
getAverage
Parameters:
vector <int>
Returns:
double
Method signature:
double getAverage(vector <int> eatenCandies)
(be sure your method is public)
   
 
Notes
-
The year 2007 was not a leap year.
-
The number of days in the months of 2007, in order, were 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 and 31.
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
eatenCandies will contain exactly 12 elements.
-
Each element of eatenCandies will be between 0 and 1000, inclusive.
-
The sum of all the elements in eatenCandies will be greater than 0.
Examples
0)
 
   
{1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 60.5
One candy was eaten on January 31 and the other was eaten on March 31. The lifetimes of the candies are 31 and 31+28+31=90. The average lifetime is (31+90)/2=60.5.
1)
 
   
{0, 1000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 59.0
All candies were eaten on February 28. The lifetime of each candy is 31+28=59, so the average candy lifetime is 59.0.
2)
 
   
{0, 0, 0, 0, 0, 1, 0, 0, 0, 50, 0, 0}
Returns: 301.5882352941176
Most of the candies were eaten on October 31 (Halloween), and the lifetime of each of those candies is 304. The average lifetime is smaller than 304, because of a candy with lifetime 181, eaten on June 30.
3)
 
   
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Returns: 252.80769230769232
 
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.

모든 캔디가 1월1일에 주어지고.. 매달 말일에 캔디를 먹는다.. 각 달마다 먹은 캔디의 개수가 주어질때 캔디의 평균 생명주기를 구하는 문제..

단순히.. 캔디가 먹히기전까지 기간의 합을 모든 캔디의 수로 나누면 된다..

음.. 코드는 별로 깔끔하지 못하군.. 이정도문제는 240점은 넘겨야하는데.. ㅠ_ㅠ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class AverageCandyLifetime {
  9 public:
 10
 11 double getAverage(vector <int> eatenCandies)
 12 {
 13     int sum[15];
 14     int a, b, i;
 15     sum[1] = 31;
 16     sum[2] = 31+28;
 17     sum[3] = sum[2]+31;
 18     sum[4] = sum[3]+30;
 19     sum[5] = sum[4]+31;
 20     sum[6] = sum[5]+30;
 21     sum[7] = sum[6]+31;
 22     sum[8] = sum[7]+31;
 23     sum[9] = sum[8]+30;
 24     sum[10] = sum[9]+31;
 25     sum[11] = sum[10]+30;
 26     sum[12] = sum[11]+31;
 27     a = b = 0;
 28     for (i = 0; i < eatenCandies.size(); i++) {
 29         a += eatenCandies[i] * sum[i+1];
 30         b += eatenCandies[i];
 31     }
 32     return (double)a / (double)b;
 33 }
 34
 35 };

[500] TwoStringMasks

Problem Statement
     
You are given two strings s1 and s2. Each string contains some letters and exactly one asterisk ('*').
You must replace each asterisk with a sequence of letters (possibly of zero length). The resulting two strings must be equal.
Return the shortest possible resulting string. If it is impossible to make the strings equal, return "impossible" (quotes for clarity) instead.
Definition
   
Class:
TwoStringMasks
Method:
shortestCommon
Parameters:
string, string
Returns:
string
Method signature:
string shortestCommon(string s1, string s2)
(be sure your method is public)
   
 
Constraints
-
s1 will contain between 1 and 50 characters, inclusive.
-
s2 will contain between 1 and 50 characters, inclusive.
-
s1 and s2 will contain only uppercase letters ('A'-'Z') and asterisks ('*').
-
s1 and s2 will contain exactly one asterisk each.
Examples
0)
 
   
"TOPC*DER"
"T*PCODER"
Returns: "TOPCODER"
Each of the asterisks should be replaced with an "O".
1)
 
     
"HELLO*"
"HI*"
Returns: "impossible"
No matter how you replace the asterisks, the second characters of the strings will differ. So it is impossible to make the strings equal.
2)
 
   
"GOOD*LUCK"
"*"
Returns: "GOODLUCK"
The first asterisk should be replaced with an empty string.
3)
 
   
"*SAMPLETEST"
"THIRDSAMPLE*"
Returns: "THIRDSAMPLETEST"
 
4)
 
   
"*TOP"
"*CODER"
Returns: "impossible"
 
5)
 
   
"*"
"A*"
Returns: "A"
 
6)
 
   
"*A"
"B*"
Returns: "BA"
 
7)
 
   
"LASTCASE*"
"*LASTCASE"
Returns: "LASTCASE"
 
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.

두개의 문자열이 주어지고 각각의 문자열은 중간에 하나의 '*' 이 있다.. 이 '*'은 임의의 문자열로 대치될 수 있을때 두 문자열을 같게 만드는 최소의 문자열 찾기.. 불가능하면 "impossible" return..

음.. 그냥 단순히 코딩하면 되는데.. 결국 실패.. ㅠ_ㅠ 막판에 sample 하나가 안나와서 수정하다가 결국 submit을 못했다..

문제풀다가 생각해 낸 tricky case는 {"ABC*ABC", "*BC"} 였는데.. 역시나.. submit한 6명중에 4명이나 fail했다.. ㅎㅎㅎ 나머지 두명도 system test때 다 fail하고.. 결국.. 얼떨결에 1등을 해버렸군..

아.. 쉽지않은 문제였다.. ㅠ_ㅠ;; 열라 삽질코딩끝에.. 겨우 pass..!!

우선 왼쪽 같은부분 제거.. 그다음 오른쪽 같은부분 제거..
이제 *을 사이에두고 남은 왼쪽과 오른쪽 string이 둘다 하나의 string에서 온것이라면 특별처리..
그게 아니라 하나는 첫번째 하나는 두번째 string에서 왔다면.. 겹치는부분을 제거하면서 붙인다..

휴.. 코딩이 완전 엉망이네.. ㅠ_ㅠ;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 void rev(char* x)
  9 {
 10     char temp[100];
 11     int i, j, len;
 12     len = strlen(x);
 13     for (i = 0, j = len-1; i < len; i++, j--) {
 14         temp[i] = x[j];
 15     }
 16     temp[i] = 0;
 17     strcpy(x, temp);
 18 }
 19
 20 void make_str(char* ss1, char* ss2, char* buf)
 21 {
 22     int i, j, k;
 23     int len1, len2;
 24     len1 = strlen(ss1);
 25     len2 = strlen(ss2);
 26     if (len1 == 0 && len2 == 0) {
 27         buf[0] =0;
 28         return ;
 29     }
 30     if (len1 == 0) {
 31         strcpy(buf, ss2);
 32         return ;
 33     }
 34     if (len2 == 0) {
 35         strcpy(buf, ss1);
 36         return ;
 37     }
 38
 39     for (i = 0; i < len1; i++) {
 40         if (i + len2 < len1)
 41             continue;
 42         for (k = 0; k < len2; k++) {
 43             if (k+i < len1 && ss1[k+i] != ss2[k])
 44                 break;
 45         }
 46         if (k == len2)
 47             break;
 48     }
 49     strcpy(buf, ss1);
 50     for (j = i, k = 0; k < len2; k++, j++) {
 51         buf[j] = ss2[k];
 52     }
 53     buf[j] = 0;
 54 }
 55
 56 class TwoStringMasks {
 57 public:
 58
 59 string shortestCommon(string s1, string s2)
 60 {
 61     char str1[100], str2[100];
 62     char temp1[100], temp2[100], buf[100];
 63     char f[100], e[100];
 64     int a1, a2, b1, b2;
 65     int len1, len2;
 66     int i, j, k;
 67     string xx, yy, zz, res;
 68     strcpy(str1, s1.c_str());
 69     strcpy(str2, s2.c_str());
 70     len1 = strlen(str1);
 71     len2 = strlen(str2);
 72     if (!strcmp(str1, "*") && !strcmp(str2, "*"))
 73         return "";
 74
 75     for (i = 0; i < len1 && i < len2; i++) {
 76         if (str1[i] == '*' || str2[i] == '*')
 77             break;
 78         f[i] = str1[i];
 79         if (str1[i] != str2[i])
 80             return "impossible";
 81     }
 82     f[i] = 0;
 83     a1 = i;
 84     b1 = i;
 85
 86     for (i = len1-1, j = len2-1, k = 0; i >= 0 && j >= 0; i--, j--, k++) {
 87         if (str1[i] == '*' || str2[j] == '*')
 88             break;
 89         e[k] = str1[i];
 90         if (str1[i] != str2[j])
 91             return "impossible";
 92     }
 93     e[k] = 0;
 94     rev(e);
 95     a2 = i;
 96     b2 = j;
 97
 98     if (str2[b1] == '*') {
 99         if (str1[a2] == '*') {
100             for (i = a1, j = 0; i < len1; i++, j++) {
101                 if (str1[i] == '*') {
102                     temp1[j] = 0;
103                     break;
104                 }
105                 temp1[j] = str1[i];
106             }
107             for (i = 0; i < len2; i++) {
108                 if (str2[i] == '*')
109                     break;
110             }
111             i++;
112             for (j = 0; i <= b2; i++, j++) {
113                 temp2[j] = str2[i];
114             }
115             temp2[j] = 0;
116             make_str(temp1, temp2, buf);
117 printf("temp1 = %s, temp2 = %s, buf = %s\n", temp1, temp2, buf);
118         }
119         else {
120             for (i = 0, j = 0; i < len1; i++) {
121                 if (str1[i] == '*')
122                     continue;
123                 buf[j++] = str1[i];
124             }
125             buf[j] = 0;
126             res = buf;
127             return res;
128         }
129     }
130     else if (str1[a1] == '*') {
131         if (str2[b2] == '*') {
132             for (i = b1, j = 0; i < len2; i++, j++) {
133                 if (str2[i] == '*') {
134                     temp1[j] = 0;
135                     break;
136                 }
137                 temp1[j] = str2[i];
138             }
139             for (i = 0; i < len1; i++) {
140                 if (str1[i] == '*')
141                     break;
142             }
143             i++;
144             for (j = 0; i <= a2 ; i++, j++) {
145                 temp2[j] = str1[i];
146             }
147             temp2[j] = 0;
148             make_str(temp1, temp2, buf);
149 printf("temp1 = %s, temp2 = %s, buf = %s\n", temp1, temp2, buf);
150         }
151         else {
152             for (i = 0, j = 0; i < len2; i++) {
153                 if (str2[i] == '*')
154                     continue;
155                 buf[j++] = str2[i];
156             }
157             buf[j] = 0;
158             res = buf;
159             return res;
160         }
161     }
162 printf("f = %s, buf = %s\n", f, buf);
163     xx = f;
164     yy = buf;
165     zz = e;
166     res = xx+yy+zz;
167 printf("res ------------> %s\n", res.c_str());
168     return res;
169 }
170
171 };

[1000] QuasiLatinSquares

Problem Statement
     
You are given two positive integers, n and d.
Create a square table of size n×n containing only integers between 0 and d-1, inclusive, such that each row and each column contains each number between 0 and d-1, inclusive, at least once.
Return this table as a vector <string> containing exactly n elements. Each element represents a single row of the table and contains a single space delimited list of the numbers in that row from left to right. The numbers must have no extra leading zeroes.
If there are multiple possible answers, return the one with the lexicographically smallest first element. If there is still a tie, return the one with the lexicographically smallest second element, etc.
Definition
   
Class:
QuasiLatinSquares
Method:
makeSquare
Parameters:
int, int
Returns:
vector <string>
Method signature:
vector <string> makeSquare(int n, int d)
(be sure your method is public)
   
 
Notes
-
A string S is greater than a string T lexicographically if T is a proper prefix of S, or if S has a greater character at the first position where the strings differ. A space character (' ') is considered smaller than any digit character ('0'-'9').
-
It is guaranteed that there exists an answer for each valid input.
Constraints
-
n will be between 1 and 10, inclusive.
-
d will be between 1 and n, inclusive.
Examples
0)
 
   
3
3
Returns: {"0 1 2", "1 2 0", "2 0 1" }
If d equals n the desired table is called a Latin square. This is the lexicographically smallest Latin square of size 3.
1)
 
   
5
2
Returns: {"0 0 0 0 1", "0 0 0 0 1", "0 0 0 0 1", "0 0 0 0 1", "1 1 1 1 0" }
 
2)
 
   
5
4
Returns: {"0 0 1 2 3", "0 0 1 2 3", "1 1 0 3 2", "2 2 3 0 1", "3 3 2 1 0" }
 
3)
 
   
9
7
Returns:
{"0 0 0 1 2 3 4 5 6",
 "0 0 0 1 2 3 4 5 6",
 "0 0 0 1 2 3 4 5 6",
 "1 1 1 0 3 2 5 6 4",
 "2 2 2 3 0 1 6 4 5",
 "3 3 3 4 5 6 0 1 2",
 "4 4 4 2 6 5 1 0 3",
 "5 5 5 6 1 4 2 3 0",
 "6 6 6 5 4 0 3 2 1" }
 
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.

to be updated..