일요일 새벽 1시에 열렸던 매치.. 왠지 예감이 안좋았는데.. 역시나..;; 이번에도 최악의 퍼포먼스를 보이면서.. 좌절했다.. 두번연속 방 최하위.. ㅠ_ㅠ 덕분에 14번의 매치만에 결국 Div2로 추락했다.. 요즘 컨디션이 안좋은건가.. 실력이 줄고있는건가..;; 젠장.. 앞으로 3주동안 참여할수 있는 SRM도 없는데.. 당분간 좀 휴식을 취해야겠다..
rating을 힘들게 조금씩 올려놓았건만.. 떨어지는건 순식간이군.. 마지막 3번 매치만에 무려 375점을 까먹었다..
Level1 - Embassy
Problem Statement
You've just qualified for the on-site round of a major coding tournament! You now need to sort out a visa to allow you to travel to the event. You know that this is likely to be a long process, but are determined to sort it out as quickly as possible, even if it means working day and night. The process involves filling out a series of forms, which then have to be approved by the embassy. When the last form is approved your visa is granted. The approval process is very quick (instantaneous for the purpose of this problem), but there is a catch: each form has to be approved by the embassy before they will give you the next form to fill out. The embassy opens at exactly the same time each day and remains open for openTime time units. By the non-standard embassy clocks, a day is dayLength time units long, so the embassy then remains closed for dayLength - openTime time units before it opens the next day. Forms can be approved at any point in time between the time that the embassy opens and the time it closes, inclusive. However, if you finish filling in a form when the embassy is closed, you have to wait until it opens again before the form can be approved. The length of time it takes you to fill out form i is forms[i] units and the forms must be completed in the order they are given in forms. You already have the first form in your possession and can start filling it out at any time. Return the minimum length of time between starting to fill out the first form and getting your visa granted.
Definition
Class:
Embassy
Method:
visaApplication
Parameters:
vector <int>, int, int
Returns:
int
Method signature:
int visaApplication(vector <int> forms, int dayLength, int openTime)
(be sure your method is public)
Constraints
-
forms will contain between 1 and 50 elements, inclusive.
-
Each element of forms will be between 1 and 1,000,000 (10^6), inclusive.
-
dayLength will be between 1 and 1,000,000 (10^6), inclusive.
-
openTime will be between 1 and dayLength, inclusive.
Examples
0)
{4,4,4}
24
8
Returns: 12
The embassy is open for 8 hours out of a 24 hour day. Each of the three forms takes 4 hours to fill in. If you start filling in the first form 4 hours before the embassy opens, you can get it approved just as the embassy opens. The embassy will still be open 4 hours later to approve the second form and the third form can be approved just as the embassy shuts. Since you never have to wait, the total time is 12 hours.
1)
{4,4,4,4}
24
8
Returns: 28
Now there is an additional form to fill in. You can't complete the process in a single day.
2)
{2,2,2,2}
24
1
Returns: 73
The embassy is only open for one hour each day, so you can only get one form approved per day.
3)
{25,500,630,2500,1000,350,22,58,100,400,500,5000}
1440
360
Returns: 16945
Time is now measured in minutes. It's optimal to start filling in the first form 335 minutes after the embassy first opens.
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.
input으로 여러개의 form을 작성하는데 걸리는 시간과 하루의 길이(?)와 하루에 대사관이 열려있는 시간이 주어진다.. visa를 받기위해 여러 form을 작성해야하는데 form을 순서대로 하나씩 제출해야 다음 form을 받을 수 있다.. visa를 받으려면 최소 몇시간을 기다려야하는지 구하기..
단순 simulation 이지만 구현이 상당히 까다로운 문제이다..
그러나 modular 연산을 사용하면 구현을 상당히 간단하게 할 수 있다..
그러기 위해서 지금까지 진행된 시간 합과는 별로로 현재가 하루중 몇시인지를 따로 관리한다..
그래서 현재시간이 openTime 안에 들지못하면.. 다음날 시작시간까지 기다려야한다는 의미이다..
그리고 또하나.. 처음에 무조건 0시부터 시작하면 최적이 아닌경우도 있다..
처음에 일부러 몇시간 기다리고 시작하는 경우가 나중에 더 효율적으로 끝나는 경우가 있는데..
바로 샘플 2번 케이스가 그렇다..
아.. 정말 어려운 문제..
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
11 class Embassy {
12 public:
13
14
15 int visaApplication(vector <int> forms, int dayLength, int openTime)
16 {
17 int res, cur;
18 int i, j;
19 int min1;
20 min1 = INF;
21 for (j= 0; j <= openTime; j++) {
22 res = forms[0];
23 cur = j;
24 for (i = 1; i < forms.size(); i++) {
25 res += forms[i];
26 cur += forms[i];
27
28 cur = cur % dayLength;
29 if (cur > openTime) {
30 res += dayLength - cur;
31 cur = 0;
32 }
33 }
34 min1 = min(min1, res);
35 }
36 return min1;
37 }
38
39 };
Level2 - StringInterspersal
Problem Statement
A string S is an interspersal of a set of strings W, if W is a set of disjoint subsequences of S which cover S. Less formally, S can be formed from W by partitioning each member of W into substrings, then concatenating all the substrings, while maintaining the order of the substrings within each element of W. For example, if W contains the strings {"DESIGN", "ALGORITHM", "MARATHON"}, then one possible interspersal would be "ADELGMAORARISIGNTHMTHON", formed as shown below.
DE SIGN A LG O RI THM MA RA THON ----------------------- ADELGMAORARISIGNTHMTHON
Given a vector <string> W, return the lexicographically minimum interspersal of the strings in W
Definition
Notes
-
The lexicographically minimum of two strings is the one with the alphabetically earlier character at the first position at which they differ.
-
The return string will contain no more than 1000 characters.
Constraints
-
W will contain between 1 and 20 elements, inclusive.
-
Each element of W will contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
Examples
0)
{"DESIGN","ALGORITHM","MARATHON"}
Returns: "ADELGMAORARISIGNTHMTHON"
The example from the problem statement.
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.
문자열이 여러개 주어지고.. 각 문자열을 모두 mix해서 lexy smallest한 문자열 하나를 만들기.. 이때 원래 문자열들은 문자의 순서가 뒤바뀌면 안된다..
to be updated..
Level3 - KPlanetaryAlignment
Problem Statement
A particular star system consists of a single star, with N planets orbiting it. Each planetary orbit is a perfect circle of distinct radius centered on the star and all orbits lie in the same 2-D plane. The planets move along their circular paths with constant speed and planet i completes 1 full orbit in the time given by the absolute value of periods[i]. periods[i] will be positive if planet i orbits clockwise and negative if it orbits counter-clockwise. A k-planetary alignment occurs when an infinite straight line exists, passing through the center of the star and through the centers of at least k of the planets. A N-planetary alignment occurs at time T = 0, i.e., all the planets lie in a line at this time (see notes for clarification). Return the number of distinct times between T1 and T2, inclusive, when a k-planetary alignment occurs.
Definition
Class:
KPlanetaryAlignment
Method:
number
Parameters:
vector <int>, int, int, int
Returns:
int
Method signature:
int number(vector <int> periods, int k, int T1, int T2)
(be sure your method is public)
Notes
-
The constraints ensure the return value will fit in a signed 32-bit integer.
-
Alignments can occur with the planets either on the same side of the star or diametrically opposite each other.
-
The configuration of the planets at T = 0 (i.e., whether the planets are all on the same side, or some are diametrically opposite) makes no difference to the answer.
Constraints
-
periods will contain between 2 and 5 elements, inclusive.
-
Each element of periods will be a non-zero integer between -100 and 100, inclusive.
-
The elements of periods will be distinct.
-
k will be between 2 and the number of elements in periods, inclusive.
-
T2 will be between 0 and 50,000,000 (5 * 10^7), inclusive.
-
T1 will be between 0 and T2, inclusive.
Examples
0)
{8,40}
2
0
20
Returns: 5
Here, the first planet is rotating 5 times as quickly as the second. Ater 5 seconds, the first will have completed 5/8 of an orbit, while the second will have completed 5/40 = 1/8 of an orbit. They are therefore diametrically opposite and this is the first 2-alignment after time 0. Further 2-alignments happen at T = 10, 15 and 20.
1)
{8,24,40}
2
0
20
Returns: 8
With an additional planet, 2-alignments happen at T = 0, 5, 6, 10, 12, 15, 18, 20.
2)
{8,24,40}
3
0
100
Returns: 4
3-alignments of the same set of planets happen at T = 0, 30, 60, 90.
3)
{-10,10}
2
2
26
Returns: 10
Now that the planets are rotating in opposite directions, 2-alignments occur every 2 1/2 seconds.
4)
{-1,2,3,4,5}
3
10000
50000
Returns: 53333
5)
{-1,1}
2
0
50000
Returns: 200001
6)
{-2,91,87,77,71}
4
0
50000000
Returns: 1471
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.
rating을 힘들게 조금씩 올려놓았건만.. 떨어지는건 순식간이군.. 마지막 3번 매치만에 무려 375점을 까먹었다..