TopCoder SRM378 DIV2 (완료)

오랜만에 참여한 탑코더.. 미국에 머무는동안 2번이나 빼먹었다.. 이로써 올해안에 1군복귀는 물건너갔다.. 젱장
오늘 문제셋은 평소에비해 쉬운것 같다.. 문제도 나름 명확하고.. 정말 오랜만에 2문제 풀었다.. ㅠ_ㅠ
그동안 하도 부진해서인지.. 이번에는 하수들만 모인방에서 했다.. 인도애들 왜케많아!!
다시 green으로 복귀했고.. volatility도 약간 높아졌다.. 나름 소득이 있는매치..
다음매치는 R 1000을 목표로해서 차근차근히 올라가야겠다.. 그동안 삽질한 영향이 크군..

방 3등 전체 73등..

정말 오랜만에 두문제 해결..;;

오랜만에 약간 가파른 상승곡선을 그렸다..


[250] TwoRotationCypher

Problem Statement
   
You have decided to create your own simple encryption method for strings containing only lowercase letters and spaces. You start by splitting the alphabet into two groups. The first group consists of the first firstSize letters of the alphabet, and the second consists of the remaining 26 - firstSize letters. To encrypt a character in your message, you do the following:
If it a space, it is kept as is.
If it is a letter in the first group, it is moved firstRotate letters forward in the group, wrapping back to the start if necessary. For example, if firstSize is 6 and firstRotate is 2, then 'A' would become 'C', and 'F' would become 'B'.
If it is a letter in the second group, then it is moved secondRotate letters forward in the group, again wrapping back to the start of the group if necessary.
Given firstSize, firstRotate, secondRotate and a message, return the encrypted form of the message.
Definition
   
Class:
TwoRotationCypher
Method:
encrypt
Parameters:
int, int, int, string
Returns:
string
Method signature:
string encrypt(int firstSize, int firstRotate, int secondRotate, string message)
(be sure your method is public)
   
 
Constraints
-
firstSize will be between 1 and 25, inclusive.
-
firstRotate will be between 0 and firstSize - 1, inclusive.
-
secondRotate will be between 0 and 25 - firstSize, inclusive.
-
message will contain between 1 and 50 characters, inclusive.
-
message will contain only lowercase letters ('a' - 'z') and spaces.
Examples
0)
 
   
13
0
0
"this string will not change at all"
Returns: "this string will not change at all"
 
1)
 
   
13
7
0
"only the letters a to m in this string change"
Returns: "onfy tbl flttlrs h to g cn tbcs strcna jbhnal"
 
2)
 
   
9
0
16
"j to z will change here"
Returns: "z sn y vikk chamge heqe"
 
3)
 
   
17
9
5
"the quick brown fox jumped over the lazy dog"
Returns: "yqn izalc kwgsf ogt bzehnm grnw yqn djvu mgp"
 
4)
 
   
3
1
2
"  watch   out for strange  spacing "
Returns: "  ybvaj   qwv hqt uvtbpig  urbakpi "
 
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-z 의 알파벳을 임의의 지점에서 나눠서 두개의 그룹으로 만든다.. 주어진 문자열이 첫번째 그룹에 속하면 첫번째 암호화규칙을 따르고 두번째 그룹에 속하면 두번째 암호화규칙을 따른다.. 암호화규칙은 단순히 원래 문제에서 주어진 수만큼 더하면 된다.. 즉 문자가 'a' 이고 rotate 값이 2 라면 암호화된 문자는 'c'가 된다.. 문자가 주어진 그룹의 범위를 넘어가면 다시 그룹의 처음으로 돌아간다..

쉬운문제.. 시키는데로 하면 된다.. 매치 도중 이문제를 내가 방에서 2번째로 빨리 풀었는데 코딩속도가 느린 나는 약간 당황했다..

첫번째 그룹에대해서는 단순히 모듈러 연산을 하면 쉽게 구해진다.. 두번째 그룹에대해서도 모듈러 연산을 포함한 한줄의 수식으로 가능하지만.. 워낙 귀찮은거를 싫어하므로.. 그냥 1씩더해가면서 simulate 했다.. 이런 단순무식한 방법은 코드길이는 늘어나지만 코딩속도는 줄여준다는 특징이 있다..

