두달 반만에 참가한 매치..~
너무 오랜만에 참가한데다가.. 옐로우를 지켜야한다는 부담감 백배였는데..
리서밋으로 망했다가 챌 하나로 겨우 살아났다..~
Level1 - Starport
Problem Statement
A new starport has just started working. Starting from some moment of time (call it minute 0), a new spaceship arrives at the starport every M minutes. In other words, spaceships arrive at the starport at minutes 0, M, 2*M, 3*M and so on. Similarly, starting from minute 0 and repeating each N minutes, all arrived spaceships that are still placed at the port are teleported to the shed. If a spaceship arrives at the exact same minute when such a teleportation happens, it will be teleported immediately. Otherwise it will need to wait until the next teleportation happens. Let the waiting time of a spaceship be the time between its arrival and its teleportation to the shed. Return the average waiting time of a spaceship in minutes. See notes for an exact definition.
Definition
Class:
Starport
Method:
getExpectedTime
Parameters:
int, int
Returns:
double
Method signature:
double getExpectedTime(int N, int M)
(be sure your method is public)
Notes
-
Let W(i) be the waiting time for the spaceship that arrives at minute M * i. The average waiting time can be defined as the limit of (W(0) + W(1) + ... + W(P - 1)) / P when P tends to positive infinity. This limit will always exist.
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
N and M will each be between 1 and 1,000,000,000, inclusive.
Examples
0)
4
2
Returns: 1.0
Spaceships arrive at the starport at minutes 0, 2, 4, 6, 8, and so on. Teleportations are done at minutes 0, 4, 8, and so on. The waiting times for the spaceships are, correspondingly, 0, 2, 0, 2, 0, and so on, so the expected waiting time is 1.
1)
5
3
Returns: 2.0
2)
6
1
Returns: 2.5
3)
12345
2345
Returns: 6170.0
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.
teleport 는 0, N, 2*N, 3*N, ... 순으로 들어오고 startport 는 0, M, 2*M, 3*M, ... 순으로 들어온다..
startport 가 들어와서 다시 teleport 를 타기위해 평균 얼마나 기다려야 할까..?
이 문제는 규칙을 찾아보면.. LCM(N, M) 을 주기로 같은 값이 반복되는 걸 알 수 있다..
그래서 두 수의 LCM 구하고 simulation 해서 답 나오길래 submit~
그런데 좀 미심쩍어서 N = 1000000000, M = 1 을 넣어보니 TLE !!!
잘 고민해보니 lcm 개수만큼 loop 를 돌 필요 없고 등차수열의 합공식을 이용하여 한방에 구할 수 있다..
다행이 내가 처음 생각했던 방법 비스무리하게 시도한 사람이 몇 있어서.. 챌 먹이감이 되었다..
다들 챌이 너무 빨라서 1개밖에 성공 못했다..
다른 사람들 코드를 보니.. 다들 너무 짧아서 황당..
식을 정리해보면 결국 나랑 같은 식이기는 한데.. 뭔가 접근방법이 다른듯..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 long long gcd(long long a, long long b)
13 {
14 if (b == 0)
15 return a;
16 return gcd(b, a % b);
17 }
18
19
20 class Starport {
21 public:
22
23 double getExpectedTime(int N, int M)
24 {
25 long long L;
26 long long G;
27 long long cnt;
28 long long dif, n;
29 double sum;
30 G = gcd(N, M);
31 L = (long long)N * (long long)M / G;
32 cnt = L / M;
33 sum = 0.0;
34 dif = N / cnt;
35 n = cnt;
36 sum = (double)(n * (n-1) * dif / 2LL);
37 sum /= (double)cnt;
38 /*
39 for (i = 0; i < cnt; i++) {
40 a = i * M;
41 b = a % N;
42 if (b == 0)
43 c = a;
44 else
45 c = a + (N - b);
46 sum = sum + (double)(c - a);
47 }
48 sum /= (double)cnt;
49 */
50 printf("sum = %lf\n", sum);
51 return sum;
52 }
53
54 };
Level2 - QuickT9
Problem Statement
Most modern mobile phones include T9 technology for typing text messages faster, and your brand new mobile phone is not an exception. Your mobile phone has the standard keyboard layout:
Button Letters
2 a,b,c
3 d,e,f
4 g,h,i
5 j,k,l
6 m,n,o
7 p,q,r,s
8 t,u,v
9 w,x,y,z
T9 requires a dictionary of words. At each moment, T9 maintains three strings: D -- the current combination of digits, F -- the "fixed" part of the message and U -- the "unfixed" part of the message. The message displayed on the phone's screen consists of the "fixed" part immediately followed by the "unfixed" part, i.e., it appears as F + U. The current combination of digits D is only stored in memory and not displayed. There always is the following correspondence between D and U: they have the same length and the i-th character in U is a letter written on the button with digit equal to the i-th character in D. Additionally, the string U must always be such that there's at least one word in the dictionary that starts with U. For a given combination of digits D, we will call a string U valid if it satisfies the described conditions. When you start typing a new message, all three strings D, F and U are empty. Then you may do the following:
press one of the digit buttons (2-9): first, the pressed digit is added to the end of D, then U is changed to the lexicographically earliest string that is valid for the new value of D. If there are no such strings, the button press is ignored, so the values of D and U remain the same as before the button press.
press the Right button: first, U is appended to the end of F, then both D and U are reset to empty strings.
press the C button: U is appended to the end of F, then both D and U are reset to empty strings, finally, if F is not empty, the last character is removed from F.
press the * button: U is changed to the lexicographically next string valid for the current value of D. If there is no such string, it is set to the lexicographically smallest valid string again.
T9 technology is very useful when you need to type a message consisting of dictionary words. However there is a small drawback - typing a word that is not contained in the dictionary becomes much more difficult, so usually you have to type this word part by part (turning T9 off is not considered). The problem you are facing now is to type a given word using T9. Return the smallest number of button presses needed to type this word on your mobile phone if it is possible at all, otherwise return -1. The word is considered to be typed if F is equal to the word and U is empty. The dictionary is given in vector <string> t9. Each element of t9 is a list of words from the dictionary separated by single spaces.
Definition
Class:
QuickT9
Method:
minimumPressings
Parameters:
vector <string>, string
Returns:
int
Method signature:
int minimumPressings(vector <string> t9, string word)
(be sure your method is public)
Notes
-
If two Strings A and B have the same length, then A comes before B lexicographically if it has an alphabetically earlier character at the first position where the Strings differ.
-
It's possible that the dictionary contains multiple occurrences of the same word.
Constraints
-
t9 will contain between 1 and 50 elements, inclusive.
-
Each element of t9 will contain between 1 and 50 characters, inclusive.
-
Each element of t9 will contain only lowercase letters ('a'-'z') and spaces, and will contain no leading, trailing or consecutive spaces.
-
word will contain between 1 and 50 characters, inclusive.
-
word will contain only lowercase letters ('a'-'z').
Examples
0)
{"aae", "bab", "abad", "bdbd", "beta"}
"babe"
Returns: 9
Button Result (the "unfixed" part of message in quotes)
1) 2 "a" (beginning of "aae")
2) 2 "aa" (beginning of "aae")
3) 2 "aba" (beginning of "abad")
4) * "bab" (beginning of "bab")
5) C ba
6) 2 ba"a" (beginning of "aae")
7) 3 ba"bd" (beginning of "bdbd")
8) * ba"be" (beginning of "beta")
9) Right babe
1)
{"ann","ie"}
"annie"
Returns: 7
Button Result (the "unfixed" part of message in quotes)
1) 2 "a" (beginning of "ann")
2) 6 "an" (beginning of "ann")
3) 6 "ann" (beginning of "ann")
4) Right ann
5) 4 ann"i" (beginning of "ie")
6) 3 ann"ie" (beginning of "ie")
7) Right annie
2)
{"ann","amm"}
"annie"
Returns: -1
3)
{"aaa aab","aac aba abb ccca"}
"aba"
Returns: 6
Button Result (the "unfixed" part of message in quotes)
1) 2 "a" (beginning of "aaa")
2) 2 "aa" (beginning of "aaa")
3) * "ab" (beginning of "aba")
4) Right ab
5) 2 ab"a" (beginning of "aaa")
6) Right aba
4)
{"acac aba aaab","aab aa baa","bba bacade abb","baba"}
"abbaca"
Returns: 10
Button Result (the "unfixed" part of message in quotes)
1) 2 "a" (beginning of "aa")
2) 2 "aa" (beginning of "aa")
3) * "ab" (beginning of "aba")
4) Right ab
5) 2 ab"a" (beginning of "aa")
6) 2 ab"aa" (beginning of "aa")
7) 2 ab"aaa" (beginning of "aaab")
8) 2 ab"aaab" (beginning of "aaab")
9) 3 ab"bacad" (beginning of "bacade")
10) C abbaca
5)
{"aaa aab aac","aba abb","ccca"}
"ccc"
Returns: 5
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.
어떻게 풀라는거임?
Level3 - InfiniteLab
Problem Statement
There is an infinite labyrinth somewhere on Earth. It has an infinite number of rows, a fixed number W of columns and consists of 1x1 cells. Each cell can be in one of three states: free cell with a teleport, free cell without a teleport and blocked cell. It is known that each row in the labyrinth contains either 0 or 2 cells with teleports. The rows and columns of the labyrinth are numbered using integers. The rows are infinite in both directions, so for every integer i (including negative integers) there's a row numbered i. The columns are numbered 0 to W-1, inclusive. A cell in row i and column j is denoted as (i,j). If you are located in a free cell (i,j), you can perform one of the following actions:
Walk to another free cell (x,y) adjacent by side to (i,j). In other words, (x,y) must be such that |i-x| + |j-y| = 1. It is impossible to walk outside of the labyrinth.
If cell (i,j) contains a teleport, you can use it to be transferred to another free cell from the same row that contains a teleport (there's always exactly one such cell). Note that when you are located in a cell with a teleport, it isn't necessary to use the teleport.
Each of the described two actions, that is, walking to an adjacent cell and using a teleport, counts as one move. You are given a vector <string> map containing H rows, with each element consisting of W characters. The character j in element i of map represents the state of cell (i,j), where '#' means a blocked cell, '.' means a free cell and 'T' means a free cell with a teleport. Both indices i and j are 0-based, so map describes the states of all cells in rows 0 to H-1, inclusive. For all other cells the following rule applies: the state of cell (i,j) is exactly the same as the state of cell (x,j) if |i-x| is divisible by H. In other words, the given pattern of H rows is repeated an infinite number of times. Return the minimum number of moves needed to get from cell (r1,c1) to cell (r2,c2). If it is impossible, return -1.
Definition
Class:
InfiniteLab
Method:
getDistance
Parameters:
vector <string>, long long, int, long long, int
Returns:
long long
Method signature:
long long getDistance(vector <string> map, long long r1, int c1, long long r2, int c2)
(be sure your method is public)
Notes
-
The start and finish cells (r1,c1) and (r2,c2) are guaranteed to be distinct free cells.
Constraints
-
map will contain between 1 and 20 elements, inclusive.
-
Each element of map will contain between 1 and 20 characters, inclusive.
-
All elements of map will contain the same number of characters.
-
Each character in map will be either '#', '.' or 'T'.
-
Each element of map will contain either 0 or 2 'T' characters.
-
r1 and r2 will each be between -10^15 and 10^15, inclusive.
-
c1 and c2 will each be between 0 and W-1, inclusive, where W is the number of characters in each element of map.
-
Cells (r1,c1) and (r2,c2) will both be free cells.
-
Cells (r1,c1) and (r2,c2) will be distinct.
Examples
0)
{"#...##",
".##...",
"..#.##",
"#.#.##"}
1
0
5
3
Returns: 7
The optimal path is drawn below. Here 'S' means the start cell, 'F' means the finish cell and 'P' means an intermediate cell.
#...##
S##...
PP#.##
#P#.##
#PPP##
.##F..
..#.##
#.#.##
Note that the labyrinth is infinite, so only its part with rows 0 to 7, inclusive, is shown here and in subsequent examples.
1)
{"##.#.",
".#T#T",
"...#.",
"##.#."}
7
4
1
0
Returns: 9
##.#.
F#T#T
PPP#.
##P#.
##P#.
.#T#T
...#P
##.#S
Here we need to use a teleport once.
2)
{"..######.#",
".###T###.T",
"..T#.##T##",
".######..#"}
1
0
6
4
Returns: 11
..######.#
S###T###.T
PPT#.##T##
.######PP#
..######P#
.###T###PT
..T#F##T##
.######..#
Here we need to use a teleport twice.
3)
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.
