TopCoder SRM380 DIV2 (완료)

악.. 결국 상승세를 이어가지못하고.. 또 망쳤다.. 이런.. 500점 문제는 처음에 잘 이해해서 다 풀어놓고.. 디버깅하다가 문제를 헷깔려서 이상하게 고치고말았다.. ㅠ_ㅠ 음.. 첫번째 문제는 방에서 3번째로 풀었는데.. 괜히 챌 시도해서 점수만 많이 날렸다.. 챌 성공률 26% 완전 극악의 성공률을 보이고있다.. 근데.. 나 코딩속도 조금 빨라진건가?

방 8등 전체 283등..

[250] LuckyTicketSubstring

Problem Statement
     
A lucky ticket is an integer with exactly 2*n digits (written without leading zeroes), where the sum of the leftmost n digits is equal to the sum of the rightmost n digits.
You are given a string s, which contains only non-zero digits. Find the longest contiguous substring of s that is a lucky ticket and return its length. If there is no such lucky ticket, return 0 instead.
Definition
   
Class:
LuckyTicketSubstring
Method:
maxLength
Parameters:
string
Returns:
int
Method signature:
int maxLength(string s)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 50 characters, inclusive.
-
s will contain non-zero digits ('1'-'9') only.
Examples
0)
 
   
"123231"
Returns: 6
The entire string, 123231, is a lucky ticket because the first 3 digits sum up to 1+2+3=6, and the last 3 digits sum up to 2+3+1=6.
1)
 
   
"74233285"
Returns: 4
4233 is the longest lucky ticket here.
2)
 
   
"986561517416921217551395112859219257312"
Returns: 36
 
3)
 
   
"1"
Returns: 0
 
4)
 
   
"112"
Returns: 2
A lucky ticket must contain an even number of digits.
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.

문자열이 주어지고.. 그 문자열의 연속된 임의의 짝수 길이의 substring중에서 앞에 절반 digit sum이 뒤에 절반 digit sum과 같은 substring을 찾는것.. 그중에 가장 긴 길이를 찾는 문제..

brute force로 풀었다.. 모든 substring을 다 구하고.. 조건을 만족하는지 체크..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7 #define max(x, y) ((x) > (y) ? (x) : (y))
      8
      9 int check(char* str, int l)
     10 {
     11     int sum1, sum2;
     12     int i;
     13     sum1 = sum2 = 0;
     14     for (i = 0; i < l/2; i++)
     15         sum1 += str[i]-'0';
     16     for ( ; i < l; i++)
     17         sum2 += str[i] - '0';
     18     if (sum1 == sum2)
     19         return 1;
     20     return 0;
     21 }
     22
     23 class LuckyTicketSubstring {
     24 public:
     25
     26 int maxLength(string s)
     27 {
     28     char buf[100], sub[100];
     29     int len, max1;
     30     int i, j;
     31     strcpy(buf, s.c_str());
     32     len = strlen(buf);
     33     max1 = 0;
     34     for (i = 2; i <= len; i+=2) {
     35         for (j = 0; j+i-1 < len; j++) {
     36             strncpy(sub, &buf[j], i);
     37             sub[i] = 0;
     38             if (check(sub, i)) {
     39                 max1 = max(max1, i);
     40             }
     41         }
     42     }
     43     return max1;
     44 }
     45
     46 };

[500] LameKnight

Problem Statement
     
A lame knight is located at the bottom-left corner of a height x width chessboard. Unlike a healthy knight, a lame knight can only make moves where he goes to the right. The only possible moves are:
2 cells up, 1 cell right;
1 cell up, 2 cells right;
1 cell down, 2 cells right;
2 cells down, 1 cell right.
The knight will make one trip, and he wants to maximize the number of visited cells. The knight's starting cell counts toward this number. There is also one restriction for the knight's trip: it must contain each kind of a move at least once, unless it is shorter than 4 moves. If the knight makes less than 4 moves (thus visiting less than 5 cells), his moves are not limited in any way. Return the maximal number of cells the knight can visit during one trip, including the initial cell.
Definition
   
Class:
LameKnight
Method:
maxCells
Parameters:
int, int
Returns:
int
Method signature:
int maxCells(int height, int width)
(be sure your method is public)
   
 
Constraints
-
height will be between 1 and 2,000,000,000, inclusive.
-
width will be between 1 and 2,000,000,000, inclusive.
Examples
0)
 
   
100
50
Returns: 48
1 move of kind 2, 1 move of kind 3, 23 moves of kind 1 and 22 moves of kind 4.
1)
 
   
1
1
Returns: 1
There are no possible moves here, so the only visited cell is the starting cell.
2)
 
   
17
5
Returns: 4
It's possible to visit 5 cells (making 4 moves of kind 1 for example), but it's impossible to make it by 4 different moves. So, the best strategy here is to make 3 moves (thus visiting 4 cells).
3)
 
   
2
4
Returns: 2
 
4)
 
   
20
4
Returns: 4
4 cells can be visited using 2 moves of kind 1 and 1 move of kind 4.
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.

