TopCoder SRM 387 Div1

오랜만에 Div1에서 했다.. 공포의 아침 11시 타임..;; 게다가 첫번째 문제도 250이 아닌 300 .. -_-;; 분위기는 완전 Div2 복귀였는데.. 그럭저럭 선방해서 rating도 올리고 Div1을 유지했다..

방 11등 전체 287등..

녹색과 회색들만보다가 파랑과 노랭이들이 있으니 좀 어색하군..;; 왠지 압도당하는 느낌.. ㄷㄷㄷ



[300] MarblesRegroupingEasy

Problem Statement
     
John is a marble collector. He keeps his marbles in boxes. He also likes to keep things in order.
One day, his younger brother was playing with the marbles. After he was done, he put all the marbles back in boxes, but he did it randomly, so certain boxes might now contain marbles of different colors. John wants him to regroup the marbles so that the grouping satisfies the following restrictions:
At most one box, called the joker box, may contain marbles of different colors. We can choose any box as a joker box.
Every box except the joker box must either be empty or only contain marbles of the same color.
All marbles of the same color, except those in the joker box, must be in the same box. It's possible that all marbles of the same color are in the joker box.
You are given a vector <string> boxes, where the j-th digit of the i-th element is the number of marbles of color j in the i-th box. Return the minimal number of moves necessary to regroup the marbles, where each move consists of taking any number of marbles from one box (not necessarily of the same color) and putting them into another.
Definition
   
Class:
MarblesRegroupingEasy
Method:
minMoves
Parameters:
vector <string>
Returns:
int
Method signature:
int minMoves(vector <string> boxes)
(be sure your method is public)
   
 
Constraints
-
boxes will contain between 1 and 50 elements, inclusive.
-
Each element of boxes will contain between 1 and 50 characters, inclusive.
-
All elements of boxes will contain the same number of characters.
-
Each element of boxes will contain only digits ('0'-'9').
Examples
0)
 
   
{"20",
 "11"}
Returns: 0
Let box 1 be the joker box. All marbles of color 0, except those in the joker box, are in box 0. Box 0 contain only marbles of the color 0. So, all restrictions are already satisfied.
1)
 
   
{"11",
 "11",
 "10"}
Returns: 1
There are several possible solutions:
Move all marbles from box 0 into box 1. Box 1 is the joker box.
Move all marbles from box 1 into box 0. Box 0 is the joker box.
Move the marble of color 0 from box 0 into box 1 or 2. Box 1 is the joker box.
Move the marble of color 0 from box 1 into box 0 or 2. Box 0 is the joker box.
2)
 
   
{"10",
 "10",
 "01",
 "01"}
Returns: 1
Let box 0 be the joker box. Now we only need to group all marbles of color 1 into one box.
3)
 
   
{"11",
 "11",
 "11",
 "10",
 "10",
 "01"}
Returns: 3
 
4)
 
   
{"020008000070",
 "000004000000",
 "060000600000",
 "006000000362",
 "000720000000",
 "000040000000",
 "004009003000",
 "000800000000",
 "020030003000",
 "000500200000",
 "000000300000"}
Returns: 6
 
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.

2차원 배열이 주어지고.. (i, j)은 i박스의 j색깔의 구슬의 개수를 의미한다.. 하나의 박스는 joker라고해서 여러가지 색깔의 구슬을 다 가질수 있고.. 나머지박스는 한가지 색깔의 구슬만 가지고 있어야한다.. 그리고 같은색깔의 구슬은 joker를 제외하고 나누어져있으면 안된다.. 이러한 조건을 만족시키도록 구슬을 옮길때 최소 몇번의 move가 필요한지 구하는 문제.. 임의의 박스에서 색깔에관계없이 임의의 구슬의 개수를 옮기는데 드는 비용은 1이다..

처음에 문제를 잘못이해하고 안드로까지 갔다가 다시 돌아왔다.. 흠.. 한 박스에서 한가지 색깔의 구슬을 임의의개수 옮기는데 비용이 1인줄 알고 다짰는데.. 샘플이 안나와서 당황.. -_-;; 문제를 다시보고 패닉상태에 빠지면서 좌절했다.. 다 포기하는 심정으로.. 그냥 주식이나 보고있었는데 막판에 번뜩 떠올라 잽싸게 코딩했다.. 300점짜리를 110점 먹었다.. -_-;;

일단 각 box에 대해서 joker라고 가정하고 나머지를 체크한다.. joker가 아닌 box에 대해서 두가지 이상의 구슬로 채워져있으면.. 무조건 한번 옮겨야한다.. (그냥 다 joker로 옮기면 된다..) 한가지 구슬로만 채워져있는경우.. 다른박스중에 역시 한가지색깔로 이루어져있고 그게 같은 색일경우면 역시 이동해야하고 그렇게 겹치는 경우가 없으면.. 이동할 필요가 없다..

