어제 새벽 1시에 열린 매치.. 정말 오랜만에 열렸다..
예전에는 1주일에 한번꼴로 있었는데.. 요즘 경기침체의 영향인지.. SRM이 반으로 줄었다..
원래는 토->일 넘어가는 새벽에 열릴 예정이었는데..
아레나 등록 관련에러가 마구 나면서 자꾸 시간이 미뤄지더니.. 결국 취소되고..
바로 하루 뒤인 일->월 넘어가는 새벽에 다시 열렸다..
이때 매치를 참여하려던 많은 사람들은 기다리기 지루한지 다들 어드민 방에 들어와서 잡담을 나눴다..~ ㅎㅎ
새벽시간에 무려 1시간넘게 기다렸더니 결국은.. 24시간 연기.. -_-
어쨋든 우여곡절끝에 SRM 438이 다시 열렸는데.. 문제가 너무 tricky하게 나와서.. 줄줄이 다 fail했다..
나도 300점짜리라도 먹어보려고 삽질하다가 결국 시간내에 코딩을 완료하지 못했다.. ㅠ_ㅠ
이번 매치는 완전 챌린지의 향연이었다.. 우리방에서 총 16개의 submission중에 12개가 챌로 날라가버렸다..
남은 4개중에서도 2개는 system test fail.. 결국 2개만 pass해버렸다.. -_-
덕분에 0점을 맞고도 적극적으로 챌은 한 사람은 예상외의 고득점을 얻을 수 있었다..
역시 예상대로 페트르가 1등을 차지했는데.. 이거 점수가 좀 엽기적인데..
그리고 한국인 1등이 전체 4등을 하는 기염을 토했다..~
[300] UnluckyIntervals
Problem Statement
You are given a set of integers called luckySet. An interval [A,B], where B is greater than A, and A and B are positive integers, is considered unlucky if none of the integers between A and B, inclusive, belongs to luckySet. An integer x is considered to be luckier than another integer y if the number of unlucky intervals that contain x is smaller than the number of unlucky intervals that contain y. In case both x and y belong to an equal number of unlucky intervals, or both belong to an infinite number of unlucky intervals, the smallest of them is considered to be luckier than the other. Given a vector <int> luckySet, return the top n luckiest positive integers sorted in descending order by luckiness (in other words, each element of the vector <int> must be luckier than the next element).
Definition
Class:
UnluckyIntervals
Method:
getLuckiest
Parameters:
vector <int>, int
Returns:
vector <int>
Method signature:
vector <int> getLuckiest(vector <int> luckySet, int n)
(be sure your method is public)
Constraints
-
luckySet will contain between 1 and 50 elements, inclusive.
-
Each element of luckySet will be between 1 and 1000000000, inclusive.
-
Each element of luckySet will be distinct.
-
n will be between 1 and 100, inclusive.
Examples
0)
{3}
6
Returns: {3, 1, 2, 4, 5, 6 }
0 unlucky intervals contain 3. 1 unlucky interval contains 1: [1,2]. 1 unlucky interval contains 2: [1, 2]. Since 1 and 2 are inside an equal number of intervals, 1 is considered luckier because it is less than 2. For every number greater than 3, there is an infinite number of unlucky intervals that contain it. However, 4 and 5 are considered to be the luckiest among them, as they are smallest.
1)
{5, 11, 18}
9
Returns: {5, 11, 18, 1, 4, 6, 10, 2, 3 }
3 unlucky intervals: [1,2], [1,3] and [1,4] include 1. 3 unlucky intervals: [1,4], [2,4] and [3,4] include 4. 4 unlucky intervals: [6,7], [6,8], [6,9] and [6,10] include 6. 4 unlucky intervals: [6,10], [7,10], [8,10] and [9,10] include 10. 5 unlucky intervals: [1,2], [1,3], [1,4], [2,3] and [2,4] include 2. 5 unlucky intervals: [1,3], [1,4], [2,3], [2,4] and [3,4] include 3.
2)
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.
positive integer로 이루어진 lucky set이 주어지고 lucky set에 있는 수를 하나도 포함하지 않는 임의의 interval [A, B] 를 unlucky interval이라고 한다.. 적은 수의 unlucky interval에 포함되는 수일수록 lucky 하다고 할때, lucky한 순서대로 n개의 수를 return..
A certain theoretical machine works by executing a program exactly s times. The first time it is executed, the program is given the String input as its input. For each subsequent execution, the program uses the output of the previous execution as its input. The initial input is a string containing only lowercase letters. A program is defined as a string containing lowercase letters and '$' characters. The output of a program is simply this string with all instances of the '$' character replaced by the program's input. For example, if the input is "a" and the program is "$meric$", the first output would be "america". The second time it is executed, it will use "america" as its input, and its output will be "americamericamerica". This process is repeated s times, so for a large s, the output would be: "americamericamericamericamericamericamericamericamericamericamericamericamericamericamerica...". Given the input, the program and s, return the substring of the machine's final output starting at index min and ending at index max, where min and max are inclusive 1-based indices. If an index between min and max exceeds the bounds of the final output, put a placeholder '-' character in its place.
Definition
Class:
EndlessStringMachine
Method:
getFragment
Parameters:
string, string, int, int, int
Returns:
string
Method signature:
string getFragment(string input, string program, int s, int min, int max)
(be sure your method is public)
Constraints
-
input will contain between 1 and 50 characters, inclusive.
-
program will contain between 2 and 50 characters, inclusive.
-
Each character in input will be a lowercase letter ('a'-'z').
-
Each character in program will be '$' or a lowercase letter ('a'-'z').
-
The first character in program will be '$'.
-
s will be between 1 and 1000000000, inclusive.
-
min will be between 1 and 1000000000, inclusive.
-
max will be between min and min+99, inclusive.
Examples
0)
"a"
"$meric$"
6
1
35
Returns: "americamericamericamericamericameri"
This is the example from the statement.
1)
"top"
"$coder"
1
1
20
Returns: "topcoder------------"
One execution is not enough to cover all 20 requested characters. Use the placeholder - character for the indexes that exceed the final output's size.
2)
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..
[1000] FeudaliasWar
Problem Statement
Feudalia's military is preparing a preemptive strike against Banania's military installations. Feudalia has a number of missile silos. Each silo has an unlimited number of missiles at its disposal, but can only fire a single missile at a time. When a missile is fired, it requires takeOffTime seconds before it can take off from its silo. Once it takes off, it requires distance/missileSpeed minutes to reach its target, where distance is the Euclidean distance between the silo and the target. When the missile reaches its target, the target is instantly destroyed. After a missile takes off, its silo requires rechargeTime minutes of preparation before it can launch another missile. The general has ordered you to destroy all of Banania's military bases in as little time as possible. You are given vector <int>s siloX, siloY, baseX and baseY which determine the locations of the missile silos and bases. Feudalia's i-th missile silo is located at (siloX[i], siloY[i]) and Banania's j-th base is located at (baseX[j], baseY[j]). Return the minimum time in minutes required to destroy all enemy bases.
Definition
Class:
FeudaliasWar
Method:
getMinimumTime
Parameters:
vector <int>, vector <int>, vector <int>, vector <int>, int, int, int
Returns:
double
Method signature:
double getMinimumTime(vector <int> baseX, vector <int> baseY, vector <int> siloX, vector <int> siloY, int takeOffTime, int rechargeTime, int missileSpeed)
(be sure your method is public)
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
takeOffTime will be between 1 and 60, inclusive.
-
rechargeTime will be between 5 and 1000, inclusive.
-
missileSpeed will be between 1 and 2000, inclusive.
-
baseX will contain between 1 and 50 elements, inclusive.
-
baseY will contain the same number of elements as baseX.
-
siloX will contain between 1 and 50 elements, inclusive.
-
siloY will contain the same number of elements as siloX.
-
Each element of baseX, baseY, siloX and siloY will be between 0 and 1000000, inclusive.
-
The locations for each base and silo will be distinct.
Examples
0)
{0,0,50}
{0,50,0}
{50,0,1000}
{50,1000,0}
30
20
1
Returns: 91.5
An optimal strategy would be: 00:00 : The silo at (50,50) launches an attack against the base at (0,0). 00:30 : The first missile finishes taking off. 20:30 : The silo at (50,50) launches its second missile, this time against the base at (0,50). 21:00 : The second missile finishes taking off. 41:30 : The silo at (50,50) launches its third missile, this time against the base at (50,0). 71:00 : The second missile hits the base at (0,50) (The distance was 50). 71:12.6 (Approx.) : The first missile hits the base at (0,0) (The distance was 70.710678119). 91:30 : The third missile hits the remaining base.
1)
{0,0,50}
{0,50,0}
{50,0,1000}
{50,1000,0}
30
900
1
Returns: 950.5
Since it now takes 15 hours to prepare a new missile, using the same silo against the three enemy bases is no longer the optimal strategy. Instead, each of the silos at (0,1000) and (1000,0) should target the closest base while the silo at (50,50) targets the base at (0,0).
2)
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.
