지난주 토->일 새벽에 열린 매치..
그동안 시간이 안맞아서 SRM을 세개나 참가 못했는데..
오랜만에 참가해서 좋은 성적이 나와 다행이다..
매우 쉬운 250 과 난해한 550, 1000 이 나오면서 챌 하나로 순위가 급상승했다..
이번 SRM 은 sponsored by Facebook 인데.. 550 문제 description 이 좀..;;
예전에는 쉬운문제가 나오면 240이 넘기도 하고 그랬는데..
이제는 아무리 빨리 풀어도 간신히 200이 넘는수준이니.. 코딩 속도가 왜이리 무뎌졌지..;;
문제 해석이 난해한데 대해 불만이 많은 1인.. 음.. 그 심정은 이해하겠는데.. -_-;;
Level1 - Badgers
Problem Statement
Badgers are lovely furry animals, and Manao has just decided to start keeping a few. The pet shop has offered him N badgers, and they are all so cute that Manao wants to take as many as he can feed. Normally, a badger needs some amount of food per day to be satisfied. However, if he sees other badgers eating, his greed awakens and he wants to eat more. A badger will want a fixed additional amount of food for each co-eater. You're given vector <int>s hunger and greed, both containing N elements. The i-th element of hunger is the number of units of food that the i-th badger needs per day if he's alone. The i-th element of greed is the amount of additional units of food the i-th badger will need for each co-eater. Return the maximum number of badgers Manao can take while keeping them all satisfied if he can supply no more than totalFood units of food per day.
Definition
Class:
Badgers
Method:
feedMost
Parameters:
vector <int>, vector <int>, int
Returns:
int
Method signature:
int feedMost(vector <int> hunger, vector <int> greed, int totalFood)
(be sure your method is public)
Constraints
-
hunger will contain between 1 and 50 elements, inclusive.
-
greed will contain the same number of elements as hunger.
-
Each element of hunger will be between 1 and 1000, inclusive.
-
Each element of greed will be between 0 and 1000, inclusive.
-
totalFood will be between 1 and 1000000, inclusive.
Examples
0)
{1,2,3}
{2,2,1}
7
Returns: 2
Manao can take badger 0 and one of the other two badgers.
1)
{5,2,1,5}
{0,2,4,1}
19
Returns: 3
Badger 2 is too greedy, but the rest can be fed together and will only need (5 + 2 * 0) + (2 + 2 * 2) + (5 + 2 * 1) = 18 units of food.
2)
{1,1,1,1,1}
{1000,1000,1000,1000,1000}
10
Returns: 1
They are too greedy to eat together.
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.
badger 라는 애는 기본적으로 hunger 만큼을 먹는데.. 다른 badger 가 먹는걸 보면 1마리당 greed 만큼을 더 먹는다.. totalFood 만큼의 음식이 있을때 최대 몇마리의 badger 를 키울 수 있는지..
brute force 로 풀었다..
k 마리를 키운다고 가정하면 각 badger 당 필요한 food 는 hunger[i] + (k-1) * greed[i]
이 값에 대해서 sort 한 후 앞에 k 개의 합이 totalFood 안에 들어오면 가능
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 int comp(const void* x, const void* y)
13 {
14 int* a = (int*)x;
15 int* b = (int*)y;
16 return *a - *b;
17 }
18
19 class Badgers {
20 public:
21
22 int feedMost(vector <int> hunger, vector <int> greed, int totalFood)
23 {
24 int n, i;
25 int cnt, cur;
26 int sum[100];
27 n = hunger.size();
28 for (cnt = n; cnt >= 1; cnt--) {
29 for (i = 0; i < n; i++) {
30 sum[i] = hunger[i] + (cnt-1) * greed[i];
31 }
32 qsort(sum, n, sizeof(int), comp);
33 cur = 0;
34 for (i = 0; i < cnt; i++) {
35 if (cur + sum[i] > totalFood)
36 break;
37 cur += sum[i];
38 }
39 if (i == cnt)
40 return cnt;
41 }
42 return 0;
43 }
44
45 };
Level2 - FriendTour
Problem Statement
Social networks have become an integral part of our lives, and Manao is no exception. Back in the times when Facebook had no news feed, Manao was spending much of his time traversing his friends' profiles. As you might know, a profile is a page which contains various information about the user. It also shows some subset of his friends. To be more precise, if a user has less than K friends, the page shows them all and if not, then only K friends are shown. The subset of K friends is chosen from the set of all friends every time somebody visits the profile, and all subsets have equal probability of being chosen. Manao liked to perform tours of his friends' profiles. He started the tour at his profile and clicked on one of the friends visible on his page, thus moving to that friend's profile. From there, he again chose one of his friends from those visible on that page and moved to that person's profile, and so on. Manao never visited the profiles of people who were not his friends and never clicked on any of his friends' profiles twice. The tour was finished when he was not able to proceed because no unvisited profiles of his friends were visible. If Manao visited profiles of all his friends during the tour, it is considered to be completed, otherwise the tour is ruined. Manao lives in Manglisi and there are a total of N people from Manglisi registered at Facebook (including Manao). We shall number them from 1 to N, where Manao is number 1. It is known that all friends of each person from Manglisi also live in Manglisi. You are given a vector <string> friends containing N elements, where the i-th element (1-based) is a space-separated list of friends of the i-th person. Manao knows the list of friends of everybody in advance. Return the probability that Manao performs a complete tour if he behaves optimally, i.e., in such a way that this probability is maximized.
Definition
Class:
FriendTour
Method:
tourProbability
Parameters:
vector <string>, int
Returns:
double
Method signature:
double tourProbability(vector <string> friends, int K)
(be sure your method is public)
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
friends will contain between 2 and 36 elements, inclusive.
-
Each element of friends will contain between 1 and 36 characters, inclusive.
-
Each element of friends will contain a space-separated list of distinct integers without leading zeros.
-
Each of the numbers in friends will be between 1 and N, inclusive. Number i will never occur in element i (1-based) of friends.
-
If number i is present in friends[j], then number j will be present in friends[i] (both indices are 1-based).
-
K will be between 1 and 36, inclusive.
Examples
0)
{"2 3 4",
"1 3 4",
"1 2 4",
"1 2 3"}
1
Returns: 0.2222222222222222
Manao has three friends, who are all also friends with each other. Every time a profile is viewed, only one friend is shown. No matter which friend appears on Manao's profile first, the probability that Manao will continue his tour from that friend's profile is 2/3 and the probability that Manao will visit the last friend left is 1/3, which results in a total of 2/9.
1)
{"2 3 4",
"1 3 4",
"1 2 4",
"1 2 3"}
2
Returns: 0.6666666666666666
This time, two friends are shown on each profile. No matter how Manao chooses between unvisited profiles, there is a 1/3 probability that he won't be able to complete the tour.
2)
{"3 2 4",
"3 5 1",
"5 2 1 4",
"3 1 5",
"3 2 4"}
2
Returns: 0.3333333333333333
Note that the friend numbers in the lists don't have to follow in increasing order. Also, unlike the previous examples, this time the outcome depends on Manao's strategy.
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.
to be updated..
Level3 - SpaceshipEvacuation
Problem Statement
Manao is an engineer of a new spaceship. He is responsible for crew safety, particularly during a possible evacuation. The spaceship consists of N units numbered from 0 to N-1. The units are connected by passages, but during evacuation, moving through them is too slow and therefore is prohibited. Some pairs of units are connected by tunnels which contain emergency cabins. There are several emergency cabins at each end of each tunnel. A cabin is designed for a single person and may only be used once for security reasons. A cabin at one end of a tunnel can only be used to reach the other end of that same tunnel. The tunnel network has a special layout. Consider a sequence of units U0, U1, ..., UK with K ≥ 3 and U0=UK. If all U0, U1, ..., UK-1 are pairwise distinct and for each i, 0 ≤ i < K, Ui and Ui+1 are connected by a tunnel, this sequence is called a cycle. A cycle is called canonical if U0 < Ui for 1 ≤ i < K and U1 < UK-1. Each unit in the spaceship will be a part of at most one canonical cycle. The tunnel network is given as vector <string> tunnelNetwork, where each element describes a tunnel and contains four space-separated integers A, B, C, D. This means that there is a tunnel between units A and B and there are C emergency cabins in the tunnel from unit A's side and D emergency cabins from unit B's side. The crew of the spaceship consists of crewSize members. Each of them might be in any of the N units when the evacuation is announced. Unit 0 is connected to the rescue boat, so every person reaching this unit is considered evacuated. The distribution of emergency cabins within the tunnels is called an evacuation plan. An evacuation plan is called acceptable if there exists a way to evacuate the whole crew for any possible distribution of crew members over the units at the moment when the evacuation is announced. The current evacuation plan might not be acceptable. Manao may demand a number of additional emergency cabins at each end of each tunnel, but he is not allowed to change the location of emergency cabins that are already present in the spaceship. Return the minimum total number of emergency cabins Manao has to add to obtain an acceptable evacuation plan from the current one. If it is impossible, return -1.
Definition
Class:
SpaceshipEvacuation
Method:
additionalCabins
Parameters:
int, vector <string>, int
Returns:
int
Method signature:
int additionalCabins(int N, vector <string> tunnelNetwork, int crewSize)
(be sure your method is public)
Constraints
-
N will be between 2 and 50, inclusive.
-
tunnelNetwork will contain between 1 and 50 elements, inclusive.
-
Each element of tunnelNetwork will contain between 7 and 50 characters, inclusive.
-
Each element of tunnelNetwork will be formatted "A B C D" (quotes for clarity), where A, B, C and D are integers formatted without extra leading zeros.
-
In each element of tunnelNetwork, A and B will be distinct integers between 0 and N-1, inclusive.
-
In each element of tunnelNetwork, C and D will each be between 0 and 100,000, inclusive.
-
The unordered pairs {A,B} in tunnelNetwork will be distinct.
-
Each unit will be a part of at most one canonical cycle.
-
crewSize will be between 1 and 100,000, inclusive.
Examples
0)
3
{"0 1 5 3",
"2 1 0 0"}
5
Returns: 7
Adding 2 cabins to the tunnel between units 0 and 1 from unit 1's side and 5 cabins to the tunnel between units 2 and 1 from unit 2's side ensures that wherever the crew members happen to be when evacuation begins, they will be able to reach unit 0.
1)
3
{"0 1 0 2",
"0 2 0 4"}
5
Returns: 4
An optimal evacuation scheme can be obtained by adding 3 emergency cabins to the 0-1 tunnel and 1 emergency cabin to the 0-2 tunnel.
2)
4
{"0 1 0 6",
"3 2 3 1",
"2 1 0 1",
"3 1 2 2"}
6
Returns: 6
One of the possible ways to obtain an optimal evacuation scheme is to add 5 cabins to the 1-2 tunnel from unit 2's side and 1 cabin to the 2-3 tunnel from unit 3's side.
3)
3
{"0 1 0 0"}
1
Returns: -1
The only crew member has no chance if he is in unit 2 at the moment of evacuation.
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.
