TopCoder SRM 385 Div2 (완료)

새벽 1시에 있었던 매치.. 결과는 조금 아쉬웠다.. 1000번은 뭔가 떠올라서 계속 시도했는데 결국 솔루션이틀렸고 안드로를 가고 말았다..

방 5등 전체 154등

[250] RussianSpeedLimits

Problem Statement
     
Rumor has it that Russians don't obey speed limits. That may be because the speed limits are sometimes specified implicitly in Russia.
More specifically, every road in a city has a default speed limit of 60 kilometers per hour, and usually doesn't have any road signs to remind drivers of that. Analogously, every road outside the city has a default speed limit of 90 kilometers per hour.
The speed limit can still be specified with road signs, like '30' or '95'. There is also a special road sign, 'start of default speed limit zone', that tells you that the default speed limit is now in place. The signs are sometimes also used to remind drivers of the current speed limit, so you can meet several same signs in a row.
To summarize, one should pay attention to the following road signs to monitor the speed limit changes:
Speed limit X - marks the start of a zone with speed limit X kilometers per hour.
Start of default speed limit zone - marks the start of a zone with the default speed limit, either 60 if inside a city or 90 if outside.
City boundary - means the default speed limit changes from 60 to 90 or vice versa. If you are inside a special speed limit zone, this zone also ends, so the speed limit always becomes equal to the new default.
Given the list of road signs you met on your way as a vector <string> signs (in the order you met them), return the current speed limit. Each element of signs will be either a positive integer number X without leading zeros, denoting the sign 'Speed limit X', a string "default" denoting the sign 'start of default speed limit zone', or a string "city", denoting the sign 'city boundary' (quotes for clarity only). You start your journey inside a city, and outside any special speed limit zone.
Definition
   
Class:
RussianSpeedLimits
Method:
getCurrentLimit
Parameters:
vector <string>
Returns:
int
Method signature:
int getCurrentLimit(vector <string> signs)
(be sure your method is public)
   
 
Constraints
-
signs will contain between 1 and 50 elements, inclusive.
-
Each element of signs will be "default", "city" or a positive integer without leading zeros, between 1 and 100, inclusive (quotes for clarity only).
Examples
0)
 
   
{"80"}
Returns: 80
On highways, speed limits may be above the default value.
1)
 
   
{"40", "70", "default", "20", "50"}
Returns: 50
The limits are specified in the order you meet them, so you're interested in the last one.
2)
 
   
{"40", "70", "default"}
Returns: 60
The default limit is still 60.
3)
 
   
{"40", "80", "city"}
Returns: 90
The first "city" means we've left the city, thus the 90 limit.
4)
 
   
{"city", "60"}
Returns: 60
Speed limits can be overridden outside the city too.
5)
 
   
{"city", "50", "default"}
Returns: 90
The default value changes when outside the city.
6)
 
   
{"city", "city", "city", "city"}
Returns: 60
You've crossed four city boundaries. The first time, you left a city. Then, you entered a city. Then, you left that city. Finally, you entered another city.
7)
 
   
{"20", "city", "city", "50", "60"}
Returns: 60
The default speed limit may be specified with a usual sign.
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.

제한속도가 city안에는 60 밖은 90 특별지역은 임의의 숫자로 표기.. 인풋이 순서대로 들어올때 마지막의 제한속도를 구하는문제..

문제가 너무 쉬워서 문제해석을 잘못했나.. 하고 한참 들여다본 문제..
마지막이 숫자이면 그게 답이고.. 나머지는 city가 몇번나왔는지 세서 그 parity를 체크하면 된다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class RussianSpeedLimits {
  9 public:
 10
 11 int getCurrentLimit(vector <string> signs)
 12 {
 13     int i, k, fl;
 14     char buf[100];
 15     int size = signs.size();
 16     fl = 0;
 17     for (i = 0; i < size; i++) {
 18         strcpy(buf, signs[i].c_str());
 19         if (*buf == 'c') {
 20             fl = (fl + 1) % 2;
 21             if (fl == 1)
 22                 k = 90;
 23             else
 24                 k = 60;
 25         }
 26         else if (*buf == 'd') {
 27             if (fl == 1)
 28                 k = 90;
 29             else
 30                 k = 60;
 31         }
 32         else {
 33             k = atoi(buf);
 34         }
 35     }
 36     return k;
 37 }
 38
 39 };

[500] UnderscoreJustification

Problem Statement
     
