TopCoder SRM 399 Div 1

아침 10시에 열린 매치.. 결과는 역시.. -_-;; 흠.. 250점짜리 쉬운문제였는데 너무 안일하게 생각해서.. 결국 system fail..;; 아쉽군.. 쩝.. 그런데 0점을 기록했는데도 불구하고 rating은 소폭 올랐다.. 음.. 이런경우도 있군..

방 9등 전체 220등..

[250] AvoidingProduct

Problem Statement
     
You are given a set A of integers and a positive integer n. You must find positive integers x, y and z such that their product is as close to n as possible (minimize |n - x * y * z|), and none of them belongs to A. If there are several such triples, find the one with the smallest x. If there are still several such triples, minimize y. If there is still a tie, minimize z.
You are given the elements of A as a vector <int> a. Return a vector <int> with exactly three elements: x, y and z, in this order.
Definition
   
Class:
AvoidingProduct
Method:
getTriple
Parameters:
vector <int>, int
Returns:
vector <int>
Method signature:
vector <int> getTriple(vector <int> a, int n)
(be sure your method is public)
   
 
Constraints
-
a will contain between 0 and 50 elements, inclusive.
-
Each element of a will be between 1 and 1000, inclusive.
-
All elements of a will be distinct.
-
n will be between 1 and 1000, inclusive.
Examples
0)
 
   
{2,4}
4
Returns: {1, 1, 3 }
You can get 3=1*1*3 and 5=1*1*5. 3 is better.
1)
 
   
{1}
10
Returns: {2, 2, 2 }
 
2)
 
   
{1,2}
10
Returns: {3, 3, 3 }
 
3)
 
   
{1,3}
12
Returns: {2, 2, 2 }
 
4)
 
   
{1,3}
13
Returns: {2, 2, 4 }
 
5)
 
   
{1,15}
90
Returns: {2, 5, 9 }
 
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.

자연수로 이루어진 set과 n 이 주어지고 |n - (x*y*z)| 이 최소가 되는 x, y, z를 찾는 문제.. 단 x, y, z은 주어진 set에 있는 수일 수 없다..


to be updated..




[500] BinarySum

Problem Statement
     
You are given three integers: a, b and c. Convert each of them into their binary representations with no leading zeroes. Let x be the number of binary digits in the longest of the three. Add leading zeroes to the others until all of them have exactly x digits.
Transform a, b and c into a', b' and c', such that a'+b'=c', by optionally reordering the digits within each number. Leading zeroes are allowed. If there are several ways to do this, use the one that minimizes c'.
For example, let a = 7, b = 6 and c = 9. In binary notation, a = 111, b = 110 and c = 1001. We add leading zeroes to a and b so that all of them have exactly four digits: a = 0111, b = 0110, c = 1001. Now, if we reorder the digits within each number to get a' = 0111, b' = 0011 and c' = 1010, we satisfy a' + b' = c' (7 + 3 = 10). There is another way to do this as well (7 + 5 = 12), but this is the way that minimizes c'.
You are given ints a, b and c. Return the minimal possible value of c'. If there is no solution, return -1.
Definition
   
Class:
BinarySum
Method:
rearrange
Parameters:
int, int, int
Returns:
int
Method signature:
int rearrange(int a, int b, int c)
(be sure your method is public)
   
 
Constraints
-
a, b and c will each be between 1 and 2^30, inclusive.
Examples
0)
 
   
7
6
9
Returns: 10
The example from the problem statement.
1)
 
   
1
1
2
Returns: 2
 
2)
 
   
1
1
4
Returns: 2
Leading zeroes are allowed.
3)
 
   
3
3
9
Returns: 6
 
4)
 
   
1
1
1
Returns: -1
 
5)
 
   
32517565
204650420
4096
Returns: -1
 
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.

a, b, c 가 주어질 때, a, b, c를 2진수로 나타내어 bit를 reordering 할 수 있다.. (심지어 leading zero도 가능하다) 이렇게 만들어진 수를 각각 a', b', c' 라고 할 때, a' + b' = c' 를 만족하는 가장 작은 c' 를 구하기..

match editorial을 참고하여 풀었다..~

이 문제는 DP로 풀 수 있는데..

