정말 오래간만에 했던 SRM 결과는 참담.. -_- 뭐 굳이 변명을하자면.. 아침 10시라 잠이 좀 덜깼다는거..;; easy 부터 코딩 짜증나는게 나오면서.. 괜히 하기가 싫어졌다.. medium 문제가 재밌어보였는데.. 결국 해법을 못찾았다.. 막판에 다시 easy를 잡고 한문제라도 풀어보려고했지만.. compile error의 압박으로..;; topcoder는 C유저한테 너무 불리한거 아닌가..;;
한번에 300점이나 떨어지다니.. -_- DIV1 안해!!
[300] Paintball
Problem Statement
For his birthday, Bart received the brand new video game "Paintball!". In this game, a person plays on teams over the Internet against various competitors, attempting to hit their opponents with paint balls. Each player earns a point each time that they "splatter" an opponent with a paintball, and lose a point for each time they get "splattered". Due to the way that the game is played, it is also possible to accidentally splatter yourself or a teammate. In that case, the shooter loses a point, and the person who was splattered (if not the shooter) does not lose any points. A team's score is simply the sum of the scores of its players.
Although Bart loves the game, he is disappointed that the game does not provide a leaderboard during gameplay. However, it does provide the list of players, formatted as "NAME TEAM" (where NAME is the player's name, and TEAM is his team), and a series of messages, each formatted as "NAME1 SPLATTERED NAME2" (all quotes for clarity), where NAME1 indicates the name of the person who shot the paintball, and NAME2 indicates the name of the person who got splattered. Bart would like to have an updated scoreboard, and that is where you come in.
All teams will receive a rank number from 1 to M (the total number of teams), based on the team scores (with 1 corresponding to the highest score). If multiple teams have the same score, then the team with the name that comes first alphabetically will receive a lower rank number. For each team (in order from 1 to M), its leaderboard entry will be formatted as follows:
The first line will be "TEAM SCORE" (quotes for clarity), where TEAM is the team name, and SCORE is the team score (with no extra leading zeroes).
Let N be the number of players on the team. Assign rank numbers to the N players from 1 to N, giving a lower rank number to a higher score. If multiple players have the same score, assign the player whose name comes first alphabetically to the lower rank number.
From the player with rank 1 to rank N, output a line with 2 spaces, the player's name, a single space, and then the player's score (with no extra leading zeroes).
Thus, if player A from team RED splatters player B from team BLUE (and they are the only players in the game), the leaderboard will be:
RED 1
A 1
BLUE -1
B -1
You are to generate the leaderboard and return it.
Definition
Notes
-
A SCORE of 0 should be output as 0, not as -0.
Constraints
-
players will contain between 1 and 50 elements, inclusive.
-
Each element of players will contain between 3 and 50 characters, inclusive.
-
Each element of players will be formatted as "NAME TEAM" (quotes for clarity).
-
In each element of players, NAME will consist of uppercase characters ('A'-'Z') and will contain at least 1 character.
-
There will be no duplicate NAMEs in players.
-
In each element of players, TEAM will consist of uppercase characters ('A'-'Z') and will contain at least 1 character.
-
messages will contain between 1 and 50 elements, inclusive.
-
Each element of messages will contain between 14 and 50 characters, inclusive.
-
Each element of messages will be formatted as described in the problem statement.
-
In each element of messages, NAME1 and NAME2 will be NAMEs found in players.
Examples
0)
{"A RED", "B BLUE"}
{"A SPLATTERED B"}
Returns: {"RED 1", " A 1", "BLUE -1", " B -1" }
The example from the statement.
1)
{"DR COHO", "ST COHO", "PE COHO"}
{"DR SPLATTERED ST",
"ST SPLATTERED PE"}
Returns: {"COHO -2", " PE 0", " DR -1", " ST -1" }
Don't shoot your teammates!
4)
{"A B", "AA AA", "AAA AAA"}
{"A SPLATTERED AAA", "A SPLATTERED AAA", "A SPLATTERED AAA",
"AA SPLATTERED AAA", "AA SPLATTERED AAA"}
Returns: {"B 3", " A 3", "AA 2", " AA 2", "AAA -5", " AAA -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.
easy 문제는..
paintball로 맞추는 게임을 하는데.. 각 팀과 팀에 속한 멤버 정보가 들어오고.. 상대방을 맞추면 개인점수가 올라가고 그에따라 팀점수도 올라간다.. 맞는 사람은 역시 개인 점수가 떨어지고 팀점수가 떨어진다.. 단, 같은편을 맞춘경우는 감점을 당한다..
팀순위 순으로 sort하고.. 각 팀 안에서는 member순으로 sort하는 문제..
시간이 5분만 더있었으면 submit은 할수있었는데.. -_-;
[500] PowerPlants
Problem Statement
Our hero, Homer, has just woken to a horrible discovery! While sleeping at work, several of the power plants in the state have lost power. Even worse, his boss is on the way to his office, and if he doesn't have the situation fixed in time, he'll be fired. He's called you, desperately asking for help, and you've agreed to help him figure things out.
Homer has given you connectionCost, in which the j-th character of the i-th element indicates the cost to restart power plant j using power plant i; a digit ('0'-'9') stands for a cost of 0-9, while an uppercase letter ('A'-'Z') stands for a cost of 10-35. Homer has also given you the plantList, in which the i-th character indicates whether the i-th plant is still working after the power outage; a 'Y' indicates that it has power, otherwise, it is an 'N'. A plant can only be used to power another plant if it currently has power. Finally, he gives you numPlants, the minimum number of plants that need to be powered to save Homer's job. You need to return the minimum cost needed to power at least numPlants plants.
Definition
Class:
PowerPlants
Method:
minCost
Parameters:
String[], String, int
Returns:
int
Method signature:
int minCost(String[] connectionCost, String plantList, int numPlants)
(be sure your method is public)
Constraints
-
connectionCost will contain exactly N elements, where N is between 1 and 16, inclusive.
-
Each element of connectionCost will contain exactly N characters.
-
Each character of connectionCost will be a digit ('0'-'9') or uppercase letter ('A'-'Z').
-
plantList will contain exactly N characters.
-
Each character of plantList will be 'Y' or 'N'.
-
At least one character of plantList will be 'Y'.
-
numPlants will be between 0 and N, inclusive.
Examples
0)
{"024",
"203",
"430"}
"YNN"
3
Returns: 5
The cheapest way is to restart plant 1 using plant 0. Once plant 1 is active, you can then use it to restart plant 2.
1)
{"0AB",
"A0C",
"CD0"}
"YNN"
3
Returns: 21
Here we can use plant 0 to restart both of the others.
2)
{"01","20"}
"YN"
2
Returns: 1
The cost to restart plant 0 using plant 1 may differ from the cost of restarting plant 1 using plant 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.
두번째 문제는 정전이 된 발전소를 모두 살리는 최소 비용을 구하는 문제이다.
input으로 2차원 배열이 들어오는데 i행 j열이 i번 발전소로 j번 발전소를 살리는데 드는 비용이다..
이어서 들어오는 string이 'Y'는 현재 동작하는 발전소 'N'는 현재 정전된 발전소라는 의미..
완전 난감.. -_-
TSP인거 같기도하고.. 생각해보니 아닌거같기도 하고.. 그냥 backtracking으로 시도해볼까 하다가 그냥 포기..;
현재 발전소 상태를 bit로 나타내서 그 상태까지의 최소비용을 저장해나가는 방식으로 어떻게 recursion, dp 등을 샤바샤바하면 될것같기도하다.. 다른사람 코드를 보면서 나중에 더 생각해봐야겠다..
문제를 잘못 이해했다..;;;; 발전소를 모두 살리는것이 아니라 numPlants개만 살아있으면 된다.. 따라서 처음 주어진 string에서 'Y'가 numPlants개 이상 있으면 답은 0 이다..
별다른 알고리즘이 없었다.. -_-;; 그냥 backtracking + memorization 문제였다.. 이렇게 쉬운문제를 못풀다니.. 아.. 한심스럽다.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <cctype>
7 using namespace std;
8 #define INF 999999999
9 #define min(x, y) ((x) > (y) ? (y) : (x))
10
11 class PowerPlants {
12 public:
13
14 int cost[20][20];
15 int memo[1000000];
16 int n;
17 char p_stat[20];
18
19 int dfs(int mask, int cnt)
20 {
21 int i, j, min1;
22
23 if (memo[mask] >= 0) {
24 return memo[mask];
25 }
26 if (cnt <= 0) {
27 memo[mask] = 0;
28 return 0;
29 }
30
31 min1 = INF;
32 for (i = 0; i < n; i++) {
33 if (mask & (1 << i)) {
34 for (j = 0; j < n; j++) {
35 if ((mask & (1<<j)) == 0) {
36 min1 = min(min1, dfs(mask | (1 << j), cnt-1) + cost[i][j]);
37 }
38 }
39 }
40 }
41 return (memo[mask] = min1);
42 }
43
44 int minCost(vector<string> connectionCost, string plantList, int numPlants)
45 {
46 int i, j;
47 int mask, cnt;
48 char buf[100];
49
50 n = connectionCost.size();
51 for (i = 0; i < n; i++) {
52 strcpy(buf, connectionCost[i].c_str());
53 for (j = 0; j < n; j++) {
54 if (isdigit(buf[j])) {
55 cost[i][j] = buf[j] - '0';
56 }
57 else {
58 cost[i][j] = buf[j] - 'A' + 10;
59 }
60 }
61 }
62
63 strcpy(p_stat, plantList.c_str());
64 mask = cnt = 0;
65 for (i = 0; i < n; i++) {
66 if (p_stat[i] == 'Y') {
67 mask |= (1 << i);
68 cnt++;
69 }
70 }
71 memset(memo, -1, sizeof(memo));
72 return dfs(mask, numPlants-cnt);
73 }
74
75
76 };
[1000] YankeeSwap
Problem Statement
Little Lisa has been invited to a holiday party with her friends. So that everyone receives a gift, the host of the party has decided to give presents through a "Yankee swap".
In this version of a Yankee swap (which may differ from the version that you are used to), each person begins holding a present; the first person (indexed from 1) holds present 'A', the second person holds present 'B', etc. Each guest in turn (starting with guest 1 and ending with guest N) decides whether or not he wants to swap presents. If he decides to swap, he chooses a person to swap with, and the chosen person cannot reject the swap. When every person has had a turn, the Yankee swap is over, and each person leaves with the gift they are holding.
For example, one way that the party (with 3 people) could proceed is as follows:
"ABC" --> Person 1 swaps with person 2 --> "BAC"
"BAC" --> Person 2 does not swap --> "BAC"
"BAC" --> Person 3 swaps with person 2 --> "BCA"
In the above example, person 1 leaves with present B, person 2 leaves with present C, and person 3 leaves with present A.
The guests at the party have given you their preferences, where the i-th element corresponds to the preference list of the i-th guest. If a guest ends up with the gift in the j-th position of his preference list, he will have an unhappiness of j. Each guest knows the preferences of all other guests. Each guest will act optimally to minimize his own unhappiness, and knows all other guests will do the same. If there are multiple ways for a guest to minimize his own unhappiness, he will choose not to swap at all if possible; if there are still multiple ways, he will choose to swap with the guest with the lowest index.
Return a String, the i-th character of which corresponds to the turn of the i-th person. If the i-th person did not swap in his turn, the i-th character of the result must be equal to '-'. If he did swap with the k-th person, the i-th character of the result must be equal to the k-th lowercase letter (so, 'a' corresponds to swapping with the first person, 'b' to the second and so on).
Definition
Class:
YankeeSwap
Method:
sequenceOfSwaps
Parameters:
String[]
Returns:
String
Method signature:
String sequenceOfSwaps(String[] preferences)
(be sure your method is public)
Constraints
-
preferences will contain N elements, where N is between 1 and 20 inclusive.
-
Each element of preferences will be a permutation of the first N uppercase letters of the alphabet.
Examples
0)
{"BAC",
"ACB",
"BCA"}
Returns: "-aa"
This swap will proceed as follows: 1) Guest 1 keeps his present. 2) Guest 2 swaps with Guest 1. 3) Guest 3 swaps with Guest 1.
1)
{"ABC",
"BCA",
"CAB"}
Returns: "---"
In this scenario, everyone keeps their own gift.
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.
한번에 300점이나 떨어지다니.. -_- DIV1 안해!!