Most word processors available today allow several standard ways to format lines in a paragraph. One of those ways is to 'justify' each line to a given width. The precise definition for that operation is as follows:
Assume that a line of text consists of several words separated by spaces (for simplicity, there will be no punctuation). Define a gap as the sequence of spaces between a pair of adjacent words. When reformatting a line, each gap can be replaced with a gap of a different non-zero length. The line is said to be justified to width w if it is exactly w characters long, has no leading or trailing spaces, and all gaps are as evenly distributed as possible. This means that the gaps should all be of equal length, or, if that is not possible, the difference in length between the longest and smallest gaps must be 1.
To better illustrate the results of the justification operation, we will use underscores ('_') in place of spaces.
Obviously, the above rules don't uniquely define the result of a justification. If there are multiple ways to justify a line of text, the one that comes earliest lexicographically is used. Note that an underscore comes after uppercase letters but before lowercase letters in the ASCII ordering.
You are given a vector <string> words containing all the words in a line of text. The words are given in the order that they appear in the line. Return the line of text justified to the given width, using underscores as spaces.
Definition
   
Class:
UnderscoreJustification
Method:
justifyLine
Parameters:
vector <string>, int
Returns:
string
Method signature:
string justifyLine(vector <string> words, int width)
(be sure your method is public)
   
 
Notes
-
Note that you must make all the gaps have equal length if possible. Only if that is impossible, the longest gap will be one longer than the shortest.
-
Remember that 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z'.
-
A string is lexicographically smaller than another string if it contains a smaller character in the first position where they differ.
Constraints
-
words will contain between 2 and 10 elements, inclusive.
-
Each element of words will contain between 1 and 10 characters, inclusive.
-
Each element of words will contain only letters ('A'-'Z', 'a'-'z').
-
width will be between 3 and 200, inclusive.
-
width will be greater than or equal to len+n-1, where n is the number of elements in words, and len is the total number of characters in words, to allow at least one space between adjacent words.
Examples
0)
 
   
{"A", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"}
50
Returns: "A___quick__brown__fox__jumps__over__the__lazy__dog"
We have 7 groups of 2 underscores and 1 group of 3 underscores to put between our words. If the first gap contains 2 underscores, then the string would start with "A__q", which is lexicographically larger than "A___", so it's advantageous to put 3 underscores in the first gap.
1)
 
   
{"Alpha", "Beta", "Gamma", "Delta", "Epsilon"}
32
Returns: "Alpha_Beta_Gamma__Delta__Epsilon"
There are six possible variants: Alpha_Beta_Gamma__Delta__Epsilon Alpha_Beta__Gamma_Delta__Epsilon Alpha_Beta__Gamma__Delta_Epsilon Alpha__Beta_Gamma_Delta__Epsilon Alpha__Beta_Gamma__Delta_Epsilon Alpha__Beta__Gamma_Delta_Epsilon The former is the lexicographically smallest one.
2)
 
   
{"Hello", "world", "John", "said"}
29
Returns: "Hello____world___John____said"
Sometimes it's better to mix large and small groups of underscores.
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.

문장이 주어지고 문장을 width 칸에 딱 맞게 배치하도록 underscore를 단어 사이에 삽입하기.. 단 삽입되는 underscore는 각각 길이가 최대 1 차이나야하고.. 답이 여러개일 경우 lexy-smallest 로 삽입하기..
단, ascii 순서는 대문자 < underscore < 소문자 순이다..

우선 단어 사이에 삽이되는 underscore개수를 구하고.. 경우에따라 1개 더 추가해야하는게 몇개인지 구한다.. 그 다음부터는 greedy하게 삽입하면 된다.. 뒤에 단어가 소문자이면 삽이.. 대문자이면 건너뛰고.. 그래도 남으면.. 뒤에서부터 안채운거를 채운다.. (맞나?)
나같은경우 복잡한거 생각하는거 매우 싫어하므로.. 그냥 next_permutation으로 모든 가능한 경우를 다 구했다..
그중에 젤 앞서는 문자열 선택..

