토->일 새벽에 열린 매치.. Div1 에만 무려 700명 넘게 참가했다..
근데 문제가 드럽게 나와서 다들 고생이 많았다..
나는 250 을 매우 늦게 풀었는데도 풀구하고 rating 이 올랐다..~
근데.. 아깝게 4점 차이로 yellow 등극 실패.. ㅠ_ㅠ
470번대 마지막 매치라서 그런지 문제 description에 47 이 자주 등장한다.. -_-;
Level1 - TheCoffeeTimeDivOne
Problem Statement
John and Brus are flying on an airplane and now it's coffee time. There are n seats in the plane numbered from 1 to n, one seat in each row. All seats are occupied, thus there are n passengers overall (including John and Brus). A stewardess will serve a cup of coffee or tea to each passenger. She needs to serve tea to all passengers whose seat numbers are listed in vector <int> tea, and she needs to serve coffee to all other passengers. A coffee and tea machine is located just before the first seat of the plane. The stewardess has a flask that can contain enough coffee or tea to serve at most 7 passengers. Initially, the stewardess is located near the coffee and tea machine and the flask is empty. The stewardess can perform the following kinds of actions:
Move from the coffee and tea machine to seat 1 or move from seat 1 to the coffee and tea machine. Each of these two actions takes 1 second.
Move from seat i, i > 1, to seat i-1. It takes 1 second.
Move from seat i, i < n, to seat i+1. It takes 1 second.
If she is near seat i, the passenger at this seat has not yet been served and the current type of drink in the flask is the same as the drink this passenger wants, she can serve this passenger with a cup of drink he/she wants. It takes 4 seconds.
If she is near the coffee and tea machine and the flask is empty, she can fill the flask with either tea or coffee (but not both simultaneously). It takes 47 seconds. Note that she can fill the flask partially (to serve less than 7 passengers), but it still takes 47 seconds.
Given int n and vector <int> tea, return the minimal time needed for the stewardess to serve all passengers with proper drinks and return to the coffee and tea machine.
Definition
Class:
TheCoffeeTimeDivOne
Method:
find
Parameters:
int, vector <int>
Returns:
long long
Method signature:
long long find(int n, vector <int> tea)
(be sure your method is public)
Constraints
-
n will be between 2 and 44,777,777, inclusive.
-
tea will contain between 1 and 47 elements, inclusive.
-
Each element of tea will be between 1 and n, inclusive.
-
All elements of tea will be distinct.
Examples
0)
2
{1}
Returns: 108
The stewardess will serve coffee in 47+2+4+2=55 seconds and tea in 47+1+4+1=53 seconds.
1)
2
{2, 1}
Returns: 59
Here she only needs to serve tea.
2)
15
{1, 2, 3, 4, 5, 6, 7}
Returns: 261
The stewardess will fill the flask three times overall: once with tea and two times with coffee.
3)
47
{1, 10, 6, 2, 4}
Returns: 891
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부터 n 까지 일렬로 있고 커피와 티는 0 번 위치에 있다.. tea 를 원하는 승객이 주어지고 나머지는 다 coffee 를 원할때 스튜어디스가 모두 serve 하는데 드는 비용 최소화하기.. 스튜어디스는 한번에 coffee 또는 tea 중에 하나만 가지고 이동할수 있고 최대 7명까지 serve 할 수 있다.. 그 이상 serve 하기 위해서는 다시 0번으로 돌아와서 coffee 또는 tea 를 채워야한다.. 블라블라.. 문제 뭐이리 복잡하냐..
많은 사람들을 안드로로 보냈다..~ challenge 도 많았지만.. system test fail 도 상당히 많았다..
이번에 문제출제자 도대체 누구여..~
이 문제는 greedy + simulation 으로 풀었다..~
일단 tea 부터 다 serve 하고 그담에 coffee 를 serve 하는데.. 마지막에 돌아오는 거리를 최소화하기 위해
가장 뒤에서부터 serve 한다..~
loop 를 4천만번 넘게 돌아도 TLE 안나고.. 배열 4천만개 잡고 MLE 도 안나고.. 탑코더 좋은데..?
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 char check[44777778];
13
14 class TheCoffeeTimeDivOne {
15 public:
16
17 long long find(int n, vector <int> tea)
18 {
19 int size;
20 int i, j, fl;
21 int cur;
22 long long sum;
23 size = tea.size();
24 sort(tea.begin(), tea.end());
25 sum = 0;
26 cur = 0;
27 j = 0;
28 fl = 0;
29 memset(check, 0, sizeof(check));
30 for (i = size-1; i >= 0; i--) {
31 if (!fl) {
32 sum += 47;
33 fl++;
34 }
35 check[tea[i]] = 1;
36
37 if (cur == 0) {
38 sum += tea[i] + 4;
39 }
40 else {
41 sum += cur - tea[i] + 4;
42 }
43 j++;
44 cur = tea[i];
45 if (j == 7) {
46 cur = 0;
47 sum += tea[i];
48 j = 0;
49 fl = 0;
50 }
51 }
52 sum += cur;
53 cout << "sum1 = " << sum << endl;
54
55 if (size == n) {
56 return sum;
57 }
58
59 fl = 0;
60 cur = 0;
61 j = 0;
62 for (i = n; i >= 1; i--) {
63 if (check[i])
64 continue;
65 if (!fl) {
66 fl++;
67 sum += 47;
68 }
69 if (cur == 0) {
70 sum += i + 4;
71 }
72 else {
73 sum += cur - i + 4;
74 }
75 j++;
76 cur = i;
77 if (j == 7) {
78 sum += i;
79 cur = 0;
80 j = 0;
81 fl = 0;
82 }
83 }
84 sum += cur;
85 cur = 0;
86 cout << "sum2 = " << sum << endl;
87 return sum;
88 }
89
90 };
Level2 - TheAirTripDivOne
Problem Statement
In some country there are n cities numbered from 1 to n. There are also several types of flights between them. Each flight type is characterized with 5 integers A, B, F, T and P. All flights of this type depart from city A and arrive at city B (without changing planes in any intermediate cities). Each flight type is one-directional, so it is impossible to fly from city B to city A using the same flight type. All flights of the same type depart with some periodicity. More precisely, the first flight of this type departs from A at time F, the next flight departs at time F + P, then at F + 2P, and so on (there are infinitely many flights of the same type). Each flight of the same type has the same flight time T. I.e., if a plane departs from A at time T0, then it arrives to B at time T0 + T. The description of all flight types is given in vector <string> flights. Concatenate the elements of this vector <string> in the same order as they are given without any delimiters between its elements to get a single string. This string will contain a single space separated list of flight type descriptions. Each such description will be of the form "A,B,F,T,P" (quotes for clarity), where the meaning of integers A, B, F, T and P is exactly the same as defined in the previous paragraph. John would like to travel from city 1 to city n where his friend Brus is waiting for him. Unfortunately, there are no direct flights from 1 to n, so he will have to use several flights to reach city n. He can't use any other transport besides planes, so the departure city of each next flight he takes must be the same as the arrival city of the previous flight he has taken. Moreover, in order for him to be able to change planes, the departure time of each next flight must be strictly greater than the arrival time of the previous flight. If he arrives at some city at time T1 and then departs at time T2, the waiting time in this city is equal to T2 - T1. John defines the safety of his route from 1 to n as the minimum of waiting times over all cities where he changes flights. John wants to arrive at city n no later than at time moment time. If there are several routes that achieve this goal, he wants to choose the route among them with the maximum possible safety. Return this maximum possible safety. If there are no such routes, return -1.
Definition
Class:
TheAirTripDivOne
Method:
find
Parameters:
int, vector <string>, int
Returns:
int
Method signature:
int find(int n, vector <string> flights, int time)
(be sure your method is public)
Constraints
-
n will be between 3 and 477, inclusive.
-
flights will contain between 1 and 47 elements, inclusive.
-
Each element of flights will contain between 1 and 47 characters, inclusive.
-
The concatenation of all elements of flights will be a single space separated list of flight type descriptions without leading or trailing spaces.
-
Each flight type description will be of form "A,B,F,T,P" (quotes for clarity), where A, B, F, T and P are integers formatted with no extra leading zeros.
-
In each flight type, A and B will be distinct integers between 1 and n, inclusive.
-
In each flight type, F, T and P will be between 1 and 1,000,000,000, inclusive.
-
There will be no flight from city 1 to city n.
-
time will be between 1 and 1,000,000,000, inclusive.
Examples
0)
3
{"1,2,1,4,7 ", "2,3,9,1,10"}
20
Returns: 14
The optimal way is to take the first flight at time 1 and the second one at time 19.
1)
3
{"1,2,1,1,1 2,3,2,1,98"}
100
Returns: -1
Since John needs a strictly positive time to change a flight, it is possible to get to city 3 only at time 101.
2)
477
{"47,74,1,1,1"}
20
Returns: -1
It is impossible to reach the destination at all.
3)
7
{"1,3,15,17,11 1,3,14,16,14 5,7,12,18,18 1,6,13,1",
"6,12 1,2,18,14,13 5,6,10,10,18 3,1,10,10,10 1,3",
",17,16,10 2,3,16,18,16 6,1,15,12,10 2,1,15,18,1",
"0 4,7,10,16,15 6,3,10,14,10 1,6,19,19,15 1,4,12",
",10,14 4,7,10,18,14 2,3,16,12,12 1,3,14,10,19 3",
",7,17,10,12 2,1,14,12,16 4,3,19,11,12 1,6,10,18",
",12 2,3,16,12,10 6,2,10,18,12 5,1,14,18,12 5,1,",
"18,10,10 3,2,19,15,10 7,4,16,19,14 6,3,16,12,10",
" 5,7,14,13,13 1,3,12,10,16 5,7,16,18,15 6,2,18,",
"12,14 3,2,10,18,16 4,2,18,18,14 1,5,10,18,16 2,",
"3,10,19,16 1,4,11,18,15 2,1,15,15,14 7,2,10,12,",
"10"}
74
Returns: 33
Note that there can be multiple flight types with the same departure city and the same arrival city.
4)
7
{"1,4,10,8,2 4,6,14,8,2 6,2,8,1",
"0,1 2,7,19,5,1 ",
"1,5,15,17,11 5,3,10,1",
"0,18 3,7,12,18,18"}
147
Returns: 35
Take the flight from city 1 to city 4 at time 10 to arrive at city 4 at time 18. Then take the flight from city 4 to city 6 at time 54 to arrive at city 6 at time 62. Next take the flight from city 6 to city 2 at time 97 to arrive at city 2 at time 107. Finally, take the flight from city 2 to city 7 at time 142 to arrive at city 7 exactly at time 147. The safety of this route is min{54 - 18, 107 - 62, 142 - 107} = 35.
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..
Level3 - TheBoardingDivOne
Problem Statement
John and Brus are going to board a plane. The boarding can be described using the following simplified model. There are 2 * n cells numbered from 1 to 2 * n from left to right. There are n seats in the plane numbered from 1 to n. The seat i is located near cell n + i. There are n passengers numbered from 1 to n. Initially they stand in some order in cells 1, 2, ..., n. The order can be described using a permutation p[1], p[2], ..., p[n] of integers from 1 to n, where p[i] is the number of the passenger who initially stands in cell i. It is known that passenger i wants to take seat i during boarding. The boarding process can be divided into primitive steps, each of which takes exactly 1 second. During each step, we can check all passengers from right to left and determine for each passenger what he/she will do according to the following rules:
Denote the number of the passenger we're currently checking as X and the current cell of this passenger as Y.
If Y < n + X and cell Y + 1 is currently empty, the passenger will move to this cell. It takes him exactly one step to complete this move, so at the beginning of the next step he/she will be in cell Y + 1.
If Y < n + X, cell Y + 1 contains a passenger and the passenger at cell Y + 1 will perform a move during the current step, the passenger at cell Y will also move to the next cell during the current step (exactly as described in the previous rule).
If Y < n + X, cell Y + 1 contains a passenger and the passenger at cell Y + 1 will not move during the current step, the passenger at cell Y will skip the current step (so he/she will still be in cell Y in the beginning of the next step).
If Y = n + X, it means that the passenger in cell Y has reached the cell near which his seat is located. Therefore he will take a seat and it takes 74 steps to do it. So cell Y will be occupied during steps S, S+1, ..., S+73 (where S is the number of the current step) because the passenger at this cell will be taking his/her seat. In the beginning of step S+74 this cell will become empty because the passenger has completed taking the seat.
The boarding time is defined as the number of steps performed until each passenger has taken his/her seat. Obviously, the boarding time can depend on the initial order of passengers. For example, if p[1] = 1, p[2] = 2, the boarding time is 76 (during the first two steps both passengers reach the cells with their seats, and during the next 74 steps they simultaneously take their seats). And if p[1] = 2, p[1] = 1, the boarding time is 151 (after one step passenger 1 will reach the cell with his/her seat, during the next 74 steps he/she will take his/her seat and passenger 2 will wait until it's finished, and then passenger 2 will need 76 more steps to reach the required cell and take a seat). You are given a vector <int> pattern that imposes some restrictions on the initial order of passengers (described by permutation p). This vector <int> contains exactly n elements. If pattern[i] (1-based) is an integer between 1 and n, inclusive, it means that p[i] must be equal to pattern[i], and if pattern[i] is -1, it means that p[i] can be an arbitrary integer between 1 and n, inclusive. The initial order of passengers is considered to be good if the boarding time for this order is not greater than boardingTime. Return the number of good initial orders of passengers that match the given pattern.
Definition
Class:
TheBoardingDivOne
Method:
find
Parameters:
vector <int>, int
Returns:
long long
Method signature:
long long find(vector <int> pattern, int boardingTime)
(be sure your method is public)
Constraints
-
pattern will contain between 2 and 18 elements, inclusive.
-
Each element of pattern will be either -1 or between 1 and n, inclusive, where n is the number of elements in pattern.
-
For each X between 1 and n, inclusive, there will be at most one occurrence of X in pattern.
-
boardingTime will be between 2 and 222, inclusive.
Examples
0)
{-1, -1}
100
Returns: 1
Here we have two possible permutations. In case of (1, 2) the boarding takes 76 seconds and in case of (2, 1) it takes 151 seconds.
1)
{-1, 2, -1}
222
Returns: 1
The only one good order is (1, 2, 3).
2)
{2, 1, 3, 5, 4, 6}
155
Returns: 1
Only one order matches pattern and the boarding for it takes exactly 155 seconds.
3)
{-1, -1, -1, -1, -1, -1, -1}
198
Returns: 233
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.
