There are several empty containers lined up in a row, and you want to put packages into them. You start with the first container and the first package. Do the following until all the packages are inside containers:
If the current package cannot fit into the current container, skip to step 3. Otherwise, go to the next step.
Put the current package into the current container. Grab the next package, and go back to step 1.
Put the current container aside (you will not put any more packages into that container). Move on to the next container in line, and go back to step 1.
You are given a vector <int> containers, the i-th element of which is the capacity of the i-th container in line, and a vector <int> packages, the i-th element of which is the size of the i-th package. The constraints will guarantee that you will be able to put all the packages into containers using the above procedure. Return the sum of the wasted space in all the containers. The wasted space in a container is its capacity minus the total size of its contents.
Definition
Class:
Containers
Method:
wastedSpace
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int wastedSpace(vector <int> containers, vector <int> packages)
(be sure your method is public)
Notes
-
A set of packages fits into a container if the total size of all the packages in the set does not exceed the capacity of the container.
-
You must use the containers and the packages in the order that they are given. You may not reorder them.
Constraints
-
containers will contain between 1 and 50 elements, inclusive.
-
Each element of containers will be between 1 and 1000, inclusive.
-
packages will contain between 1 and 50 elements, inclusive.
-
Each element of packages will be between 1 and 1000, inclusive.
-
It will be possible to put all the packages inside containers using the method described in the statement.
Examples
0)
{ 5, 5, 5 }
{ 5, 5, 5 }
Returns: 0
Here, we've got 3 packages of size 5 and 3 containers of size 5, so no space will be wasted.
1)
{ 5, 6, 7 }
{ 5, 5, 5 }
Returns: 3
All the packages are of size 5. We will put the first package into the container of size 5, the second package into the container of size 6 and the third into the container of size 7. The overall wasted space will be equal to (5 - 5) + (6 - 5) + (7 - 5) = 3.
2)
{ 2, 3, 5 }
{ 3 }
Returns: 7
Here, we've got only one package of size 3. First, we'll try to put it into the container of size 2, but it won't fit, so we'll put it into the second container, leaving the third untouched. The overall wasted space will be 2 + (3 - 3) + 5 = 7.
3)
{ 3, 4, 5, 6 }
{ 3, 3, 3, 3, 3 }
Returns: 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.
container와 package가 나온다.. package를 모두 담았을때 container의 낭비되는 양을 구하는 문제.. 단 들어온 순서대로 채워져야한다..
아.. 열라 후루꾸로 풀리는 문제.. [모든 container크기 합 ] - [모든 package의 합] 이 답이다..
곰곰히 생각해보니 input 조건이 모든 package는 무조건 다 container에 들어간다고 했으니.. 그게 말이된다..
난 앞에서부터 차례로 simulation했는데 그럴필요가 없는것이었다..
그래서 문제 파악을 잘못하고 막 소팅하고 별짓을 다한애들이 운좋게 다 맞은것이었다..
제길! 이런문제 싫어..!!!
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class Containers {
9 public:
10
11 int wastedSpace(vector <int> containers, vector <int> packages)
12 {
13 int i, a, b;
14 int n = containers.size();
15 int m = packages.size();
16
17 a = b = 0;
18 for (i = 0; i < n; i++)
19 a += containers[i];
20 for (i = 0; i < m; i++)
21 b += packages[i];
22 return a - b;
23 }
24
25 };
[500] DrawingMarbles
Problem Statement
A big box contains marbles of one or more colors. You're given a vector <int> colors, each element of which denotes the number of marbles there are of a particular color. You draw n marbles randomly from the box, leaving each marble outside the box after taking it. Return the probability that all marbles drawn will be the same color.
Definition
Class:
DrawingMarbles
Method:
sameColor
Parameters:
vector <int>, int
Returns:
double
Method signature:
double sameColor(vector <int> colors, int n)
(be sure your method is public)
Notes
-
Every time we draw a marble, all marbles in the box are equally likely to be chosen.
-
A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
-
colors will contain between 1 and 50 elements, inclusive.
-
Each element of colors will be between 1 and 50, inclusive.
-
n will be between 1 and the sum of all elements of colors, inclusive.
Examples
0)
{ 13 }
8
Returns: 1.0
All the marbles are the same color, so obviously all drawn marbles will be the same color too.
1)
{ 5, 7 }
1
Returns: 1.0
2)
{ 5, 6, 7 }
2
Returns: 0.3006535947712418
The probability that the first drawn marble will be of the color 0 is 5 / 18 (there are 5 marbles of color 0 out of 18). If the first drawn marble is of the color 0, then the probability that the second drawn marble will be of the color 0 is 4 / 17 (there are 4 marbles of color 0 left out of 17). So the probability that both drawn marbles will be of the color 0 is (5 / 18) * (4 / 17) = 0.0653594771... . Similarly, the probability that both drawn marbles will be of the color 1 is (6 / 18) * (5 / 17) = 0.0980392156..., and that both drawn marbles will be of the color 2 is (7 / 18) * (6 / 17) = 0.1372549019... . The answer is the sum of these 3 probabilities.
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으로 각 색깔에대한 구슬의 개수가 주어지고, 구슬을 n개 꺼낼 때 모두다 서로 같은 색깔이 확률을 구하는 문제..
단순한 확률문제이다..
첫번째 색깔의 구슬을 다 뽑았을때의 확률 + 두번째 색깔의 구슬을 다 뽑았을때의 확률 + ...
이런식으로 구했다..
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 double fun(int k, int n, int cnt)
7 {
8 int i;
9 double p;
10 p = 1.0;
11 for (i = 0; i < n; i++) {
12 p *= (double)(k-i) / (double)(cnt-i);
13 }
14 return p;
15 }
16
17 class DrawingMarbles {
18 public:
19
20 double sameColor(vector<int> colors, int n) {
21 int size;
22 int i, k, cnt;
23 double p;
24 size = colors.size();
25 cnt = 0;
26 for (i = 0; i < size; i++) {
27 cnt += colors[i];
28 }
29 p = 0;
30 for (i = 0; i < size; i++) {
31 if (colors[i] < n) {
32 continue;
33 }
34 k = colors[i];
35 p += fun(k, n, cnt);
36 }
37 return p;
38 }
39
40 };
[1000] JohnnysPhone
Problem Statement
Little Johnny loves sending text messages to his friends. Recently, he bought himself a cool new phone (an Eric-Sonnicson F198-EX32 with MP3 player, GPS navigation, built-in washing machine, and many other features). Johnny's favorite feature is a T9 dictionary that simplifies typing. Here's how T9 works. The 26 letters of the alphabet are assigned to the phone's keypad as follows:
2 - a, b, c
3 - d, e, f
4 - g, h, i
5 - j, k, l
6 - m, n, o
7 - p, q, r, s
8 - t, u, v
9 - w, x, y, z
The phone also has three special buttons: "Next in dictionary", "New word" and "Space". These are described in the following paragraphs. To type a word, you press the digit buttons corresponding to the letters in the word one by one. Each time you press a digit button, the T9 feature will automatically find the first word in the dictionary that has a prefix matching the digits you've typed so far. It will then display that prefix. For example, if the dictionary is { "bad", "apple" }, and you press the 2 button, the display will read "b" since "bad" is the first word with a prefix of "a", "b" or "c". If there are multiple words in the dictionary that have a matching prefix, you can press the "Next in dictionary" button to display the next prefix. In this example, pressing "Next in dictionary" will cause the display to change to "a" since "apple" is the next word with a matching prefix (note that dictionary entries are not necessarily in alphabetical order). However, if you then type another 2, the display will read "ba" since "bad" is the only word that matches that prefix. If there are no matches in the dictionary for what you've typed so far, nothing will be displayed. Also, if you press "Next in dictionary" more times than there are words with the prefix you typed, nothing will be displayed. If you type something and press "Next in dictionary" one or more times after that, when you type the rest of the word, T9 will search the dictionary from the place it has finished for the last prefix. (See examples for more clarification.) To start a new word, you can press the "Space" button, which will insert a space and let you start typing a new word. Alternatively, you can use the unusual "New word" button, which lets you start a new word without inserting a space, leaving the previous word in whatever state it was in. For example, using the above dictionary, you can press 2, then "New word", then 2, and then 7 to type "bap", a word that does not exist in the dictionary. You can also sometimes use this method to type words that are in the dictionary using fewer button presses. Each time you start typing a new word, T9 will search the dictionary from the beginning. You are given a vector <string> dictionary. Concatenate the elements of dictionary into a single string. This string will be a space separated list of words in the order that they appear in the dictionary. You will be also given a string message, the message that Johhny wants to type. Return the minimum possible number of button presses required to type the message, or -1 if it is impossible to type the message using the given dictionary.
Definition
Class:
JohnnysPhone
Method:
minimizePushes
Parameters:
vector <string>, string
Returns:
int
Method signature:
int minimizePushes(vector <string> dictionary, string message)
(be sure your method is public)
Constraints
-
dictionary will contain between 1 and 50 elements, inclusive.
-
Each element of dictionary will contain between 1 and 50 characters, inclusive.
-
Each element of dictionary will contain only lowercase letters ('a'-'z') and spaces (' ').
-
dictionary, when concatenated, will be a single space separated list of words, without leading or trailing spaces.
-
message will contain between 1 and 50 characters, inclusive.
-
message will contain only lowercase letters ('a'-'z') and spaces (' ').
Examples
0)
{ "age messagd messagd message" }
"message"
Returns: 8
The most obvious way to type "message" is to type the seven digits corresponding to the letters in order: 6, 3, 7, 7, 2, 4, 3. At this point, the display will read "messagd" since that is the first matching prefix in the dictionary. You would then have to press "Next in dictionary" two times to get to "message". That's a total of 9 button presses. A faster way to type "message" is to first type the digits 6, 3, 7, 7. The display will read "mess". Now, press "New word" to start a new word without inserting a space. Type the digits 2, 4, 3. "age" is the only matching prefix in the dictionary for this second word, so the display will read "message". That only requires 8 button presses.
1)
{ "b a c d" }
"abcd dcba "
Returns: 23
2)
{ "a b c" }
"d"
Returns: -1
3)
{ "gajdkwifpcks iclfabc" }
"gajf"
Returns: -1
The digits corresponding to the letters in "gajf" are 4, 2, 5, 3. If we type the first three digits, the display will read "gaj". At this point, there's no way to get "f" as the next letter. If we type 3, the display will change to "gajd". If we then press "Next in dictionary", it will change to "iclf". "gajf" is impossible to type with the given dictionary.
4)
{ "aaa ", "bbb ", "ccc" }
"ccc"
Returns: 5
When we type 2, the display will read "a". Now we can press "Next in dictionary" two times and the display will read "c". Now we should just press 2 two more times to finish our message. Note, that when we're finishing the message, the T9 doesn't search the dictionary from the beginning but stays where it were before (unless we press "New word").
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.