system test때 #include <cctype> 을 안한거를 알고 당황했는데.. 그대로 pass해버렸다.. 다행..;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class TwoRotationCypher {
      9 public:
     10
     11 string encrypt(int firstSize, int firstRotate, int secondRotate, string message)
     12 {
     13     char buf[100], res[100];
     14     int i, j;
     15     int len, ch;
     16     string ret;
     17     strcpy(buf, message.c_str());
     18     len = strlen(buf);
     19     for (i = 0; i < len; i++) {
     20         ch = buf[i] - 'a';
     21         if (!isalpha(buf[i])) {
     22             res[i] = buf[i];
     23             continue;
     24         }
     25         if (ch < firstSize) {
     26             ch += (firstRotate);
     27             ch %= firstSize;
     28         }
     29         else {
     30             for (j = 0; j < secondRotate; j++) {
     31                 ch++;
     32                 if (ch == 26)
     33                     ch = firstSize;
     34             }
     35         }
     36         res[i] = ch + 'a';
     37     }
     38     res[i] = 0;
     39     ret = res;
     40     return ret;
     41 }
     42
     43 };

[500] TrueStatements

Problem Statement
     
Professor Smith teaches a logic class. One day, he writes some statements on the blackboard:
Exactly a of these statements are true.
Exactly b of these statements are true.
Exactly c of these statements are true.
.
.
.
Each of a, b, c and so on is a number. He then asks the class how many of the statements are true.
You will be given a vector <int> statements, containing the numbers written in Professor Smith's statements. Return the number of the statements that are true. If there is more than one possible answer, return the largest one. If there are no possible answers, return -1.
Definition
   
Class:
TrueStatements
Method:
numberTrue
Parameters:
vector <int>
Returns:
int
Method signature:
int numberTrue(vector <int> statements)
(be sure your method is public)
   
 
Constraints
-
statements will contain between 1 and 50 elements, inclusive.
-
Each element of statements will be between 0 and 50, inclusive.
Examples
0)
 
   
{0, 1, 2, 3}
Returns: 1
The 2nd statement is true (there is one true statement) and the others are false.
1)
 
   
{0}
Returns: -1
This is the Epimedes paradox: if the statement is true then it claims to be false, but if it is false then it must be true.
2)
 
   
{0, 3, 1, 3, 2, 3}
Returns: 3
One solution is that the 3rd statement is the only true statement. However, it is also possible that the 2nd, 4th and 6th statements are true (all of which say that 3 statements are true), and the largest solution must be returned.
3)
 
   
{1, 1}
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.

여러개의 숫자가 들어오고 그 숫자의 값만큼의 statement가 true라는 것을 의미한다.. 정말로 true인 statement의 개수.. 답이 여러개면 그중 최대값 구하기..

문제를 본 순간 적잖이 당황했다.. 문제의 솔루션이 직관적으로 바로 떠올랐지만.. 500점이 이렇게 간단할리 없을거라고 생각해서 반례를 찾아보려고 많은 시간을 까먹은게 실수였다.. ㅠ_ㅠ

솔루션은 간단히.. 각 원소에대해서 그 원소의 값과 출현한 개수가 같으면 답이 될 수 있다..

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class TrueStatements {
      9 public:
     10
     11 int numberTrue(vector <int> statements)
     12 {
     13     int cnt[100];
     14     int n, i;
     15     n = statements.size();
     16     memset(cnt, 0, sizeof(cnt));
     17     for (i = 0; i < n; i++) {
     18         cnt[statements[i]]++;
     19     }
     20     for (i = 50; i >= 0; i--) {
     21         if (cnt[i] == i)
     22             break;
     23     }
     24     return i;
     25 }
     26
     27 };

[1000] HanoiState

Problem Statement
     
In the classic Towers of Hanoi problem, there are three pegs, labeled A, B and C, and n discs, of sizes 1 to n. Each disc has a hole in the center, so that it can be placed on a peg. Initially, all the discs are stacked on peg A in order of size, with the smallest disc on top. Only one disc may be moved at a time. In each move, you remove the top disc from one of the pegs, and place it on another peg. A disc may be placed on an empty peg or stacked on top of a larger disc, but it may not be placed on top of a smaller disc.
target is a string consisting of n characters, each of which is either A, B or C. The goal of the game is to make the minimum number of moves so that character i of target is the peg containing the disc of size i + 1. There is only one shortest sequence of moves. Return the state of the game after making moves of these moves, in the same format as target.
Definition
   
