어제 열렸던 TCO10 Q2
600등까지가 다음 라운드로 진출하는데 어처구니없게도 613 등으로 실격됐다.. ㅠ_ㅠ
25일 아침에 마지막 패자부활전이 남아있지만.. 그걸 참가하려면 휴가를 써야한다..
나이를 먹다보니 점점 순발력이 떨어지는것 같다..
250 을 조금만 더 빨리풀었으면 됐는데.. 흑흑.. ㅠ_ㅠ;
Level1 - JingleRingle
Problem Statement
Your favorite online game operates on two types of currency - jingles and ringles. They are obtained from different sources, and players can trade them in an exchange market. Each individual trade is the result of an agreement between two people - a seller who wants to sell 1 jingle and a buyer who wants to buy it for an agreed upon integer price of X ringles. Each trade is executed as follows:
The buyer pays X ringles to the seller.
The seller pays 1 jingle to the buyer.
The seller pays a tax of floor((X * tax) / 100) ringles to the game host. The buyer pays no taxes.
You have a lot of ringles and no jingles, and you want to perform several trades to make a profit. The exchange market is described as two sets of offers. Offers from buyers are given in the vector <int> buyOffers, where each element is the price that some buyer is willing to pay for 1 jingle. Offers from sellers are given in the vector <int> sellOffers, where each element is the price some seller wants to receive for 1 jingle. You are also given the tax rate tax. Return the maximum profit in ringles you can get after accepting some of these offers and paying the applicable taxes. Note that you can accept as many offers from sellers as you wish, but you can only accept offers from buyers if you already have enough jingles to sell. If you can't make a positive profit, return 0.
Definition
Class:
JingleRingle
Method:
profit
Parameters:
vector <int>, vector <int>, int
Returns:
int
Method signature:
int profit(vector <int> buyOffers, vector <int> sellOffers, int tax)
(be sure your method is public)
Notes
-
floor(X) is the largest integer which is less than or equal to X.
-
Assume that you have enough ringles to accept all offers from sellers.
Constraints
-
buyOffers and sellOffers will each contain between 0 and 50 elements, inclusive.
-
Each element of buyOffers and sellOffers will be between 100 and 10000, inclusive.
-
tax will be between 0 and 20, inclusive.
Examples
0)
{1000, 1024}
{990, 1011}
0
Returns: 34
You can accept offer 0 from sellOffers and buy 1 jingle for 990 ringles, and then accept offer 1 from buyOffers and sell this jingle for 1024 ringles. There are no taxes here, so your profit is 34 ringles.
1)
{1000, 1001, 1002}
{980, 981, 982}
2
Returns: 2
Accepting any of buyOffers makes you pay 20 ringles in taxes. If you accept offer 0 from sellOffers and offer 2 from buyOffers, you can get a profit of 2 ringles.
2)
{100, 120, 140}
{150, 170, 200}
15
Returns: 0
All offers from sellOffers are higher than offers from buyOffers, so no profitable trades can be done.
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.
사고자 하는 가격, 팔고자 하는 가격이 주어질때.. 이를 이용해서 최대 차익을 얼마나 낼 수 있는지..
greedy 로 풀리는 문제이다..
buy 는 역순으로.. sell 은 정방향으로 매치시켜나가다가 더이상 수익을 낼 수 없으면 break
greedy 로 하면 안되는 경우가 있는지 한참 생각하다가 시간을 허비했다..
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 int& a, const int& b)
13 {
14 return b < a;
15 }
16
17 class JingleRingle {
18 public:
19
20 int profit(vector <int> buy, vector <int> sell, int tax)
21 {
22 int n, m;
23 int dif, t;
24 int i;
25 int sum;
26 n = buy.size();
27 m = sell.size();
28
29 if (n == 0 || m == 0)
30 return 0;
31
32 sort(buy.begin(), buy.end(), comp);
33 sort(sell.begin(), sell.end());
34
35 sum = 0;
36
37 for (i = 0; i < min(n, m); i++) {
38 dif = buy[i] - sell[i];
39 t = (int)(((double)buy[i] * tax) / 100.0 + EPS);
40 if (dif - t <= 0)
41 break;
42 sum += dif - t;
43 }
44
45 return sum;
46 }
47
48 };
Level2 - FuzzyLife
Problem Statement
The Game of Life is a simulation which takes an initial state and shows its evolution over time. The simulation takes place on an infinite 2-dimensional grid of cells, where each cell is either live or dead. Each cell has exactly 8 neighbors (2 horizontal, 2 vertical, and 4 diagonal). Once the initial layout of live and dead cells is known, the evolution of the grid happens step by step. On each step, the state of the cells changes in the following way:
Each live cell with less than 2 or more than 3 live neighbors becomes dead.
Each dead cell with exactly 3 live neighbors becomes live.
All other cells remain the same.
All cells change their states simultaneously, so for each cell, the number of live neighbors is calculated before any changes are performed. You are given a vector <string> grid which describes the initial layout of cells on a rectangular section of the grid. Unlike the classic game, in which the initial states of all the cells are known, grid contains cells of three types: live, dead and unknown, denoted by '1' (one), '0' (zero) and '?', respectively. The j-th character of the i-th element of grid describes the cell at row i, column j of the rectangular section. No cell will have more than one neighbor of type '?'. All cells outside of the area described by grid are initially dead. Your task is to replace the unknown cells in the initial layout with live or dead cells in such a way that the total number of live cells after one step is maximized. Return the maximal possible number of live cells after one step.
Definition
Class:
FuzzyLife
Method:
survivingCells
Parameters:
vector <string>
Returns:
int
Method signature:
int survivingCells(vector <string> grid)
(be sure your method is public)
Constraints
-
grid will contain between 2 and 50 elements, inclusive.
-
Each element of grid will contain between 2 and 50 characters, inclusive.
-
All elements of grid will contain the same number of characters.
-
Each character in grid will be '0', '1' or '?'.
-
No cell will have more than one neighboring cell of type '?'.
Examples
0)
{"011",
"0?1",
"100"}
Returns: 5
There is only one unknown cell on the board, and two choices of filling it:
011 011 011 011
001 -> 001 or 011 -> 101
100 000 100 010
The first choice produces 3 live cells, and the second one produces 5 live cells.
1)
{"101",
"0?0",
"101"}
Returns: 4
Again only one unknown cell and two choices:
101 000 101 010
000 -> 000 or 010 -> 101
101 000 101 010
2)
{"11",
"11"}
Returns: 4
It is possible to have no unknown cells.
3)
{"111",
"1?1",
"111"}
Returns: 8
The number of live cells doesn't depend on the choice of the unknown cell. Remember that the cells outside of the described part of the grid can turn live as well.
4)
{"?11?",
"0110",
"1001",
"?11?"}
Returns: 12
5)
{"00100",
"01010",
"10?01",
"01010",
"00100"}
Returns: 12
Choosing '0' as the value of an unknown cell is sometimes better.
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.
0 과 1 로 되어있는 grid 가 매 단계마다 변하는데..
neighbor 중에 1이 3 개면 1로 되고 2 이면 상태 유지 그 이외의 경우면 0 이 된다..
? 를 적절히 바꿔서 1단계 이후에 최대 1의 개수 구하기
to be updated..
Level3 - HandlesSpelling
Problem Statement
You have recently gained access to the badge printing machine used by TopCoder to print name badges for their tournaments. Each badge produced by the machine contains the handle of a TopCoder member, and you can print any number of badges for each handle from a predefined list. You decide to play a game using the machine. Given an arbitrary sentence, you want to spell it using only name badges that you print with the machine in some optimal way. The rules of the game are as follows. First, you remove all spaces and punctuation from the sentence. Then, you try to spell out the resulting string by printing out name badges and arranging them in a single row. Each badge you use must contain a handle which is a contiguous substring of the string. Badges can touch but not overlap. Letters in the string which are not represented by the badges are considered "uncovered". For example, consider the case where only the following TopCoder members exist: {"E", "HE", "L"}. If you want to spell the sentence "HELLO", you might try to do it by printing out one "E" badge and two "L" badges. However, "H" and "O" would then be uncovered, and you wouldn't be able to add an "HE" badge because it would overlap with the "E". A better way would be to print out one "HE" badge and two "L" badges. Then, only the "O" would be uncovered. You want to create the best possible arrangement of badges, so you've come up with the following scoring system. Define A as the length of the longest contiguous sequence of letters covered with the badges, and B as the number of letters that are uncovered. If all letters are uncovered, A is equal to 0. The score of the arrangement is A^2-B. You are given a vector <string> parts. Concatenate the elements of parts to obtain the original sentence (with spaces and punctuation already removed). The handles on your name badges are given to you in the vector <string> badges. Return the maximal possible score you can obtain using the given badges.
Definition
Class:
HandlesSpelling
Method:
spellIt
Parameters:
vector <string>, vector <string>
Returns:
int
Method signature:
int spellIt(vector <string> parts, vector <string> badges)
(be sure your method is public)
Constraints
-
parts will contain between 1 and 20 elements, inclusive.
-
Each element of parts will contain between 1 and 50 characters, inclusive.
-
badges will contain between 1 and 50 elements, inclusive.
-
Each element of badges will contain between 1 and 50 characters, inclusive.
-
parts and badges will contain only uppercase letters ('A'-'Z').
-
All elements of badges will be distinct.
Examples
0)
{"HELLO"}
{"E","HE","L"}
Returns: 15
Example from the problem statement.
1)
{"ALGORITHM","QUALIFICATION","ROUND","TWO"}
{"AL", "CAT", "GOR", "IFI", "ION", "ROUND", "T"}
Returns: 282
The optimal spelling is "AL"-"GOR"-I-"T"-HMQU-"AL"-"IFI"-"CAT"-"ION"-"ROUND"-"T"-WO. In this spelling, A=17 and B=7.
2)
{"GOOD","LUCK"}
{"GOODLUCKBJ","G","L"}
Returns: -5
The handle used has to be a proper substring of the sentence spelled, and not vice versa. In this case at most one letter in a row can be covered with badges, and 6 letters are left uncovered, so the total score is negative.
3)
{"ANDDOHAVEFUN"}
{"HAV"}
Returns: 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.
주어진 단어들만 이용해서 문장을 최대한 많이 커버해야하는데.. (단어는 중복사용 가능, overlap 불가능)
score 는 (covered 된 가장 긴 substring)^2 - (# of uncovered letters) 가 된다.. score 를 최대화 하기..
