아.. 이번 match는 지금까지했던 match중 최악이었다.. ㅠ_ㅠ
문제는 가장 쉬웠는데.. 한문제도 못푸는.. 그것도 모잘라서 챌까지 당하고..
요즘 되는일이 하나도 없더니.. 탑코더도 안되네.. 컨디션 최악이다..
덕분에 rating 대폭 하락.. green이 되는 소기의 목적(?)을 달성했다..
다음번엔 그토록 원하던 DIV2를 하겠지만.. 3번 치뤘던 DIV1에서 한문제도 못푼게.. 좀 씁쓸하다..
[250] ChangingSounds
Problem Statement
You are a guitar player and you are going to play a concert. You don't like to play all the songs at the same volume, so you decide to change the volume level of your guitar before each new song. Before the concert begins, you make a list of the number of intervals you will be changing your volume level by before each song. For each volume change, you will decide whether to add that number of intervals to the volume, or substract it.
You are given a vector <int> changeIntervals, the i-th element of which is the number of intervals you will change your volume by before the i-th song. You are also given an int beginLevel, the initial volume of your guitar, and an int maxLevel, the highest volume setting of your guitar. You cannot change the volume of your guitar to a level above maxLevel or below 0 (but exactly 0 is no problem). Return the maximum volume you can use to play the last song. If there is no way to go through the list without exceeding maxLevel or going below 0, return -1.
Definition
Class:
ChangingSounds
Method:
maxFinal
Parameters:
vector <int>, int, int
Returns:
int
Method signature:
int maxFinal(vector <int> changeIntervals, int beginLevel, int maxLevel)
(be sure your method is public)
Constraints
-
changeIntervals will contain between 1 and 50 elements, inclusive.
-
Each element of changeIntervals will be between 1 and maxLevel, inclusive.
-
maxLevel will be between 1 and 1000, inclusive.
-
beginLevel will be between 0 and maxLevel, inclusive.
Examples
0)
{5, 3, 7}
5
10
Returns: 10
First we turn the volume down to 0 (-5), then we turn it up to 3 (+3), and then up to 10 (+7) for the last song.
1)
{15, 2, 9, 10}
8
20
Returns: -1
Adding 15 to 8 or substracting 15 from 8 both give an invalid sound level.
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.
정말 쉬운 문제이다.. 숫자 배열이 주어지고 그 숫자만큼 소리를 높이거나 낮출수있다.. 소리는 maxLevel을 넘어갈 수 없고.. 0 밑으로 떨어져서도 안된다.. 이 조건을 유지하면서 마지막까지 도달했을때 가능한 최대 level을 구하는 문제..
뭐 다양한 방법이 있다.. -_-;;
도저히 틀릴수없다고 생각했는데 챌 당했다.. 나중에 알고보니 초기화 문제였다.. 처음에 문제를 잘못이해하고 잘못 짜다가 나중에 수정했는데.. 미쳐 고치지 못한 한줄이 있었다.. ㅠ_ㅠ 그나저나 찾아낸놈도 대단하다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 #define max(x, y) ((x) > (y) ? (x) : (y))
7
8 int bound;
9 int check[51][1001];
10 int num[51];
11 int n;
12 int fl;
13 int max1;
14
15 void dfs(int u, int cnt)
16 {
17 if (cnt == n) {
18 fl = 1;
19 max1 = max(max1, u);
20 return ;
21 }
22
23
24 if (u - num[cnt] >= 0 && check[cnt+1][u-num[cnt]] == 0) {
25 check[cnt+1][u-num[cnt]] = 1;
26 dfs(u-num[cnt], cnt+1);
27 }
28 if (u + num[cnt] <= bound && check[cnt+1][u+num[cnt]] == 0) {
29 check[cnt+1][u+num[cnt]] = 1;
30 dfs(u+num[cnt], cnt+1);
31 }
32 return ;
33 }
34
35 class ChangingSounds {
36 public:
37
38 int maxFinal(vector<int> changeIntervals, int beginLevel, int maxLevel)
39 {
40 int i;
41
42 n = changeIntervals.size();
43 bound = maxLevel;
44
45 for (i = 0; i < n; i++) {
46 num[i] = changeIntervals[i];
47 }
48
49 fl = 0;
50 max1 = -1;
51 memset(check, 0, sizeof(check));
52 check[0][beginLevel] = 1;
53
54 dfs(beginLevel, 0);
55
56 if (fl)
57 return max1;
58 return -1;
59 }
60
61 };
[500] GuitarConcert
Problem Statement
You are a guitar player and you want to play a concert. Unfortunately, you don't have any good guitars left, so you need to buy some new guitars. You are given a vector <string> guitarNames, the i-th element of which is the name of the i-th guitar that is available for purchase.
You have a list of songs that you would like to play at the concert. Certain songs cannot be played with certain guitars because they will sound weird, so you might not be able to play the entire concert with just one guitar. You are given a vector <string> guitarSongs, where the j-th character of the i-th element is 'Y' if the j-th song can be played on the i-th guitar, and 'N' otherwise.
You want your concert to be as long as possible, so your main goal is to play as many of the songs as possible (you can only play each song at most once). You also want to save your money, so you want to buy the least number of guitars required to play that maximum number of songs. Return a vector <string> containing the names of the guitars you should buy in alphabetical order. If there are multiple possible return values, return the one among them that comes first lexicographically. A vector <string> s1 comes before vector <string> s2 lexicographically if s1[i] comes before s2[i] alphabetically, where i is the first position at which they differ.
Definition
Constraints
-
guitarNames will contain between 1 and 10 elements, inclusive.
-
guitarSongs will contain the same number of elements as guitarNames.
-
Each element of guitarSongs will contain between 1 and 50 characters, inclusive.
-
Each element of guitarSongs will contain the same number of characters.
-
Each element of guitarSongs will contain only the uppercase letters 'Y' or 'N'.
-
Each element of guitarNames will contain between 2 and 50 characters, inclusive.
-
Each element of guitarNames will contain only uppercase letters ('A' - 'Z').
-
All elements of guitarNames will be distinct.
Examples
0)
{"GIBSON","FENDER", "TAYLOR"}
{"YNYYN", "NNNYY", "YYYYY"}
Returns: {"TAYLOR" }
You can play all the songs on the TAYLOR guitar.
1)
{"GIBSON", "CRAFTER", "FENDER", "TAYLOR"}
{"YYYNN", "NNNYY", "YYNNY", "YNNNN"}
Returns: {"CRAFTER", "GIBSON" }
You can play all the songs, but you need 2 guitars to do it.
2)
{"AB", "AA", "BA"}
{"YN", "YN", "NN"}
Returns: {"AA" }
You can only play the first song, so you buy guitar AA because it comes before AB alphabetically.
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.
기타 종류와 각 기타가 연주할 수 있는 노래의 종류가 input으로 들어온다. 최대한 많은 노래를 연주할 때 선택해야하는 최소의 기타 set을 구하는 문제..
vertex cover문제.. 쉬운문제였는데 역시 못풀었다.. 나중에 다른사람 코드를 살펴보고는 황당해했다는.. -_-;
기타의 개수가 50개인줄알고 GG쳤는데.. 나중에 알고보니.. 이런.. ㅠ_ㅠ 나 요즘 왜이러지..
임의로 만들 수 있는 기타 셋 (binary representation으로 0~2^10까지 숫자로 표기)에 대해서 연주할 수 있는 최대 음악을 다 포함하는게 답이다.. 답이 여러개일경우 lexy-smallest로..
코딩하기는 귀찮다.. -_-;;
[1000] LateForConcert
Problem Statement
You are a guitar player and you are giving a concert tonight. Unfortunately, you are running a bit late, and you still need to travel across town to get to the concert hall. You will drive as fast as possible (above the speed limit) and you are willing to drive through red lights at the risk of getting fined. However, you do not want to arrive early because you don't like the artist playing before you. Your goal is to get to the concert hall exactly on time.
The city is a rectangular grid of squares described by the String[] cityMap. The j-th character of the i-th element of cityMap is the square at row i, column j. Each square is one of the following:
X: A house. You cannot enter this square.
.: A safe road. You can drive here safely without ever getting a speeding ticket.
Y: Your starting location. After time = 0, this becomes a safe road.
C: The concert hall. As soon as you enter this square, you are at your final destination and you cannot leave.
T: A traffic light. See below for details.
S: A speed trap. You will get fined speedingTicket dollars every time you enter a square containing a speed trap.
You are given an int timeLeft, the number of seconds you have left until your concert starts. At time 0, you are at your starting location. At the speed you are driving, it takes you exactly one second to move to any of the 4 adjacent squares. At each second, you must move to an adjacent square unless you are at a traffic light. You are never allowed to directly go back to the immediately previous square of your path. If you are currently at a traffic light, you have two options: make a move during the upcoming second (like you would from any other square), or stay at the traffic light for exactly one second before making your next move. If you stay at the traffic light for one second, you are guaranteed to not get fined. Otherwise, you have a 70% chance of getting fined redLight dollars.
Determine the route that will take you to the concert hall in exactly timeLeft seconds. If there are multiple such routes, choose the one that minimizes your total expected fine. Return your total expected fine, or -1 if there is no way to get to the concert hall exactly on time.
Definition
Class:
LateForConcert
Method:
bestRoute
Parameters:
String[], int, double, double
Returns:
double
Method signature:
double bestRoute(String[] cityMap, int timeLeft, double speedingTicket, double redLight)
(be sure your method is public)
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
cityMap will contain between 1 and 50 elements, inclusive.
-
Each element of cityMap will contain between 1 and 50 characters, inclusive.
-
Each element of cityMap will contain the same number of characters.
-
Each character of cityMap will be one of the following: 'X', '.', 'Y', 'C', 'T' or 'S'.
-
Exactly one character in cityMap will be 'Y'.
-
Exactly one character in cityMap will be 'C'.
-
timeLeft will be between 1 and 100, inclusive.
-
speedingTicket will be between 1.0 and 1000.0, inclusive.
-
redLight will be between 1.0 and 1000.0, inclusive.
Examples
0)
{"XXXXXXXX",
"XY...S.X",
"XXXXXX.X",
"C..S.TT."}
14
60
93
Returns: 185.1
If you wait for one of the traffic lights, it will take 14 seconds, and your expected total fine will be speedingTicket + speedingTicket + 0.7 * redLight.
1)
{"XX..XX",
"Y....C"}
9
52
874
Returns: 0.0
You can use the 2x2 square to spend your time so you don't have to see the other artist.
2)
{"C.......",
"SXXSXXX.",
"TSSTY..."}
12
1.23456789
123.456789
Returns: 0.0
The shortest route is not always the best!
4)
{"Y..",
"...",
"..C"}
3
1.0
1.0
Returns: -1.0
The concert hall is too far, so you don't have enough time to reach it.
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.
이문제는 조금 읽어보다가.. 중간에 좀 짜증나는거같아서 때려쳤다.. 뭐 그렇게 조건이 많은지.. -_-;
