SRM 507 - 나이스!

와우.. 이번매치에서 무려 rating +61 을 기록한 덕분에
거의 6개월만에 다시 Yellow 회복했다..~

이번 매치도 거의 망하는 분위기였는데.. 적극적으로 챌을 했던게 순위를 끌어올렸다..~

최근 2번의 매치에서 rating 100을 올렸다..


Level1 - CubeStickers

Problem Statement
    
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
 
Fox Ciel has a cube and some colored stickers. You are given a vector <string> sticker, where the i-th element is the color of the i-th sticker. Ciel wants to choose six of these stickers and apply one on each of the cube's faces. Each pair of adjacent faces must have different colors. Two faces are considered adjacent if they share an edge.
 
If this is possible, return "YES", otherwise, return "NO" (all quotes for clarity).
Definition
     
Class:
CubeStickers
Method:
isPossible
Parameters:
vector <string>
Returns:
string
Method signature:
string isPossible(vector <string> sticker)
(be sure your method is public)
    
 
Constraints
-
sticker will contain between 6 and 50 elements, inclusive.
-
Each element of sticker will contain between 1 and 10 lowercase letters ('a'-'z'), inclusive.
Examples
0)
 
    
{"cyan","magenta","yellow","purple","black","white","purple"}
Returns: "YES"
One of the possible ways is shown in the following picture:
 
1)
 
    
{"blue","blue","blue","blue","blue","blue","blue","blue","blue","blue"}
Returns: "NO"
 
2)
 
    
{"red","yellow","blue","red","yellow","blue","red","yellow","blue"}
Returns: "YES"
 
3)
 
    
{"purple","orange","orange","purple","black","orange","purple"}
Returns: "NO"
 
4)
 
    
{"white","gray","green","blue","yellow","red","target","admin"}
Returns: "YES"
 
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개의 color 가 주어지고 이 중 6개를 뽑아서 cube를 칠할때 이웃한 면이 다른색으로 칠할 수 있는지..

주사위를 하나 가져다 놓고 생각해보자..
일단 color가 6가지 이상이면 무조건 가능하고..
최소 3가지 종류만 있어도 가능한 경우가 있다..
그런데 같은 color 가 2개까지는 유용하지만 3개 이상 있어봤자 소용이 없다..
이를 조합해서 대충 풀어보자..

나름 재밌는 문제..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <set>
  7 #include <map>
  8 using namespace std;
  9 //#define min(x, y) ((x) > (y) ? (y) : (x))
 10 //#define max(x, y) ((x) > (y) ? (x) : (y))
 11 //#define INF 999999999
 12 //#define EPS 1e-14
 13
 14 class CubeStickers {
 15 public:
 16
 17 string isPossible(vector <string> sticker)
 18 {
 19     int i;
 20     int cnt, left;
 21     set<string> ss;
 22     map<string, int> mm;
 23     map<string, int>::iterator it;
 24     for (i = 0; i < sticker.size(); i++) {
 25         ss.insert(sticker[i]);
 26         if (mm.find(sticker[i]) == mm.end())
 27             mm[sticker[i]] = 1;
 28         else
 29             mm[sticker[i]]++;
 30     }
 31     cnt = 0;
 32     for (it = mm.begin(); it != mm.end(); it++) {
 33         if (it->second >= 2)
 34             cnt++;
 35     }
 36 printf("size = %d, cnt = %d\n", ss.size(), cnt);
 37     left = 6-ss.size();
 38     if (left <= 0)
 39         return "YES";
 40     if (cnt >= left)
 41         return "YES";
 42     return "NO";
 43 }
 44
 45 };