Class:
HanoiState
Method:
partwayState
Parameters:
string, int
Returns:
string
Method signature:
string partwayState(string target, int moves)
(be sure your method is public)
   
 
Constraints
-
target will contain between 1 and 30 characters, inclusive.
-
Each character of target will be either 'A', 'B' or 'C'.
-
moves will be between 0 and m, inclusive, where the shortest solution to the game takes m moves.
Examples
0)
 
   
"CCC"
4
Returns: "BBC"
The full sequence of states is AAA, CAA, CBA, BBA, BBC, ABC, ACC, CCC. After 4 moves the state is BBC.
1)
 
   
"AAC"
7
Returns: "AAC"
 
2)
 
   
"AAAAAAAAAAAAAAAAAAAAAAAAAAAA"
0
Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 
3)
 
   
"ABCABCABCABCABCABCABCABCABCABC"
100000000
Returns: "CCCCCCCCBAAAABBBBACBAAAAACBAAA"
 
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.

하노이타워에서 초기상태가 "AAA...AA" 일때.. moves번의 이동을 통해 target 을 만들고자 할때 최종 하노이타워의 상태를 구하는 문제.. (당연히 moves가 충분히 크면 답은 target과 같다) 문자열의 왼쪽이 위에있는 원반.. 오른쪽이 아래쪽에있는 원반이다.. 세개의 타워는 각각 'A', 'B', 'C' 로 표기..

시간이 많이 남아있었는데.. 결국 아쉽게도 못풀었다.. 나중에 1등한사람의 코드를 보니 내가 짜다포기한 코드와 거의 90%가 같았다.. 아쉽군..!! 하노이타워에대한 이해가 아직 부족하다..

우선 아래쪽 원반부터 top-down으로 생각한다.. 최종 이동지점만 찾으면 되므로 recursion을 돌릴필요가 없다.. 어떤 원반을 다른타워로 옮기기 위해서는 2^n 번의 이동이 필요하다는점을 이용하여 moves에서 2^n씩을 빼면서 target으로 조작해나간다.. 만약에 moves가 2^n보다 작으면.. target을 바꾸면 된다?! (왜그런지 모르겠다..)

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class HanoiState {
      9 public:
     10
     11 string partwayState(string target, int moves)
     12 {
     13     int i, j, k;
     14     int n, len, p;
     15     char buf[100], cur[100];
     16     char ch;
     17     string ret;
     18
     19     n = moves;
     20     len = target.size();
     21     strcpy(buf, target.c_str());
     22     for (i = 0; i < len; i++) {
     23         cur[i] = 'A';
     24     }
     25     cur[len] = 0;
     26     for (i = len-1; i >= 0; i--) {
     27         ch = buf[i];
     28         if (ch == cur[i]) {
     29             continue;
     30         }
     31         p = 1 << i;
     32         if (p > n) {
     33             for (j = 0; j < i; j++) {
     34                 if ((ch == 'A' && cur[i] == 'B') || (ch == 'B' && cur[i] == 'A')) {
     35                     buf[j] = 'C';
     36                 }
     37                 else if ((ch == 'A' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'A')) {
     38                     buf[j] = 'B';
     39                 }
     40                 else if ((ch == 'B' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'B')) {
     41                     buf[j] = 'A';
     42                 }
     43             }
     44         }
     45         else {
     46             for (j = 0; j < i; j++) {
     47                 if ((ch == 'A' && cur[i] == 'B') || (ch == 'B' && cur[i] == 'A')) {
     48                     cur[j] = 'C';
     49                 }
     50                 else if ((ch == 'A' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'A')) {
     51                     cur[j] = 'B';
     52                 }
     53                 else if ((ch == 'B' && cur[i] == 'C') || (ch == 'C' && cur[i] == 'B')) {
     54                     cur[j] = 'A';
     55                 }
     56             }
     57             cur[i] = ch;
     58             n -= p;
     59         }
     60     }
     61     ret = cur;
     62     return ret;
     63 }
     64
     65 };