dp[n][a][b][c][carry] = n자리까지 a개의 1, b개의 1, c개의 1을 사용하여 만들 수 있는 가장 작은 수

이런식으로 정의하면..

a의 다음 bit가 0 일 경우, 1일경우, b의 다음 bit가 0일 경우, 1일 경우.. 로 나눠서

다음과 같은 점화식을 만들 수 있다..

dp[n][a][b][c][carry] = min(

2 * dp[n-1][a-1][b][c-(carry+1)%2][(carry+1)/2] + (carry+1)%2,

2 * dp[n-1][a][b-1][c-(carry+1)%2][(carry+1)/2] + (carry+1)%2,

..

..

)

  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 999999999999999999LL

 10 #define LL long long

 11

 12 LL memo[32][32][32][32][2];

 13

 14 int get_len(LL a)

 15 {

 16     int cnt;

 17     cnt = 0;

 18     while (a) {

 19         cnt++;

 20         a >>= 1;

 21     }

 22     return cnt;

 23 }

 24

 25 int get_bit(LL a)

 26 {

 27     int cnt;

 28     cnt = 0;

 29     while (a) {

 30         if (a & 1)

 31             cnt++;

 32         a >>= 1;

 33     }

 34     return cnt;

 35 }

 36

 37 LL recur(int n, int a, int b, int c, int carry)

 38 {

 39     int x, y, z, new_carry;

 40     LL res, temp;

 41     if (a < 0 || b < 0 || c < 0)

 42         return INF;

 43     if (memo[n][a][b][c][carry] != -1)

 44         return memo[n][a][b][c][carry];

 45     res = INF;

 46     if (n == 0) {

 47         if (a == 0 && b == 0 && c == 0 && carry == 0)

 48             res = 0;

 49         else

 50             res = INF;

 51         return memo[n][a][b][c][carry] = res;

 52     }

 53     for (x = 0; x < 2; x++) {

 54         for (y = 0; y < 2; y++) {

 55             z = x + y + carry;

 56             new_carry = 0;

 57             if (z >= 2) {

 58                 z -= 2;

 59                 new_carry++;

 60             }

 61             temp = 2 * recur(n-1, a-x, b-y, c-z, new_carry) + z;

 62             res = min(res, temp);

 63         }

 64     }

 65     return memo[n][a][b][c][carry] = res;

 66 }

 67

 68 class BinarySum {

 69 public:

 70

 71 int rearrange(int a, int b, int c)

 72 {

 73     int n;

 74     LL res;

 75     n = max(get_len(a), max(get_len(b), get_len(c)));

 76     memset(memo, -1, sizeof(memo));

 77     res = recur(n, get_bit(a), get_bit(b), get_bit(c), 0);

 78     if (res == INF)

 79         return -1;

 80     return (int)res;

 81 }

 82

 83 };

[1000] DancingParty

Problem Statement
     
You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.
In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like.
You are given a vector <string> likes. The j-th character of likes[i] is 'Y' if the i-th boy and the j-th girl like each other, and 'N' if they don't. Return the maximum number of rounds you can organize.
Definition
   
Class:
DancingParty
Method:
maxDances
Parameters:
vector <string>, int
Returns:
int
Method signature:
int maxDances(vector <string> likes, int k)
(be sure your method is public)
   
 
Constraints
-
likes will contain between 1 and 50 elements, inclusive.
-
Each element of likes will contain exactly n characters, where n is the number of elements in likes.
-
Each element of likes will contain only the characters 'Y' and 'N'.
-
k will be between 0 and 50, inclusive.
Examples
0)
 
   
{"YYY", "YYY", "YYY"}
0
Returns: 3
Every boy likes every girl, so you can organize 3 rounds.
1)
 
   
{"YYY", "YYN", "YNY"}
0
Returns: 2
For example, you can have one round with pairs 1-2, 2-1 and 3-3 and one round with pairs 1-3, 2-2 and 3-1.
2)
 
   
{"YN", "YN"}
0
Returns: 0
The second girl doesn't like anybody.
3)
 
   
{"YN", "YN"}
1
Returns: 1
The second girl doesn't like anybody again, but this time she agrees to dance with someone she doesn't like once.
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..