으.. 여러모로 짜증났던 문제.. 그래도 이 문제가 Div1 첫번째 pass한 문제가 되었다.. ㅎㅎ

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class MarblesRegroupingEasy {
  9 public:
 10
 11 int minMoves(vector <string> boxes)
 12 {
 13     int n, m;
 14     int i, j, k, l, temp;
 15     int cnt, min1;
 16     int color[101];
 17     char map[101][101];
 18     n = boxes.size();
 19     m = boxes[0].size();
 20     for (i = 0; i < n; i++) {
 21         strcpy(map[i], boxes[i].c_str());
 22     }
 23     min1 = 99999999;
 24     for (i = 0; i < n; i++) {
 25         cnt = 0;
 26         memset(color, 0, sizeof(color));
 27         for (j = 0; j < n; j++) {
 28             if (i == j)
 29                 continue;
 30             l = 0;
 31             for (k = 0; k < m; k++) {
 32                 if (map[j][k] != '0') {
 33                     temp = k;
 34                     l++;
 35                 }
 36             }
 37             if (l == 1) {
 38                 if (color[temp])
 39                     cnt++;
 40                 color[temp] = 1;
 41             }
 42             else if (l > 1) {
 43                 cnt++;
 44             }
 45         }
 46         if (cnt < min1)
 47             min1 = cnt;
 48     }
 49 printf("min1= %d\n\n", min1);
 50     return min1;
 51 }
 52
 53 };

[500] IntervalSubsets

Problem Statement
     
You are given two vector <int>s, start and finish, representing a set of intervals. The i-th interval is between start[i] and finish[i], inclusive. A subset of the given set is valid only if the following two conditions are satisfied:
No two intervals in the subset intersect each other. Two intervals intersect each other if they both contain at least one common number.
Adding any remaining interval from the original set would make the subset invalid.
Return the number of distinct valid subsets of the given set. Two subsets are distinct if there is at least one interval in the first subset which is not in the second. Two intervals are distinct if their indexes in start (so, in finish also) are different. Correct result will always fit in 32-bit signed integer.
Definition
   
Class:
IntervalSubsets
Method:
numberOfSubsets
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int numberOfSubsets(vector <int> start, vector <int> finish)
(be sure your method is public)
   
 
Constraints
-
start and finish will each contain between 1 and 50 elements, inclusive.
-
start and finish will contain the same number of elements.
-
For all i, start[i] will be less than or equal to finish[i].
-
Each element of start and finish will be between 1 and 100, inclusive.
Examples
0)
 
   
{68,25}
{75,64}
Returns: 1
The whole set is the only valid subset.
1)
 
   
{4,2,3}
{4,5,3}
Returns: 2
The given set of intervals is {[4, 4], [2, 5], [3, 3]}. The valid subsets are {[4, 4], [3, 3]} and {[2, 5]}.
2)
 
   
{3,4,3,2,1}
{4,5,4,5,5}
Returns: 5
 
3)
 
   
{2,3,4,4,4,4,2,2,1}
{3,5,4,5,4,5,3,2,4}
Returns: 14
 
4)
 
   
{1, 1, 3, 3}
{2, 2, 4, 4}
Returns: 4
The given set of intervals is {[1, 2], [1, 2], [3, 4], [3, 4]}. We can combine each of the first two intervals with each of the other two.
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으로 여러개의 integer 구간이 들어온다.. 서로 겹치지않는 구간끼리 그룹화하여 생길수있는 그룹을 하나의 set으로 만들때, 나올수있는 set의 개수 구하기.. 단, 각 그룹에는 다른 구간을 더이상 추가할 수 없어야함.. 흠.. 문제해석이 어렵다.. ㅠ_ㅠ 자세한내용은 sample I/O를 보고 파악..;;

to be updated..




[950] StrangeArray

Problem Statement
   
You are given an infinite sequence P, where the i-th member is defined as follows:
  P[i] = (A[i % A.size] ^ (B[i % B.size] + i / B.size)) % 1000000007
where % denotes modulo, ^ denotes exponentiation, / denotes integer division, and X.size represents the number of elements in X.
Alternatively, the following pseudocode can be used to calculate the elements of P successively:
int i = 0;
loop forever
 P[i] = (A[i % A.size] ^ B[i % B.size]) % 1000000007;
 B[i % B.size] = B[i % B.size] + 1;
 i = i + 1;
end of loop
You are given vector <int>s A and B, and a string N containing an integer. Calculate the sum of the first N elements of the sequence (i.e., P[0] + P[1] + ... + P[N - 1]), and return that sum modulo 1000000007.
Definition
     
Class:
StrangeArray
Method:
calculateSum
Parameters:
vector <int>, vector <int>, string
Returns:
int
Method signature:
int calculateSum(vector <int> A, vector <int> B, string N)
(be sure your method is public)
   
 
Constraints
-
A and B will each contain between 1 and 50 elements, inclusive.
-
Each element of A and B will be between 1 and 10^9, inclusive.
-
N will represent an integer between 1 and 10^18, inclusive, with no leading zeros.
Examples
0)
 
   
{1,2,3}
{3,4}
"2"
Returns: 17
1^3 + 2^4 = 17.
1)
 
   
{2, 3, 4}
{2, 3}
"3"
Returns: 95
2^2 + 3^3 + 4^(2 + 1) = 95.
2)
 
   
{2, 3, 4}
{2, 3}
"5"
Returns: 192
2^2 + 3^3 + 4^(2 + 1) + 2^(3 + 1) + 3^(2 + 2) = 192.
3)
 
   
{1, 2, 3, 4}
{1}
"1000000000"
Returns: 607570807
1^1 + 2^2 + 3^3 + 4^4 + 1^5 + 2^6 + ... + 4^1000000000 = 607570807 (mod 1000000007).
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..