이문제는 특히 기억에 남는게.. 디버깅도 안하고 한번에 짠게 pass 했다.. 그런 경우가 거의 없었는데.. -_-
fail이 많을줄알았는데.. submit한사람은 거의 pass했다.. 흠.. 덕분에 내 등수만 하락.. ㅠ_ㅠ
그러고보니.. 35~40 줄은 필요가없는 코드이군.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 using namespace std;
  8
  9 char word[20][20];
 10
 11 void get_underscore(int u, char* str)
 12 {
 13     int i;
 14     for (i = 0; i < u; i++)
 15         str[i] = '_';
 16     str[i] = 0;
 17 }
 18
 19 class UnderscoreJustification {
 20 public:
 21
 22 string justifyLine(vector <string> words, int width)
 23 {
 24     int n, sum;
 25     int i, k, left;
 26     int cnt[20];
 27     char buf[10000], str[100];
 28     set<string> s;
 29     n = words.size();
 30     sum =0;
 31     for (i = 0; i < n; i++) {
 32         strcpy(word[i], words[i].c_str());
 33         sum += strlen(word[i]);
 34     }
 35     if (((width-sum) % (n-1)) == 0) {
 36         k = (width-sum) / (n-1);
 37         for (i = 0; i < n-1; i++) {
 38             cnt[i] = k;
 39         }
 40     }
 41     else {
 42         k = (width-sum) / (n-1);
 43         left = (width-sum) % (n-1);
 44         for (i = 0; i < n-1; i++) {
 45             if (left) {
 46                 cnt[i] = k + 1;
 47                 left--;
 48             }
 49             else {
 50                 cnt[i] = k;
 51             }
 52         }
 53     }
 54     sort(cnt, cnt+n-1);
 55     do {
 56         strcpy(buf, word[0]);
 57         for (i = 0; i < n-1; i++) {
 58             get_underscore(cnt[i], str);
 59             strcat(buf, str);
 60             strcat(buf, word[i+1]);
 61         }
 62         s.insert(buf);
 63     } while (next_permutation(cnt, cnt+n-1));
 64
 65     set<string>::iterator it;
 66     it = s.begin();
 67     cout << "buf = " << *it << endl;
 68     return *it;
 69 }
 70
 71 };

[1000] SummingArithmeticProgressions

Problem Statement
     
A magic arithmetic progression with k elements is a sequence of the form x, x+d, x+2*d, ..., x+(k-1)*d for some positive integers x and d. How many integers between left and right, inclusive, can be represented as the sum of some magic arithmetic progression with exactly k elements?
Definition
   
Class:
SummingArithmeticProgressions
Method:
howMany
Parameters:
int, int, int
Returns:
int
Method signature:
int howMany(int left, int right, int k)
(be sure your method is public)
   
 
Constraints
-
left will be between 1 and 1000000000, inclusive.
-
right will be between left and 1000000000, inclusive.
-
k will be between 2 and 5, inclusive.
Examples
0)
 
     
1
12
3
Returns: 3
The representable numbers are: 6=1+2+3, 9=2+3+4=1+3+5, 12=3+4+5=2+4+6=1+4+7. Note that there can be several possible representations for a number.
1)
 
   
1
10
2
Returns: 8
Every number except 1 and 2 is representable: 3=1+2, 4=1+3, 5=1+4, etc.
2)
 
   
20
30
4
Returns: 6
The representable numbers are 20, 22, 24, 26, 28 and 30.
3)
 
   
1
9
4
Returns: 0
The minimal possible sum is 1+2+3+4=10.
4)
 
   
1
13
4
Returns: 1
And the next possible sum is 2+3+4+5=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.

k개의 항으로 이루어진 등차수열의 합이 left와 right 사이에 몇개들어가는지..

ACM-ICPC 준비할때도 그랬지만.. 나는 이런 류의 문제에 가장 취약한것같다.. 그냥 침착하게 하나부터 쭉 구해나가면서 규칙을 찾아야하는데 급하게 한번에 나오는 식을 찾으려고하다가 매번 삽질하는것 같다..

이 문제의 경우 k가 2~5 사이 이므로.. 각각에 대해서 규칙을 찾아보면 쉽다..

k = 2 일때: 3, 4, 5, 6, 7, ...
k = 3 일때: 6, 9, 12, 15, ...
k = 4 일때: 10, 14, 16, 18, 20, ...
k = 5 일때: 15, 20, 25, 30, ...

해당하는 k 에 대해서 몇개의 만족하는 수를 나열하면 쉽게 규칙을 찾아낼 수 있다..
그리고.. 조만간에 모듈러 합동에대한 것도 공부해봐야겠다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int f(int limit, int k)
  9 {
 10     if (k == 2) {
 11         if (limit <= 2)
 12             return 0;
 13         return limit-2;
 14     }
 15     else if (k == 3) {
 16         if (limit <= 5)
 17             return 0;
 18         return (limit / 3) - 1;
 19     }
 20     else if (k == 4) {
 21         if (limit <= 9)
 22             return 0;
 23         if (limit >= 10 && limit <= 13)
 24             return 1;
 25         return (limit-10) / 2;
 26     }
 27     if (limit <= 14)
 28         return 0;
 29     return (limit-10) / 5;
 30 }
 31
 32 class SummingArithmeticProgressions {
 33 public:
 34
 35 int howMany(int left, int right, int k)
 36 {
 37     int a, b;
 38     a = f(left-1, k);
 39     b = f(right, k);
 40     printf("a = %d, b = %d\n", a, b);
 41     return b-a;
 42 }
 43
 44 };