LameKnight가 움직이는 규칙은 일반 knight와 같지만.. 무조건 오른쪽 방향으로 이동해야한다.. height * width 보드가 주어질때 (1, 1)에 있는 lame knight가 갈수있는 최대 cell의 개수 구하기.. 단 4번 이상의 move를 할 경우 무조건 4방향 move를 다 이용해야하고.. 그렇지 않다면 move하는 방향에 제약이 없다..

문제 해석이 좀 까다로웠던 문제.. 나중에 문제를 제대로 이해하고 풀었는데.. 디버깅중에 문제가 다시 헷깔리는바람에.. 챌 당한 문제.. ㅠ_ㅠ 쉬운문제였는데.. 아쉽다..

그냥 규칙을 꼼꼼하게 잘 따져보면서 if문을 남발하면 풀 수있다..

  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
 10 class LameKnight {
 11 public:
 12
 13 int maxCells(int height, int width)
 14 {
 15     if (width == 1 || height == 1)
 16         return 1;
 17     if (width <= 2 && height <= 2)
 18         return 1;
 19     if (height <= 2)
 20         return min(4, (width+1)/2);
 21
 22     if (width < 7)
 23         return min(4, width);
 24     return width-2;
 25 }
 26
 27 };

[1000] CompilingDecksWithJokers

Problem Statement
     
You are given a vector <int> cards, the i-th element of which is the number of cards you have of type i, and an int jokers, the number of jokers you have. You want to construct decks using these cards. There are two types of valid decks:
A deck containing exactly 1 card of each type, and no jokers.
A deck containing exactly 1 card of each type except one, and exactly 1 joker.
For example, if there are 3 types of cards, the following four decks would be valid: {1, 2, 3}, {J, 2, 3}, {1, J, 3}, {1, 2, J}. Return the maximum possible number of valid decks you can construct with the given cards. Each card can only be a member of a single deck.
Definition
   
Class:
CompilingDecksWithJokers
Method:
maxCompleteDecks
Parameters:
vector <int>, int
Returns:
int
Method signature:
int maxCompleteDecks(vector <int> cards, int jokers)
(be sure your method is public)
   
 
Notes
-
The total number of types of cards is equal to the total number of elements in cards.
Constraints
-
cards will contain between 1 and 50 elements, inclusive.
-
Each element of cards will be between 0 and 500,000,000, inclusive.
-
jokers will be between 0 and 500,000,000, inclusive.
Examples
0)
 
   
{10, 15}
3
Returns: 13
10 full decks without jokers and 3 decks with jokers instead of cards of the first type can be compiled.
1)
 
   
{1, 2, 3}
4
Returns: 3
Three decks with one joker each can be compiled: one with the card of the second type changed to joker and two with the card of the first type replaced by joker.
2)
 
   
{1}
5
Returns: 6
Note that a deck can be composed of 1 sole joker if there is only 1 type of card.
3)
 
   
{2, 3, 4, 5, 6}
4
Returns: 4
 
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.

n 종류의 카드가 있고.. 각 종류별 카드의 개수와 조커의 개수가 주어진다.. 조커는 임의의 숫자를 대체할 수 있다.. {1, 2, 3, ..., n} 형식으로 각 종류별 카드가 하나씩 들어가게 해서 카드 묶음을 만들때 최대 몇개의 묶음을 만들 수 있는지 구하는 문제.. 각 묶음에는 최대 한개의 조커가 들어갈 수 있다..

이 문제는 가능한 묶음 수에 대해서 binary search해서 풀 수 있다.. 이러한 방법을 parametric search라고도 하는 것 같다.. ㅎㅎ

mid개의 묶음을 만들 수 있다고 가정할 때.. 묶음수보다 모자란 카드 종류에 대해서 그만큼 조커가 더 필요하다는 의미가 된다.. 이때 다음 두가지 사항을 반드시 만족해야 한다..

1) 필요한 조커 수 <= jokers
2) 필요한 조커 수 <= mid

첫번째 조건은 당연한 것이고.. 두번째 조건은 각 묶음에 들어갈 수 있는 조커 수는 최대 하나이기 때문이다..
두번째 조건을 생각해내는것이 조금 까다로웠다.. ;;;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class CompilingDecksWithJokers {
  9 public:
 10
 11 int maxCompleteDecks(vector <int> cards, int jokers)
 12 {
 13     int n, i;
 14     long long left, right, mid;
 15     long long need, res;
 16     n = cards.size();
 17     left = right = 0;
 18     for (i = 0; i < n; i++) {
 19         if (right < cards[i] + jokers)
 20             right = cards[i] + jokers;
 21     }
 22     while (left <= right) {
 23         mid = (left + right) / 2;
 24         need = 0;
 25         for (i = 0; i < n; i++) {
 26             if (cards[i] < mid)
 27                 need += mid - cards[i];
 28         }
 29         if (need <= jokers && need <= mid) {
 30             res = mid;
 31             left = mid + 1;
 32         }
 33         else {
 34             right = mid - 1;
 35         }
 36     }
 37     return (int)res;
 38 }
 39
 40 };