Binary Watch

Description:

Consider a binary watch with 5 binary digits to display hours (00 - 23) and 6 binary digits to display minutes (00 - 59).

For example 11:26 is displayed as 01011:011010.

Given a number x, output all times in human-readable format “hh:mm” when exactly x digits are 1.

Input:

An integer x. (0 ≤ x ≤ 9)

Output:

All times in increasing order.

Sample input:

1

Sample output:

00:01
00:02
00:04
00:08
00:16
00:32
01:00
02:00
04:00
08:00
16:00

分析：

   一开始没读懂题目，它的意思是当着11个数字中有 x 个是1的时候，按照 human readable 的形式输出所有可能的时间，并且要按照升序。

   读懂题目后一开始还是没有思路，第一感觉就是 : 前后分开考虑1的个数；接着，就按照这个第一感觉来想，假设x=2，则 : 右边的情况可分为：000011 、000110 、001100…… ，左边的情况也是类似，一想那么多中情况怎么遍历/搜索得到，换个方法吧……

   然后，又想到这和之前做过的Combination Sum II类似：一个位置要么是1，要么是0，这种情况正好对应一个数要么加，要么不加。于是想到了 DFS ，但是出现了 stack overflow 的错误，看到这个错误，我莫名的笑了出来（想到了stackoverflow网站）…想想也是，这种方法肯定不对：都已经表明有x个1了，少于和多于x个1的情况根本不用考虑，除了加大资源消耗（内存，时间）。

   接着，就不知道怎么做了，又想到了“第一感觉”，但还是不知道怎么实现。这时，突然想到可以求出所有的1的位置的组合情况，这也便于接着把2进制转化为10进制。按照这个思路，最后accept。

思路：

  1. 假设 : 右边1的个数为 right ，左边1的个数为 left 。接着循环一次 right-- 、 left++ ，即右边1的个数减少，右边1的个数增加。

  2. 每次循环内部

    • 首先得到 : 两边所有的组合情况（计算组合情况的算法使用了Generating combinations in c++的算法，很美妙…），也就是所有的时间表示（有不符合要求的，比如分钟>59，小时>23），此时组合情况的形式是：12 表示第1、2位是1（从左数或从右数都没关系，因为如果从左是 12 有从右数时的 56 与之对应，两者都是 110000）。

    • 由于输出 human readable ，所以需要转化为，在转化的同时将不符合要求（分钟>59，小时>23）的删去。

    • 由于输出需要按照升序，所以在 while 内不能输出，需要把结果存储到 set<int> 中（它自动按照非降序排序）。注意，这个存储的过程一定要在 while 内进行，因为 right + left = x 必须成立，在while内保证不了这个条件。

  3. 输出结果

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <set>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//combute all combinatorial instance
vector<string> getCombinations(int n, int r) {
    vector<string> combination;
    vector<bool> v(n);
    fill(v.begin(), v.begin() + r, true);

    do {
        string tem;
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                tem += to_string(i);
            }
        }
        if (tem != "") combination.push_back(tem);
    } while (prev_permutation(v.begin(), v.end()));

    return combination;
}

//change to human readable format, at the same time,
//remove the instance the not meet requirement like minute>59 or hour>23
vector<int> processTime(vector<string> &time, int maxTime) {
    vector<int> timeList;
    for (int i = 0; i < time.size(); i++) {
        string tem = time[i];
        int humanTime = 0;

        for (int j = 0; j < tem.length(); j++) {
            int n = tem[j] - '0';
            humanTime += pow(2, n);
        }
        if (humanTime < maxTime) timeList.push_back(humanTime);
    }
    return timeList;
}

int main(){
    set<string> rs;
    int x;
    scanf("%d", &x);
    if (x == 0) {
        printf("00:00\n");
        return 0;
    }
    int right = x < 6 ? x : 5;
    int left = max(0, x - right);
    int n = right;

    while (right >= 0 && left < 5) {
        vector<string> r;
        vector<string> l;
        r = getCombinations(6, right);
        l = getCombinations(5, left);
        vector<int> rr = processTime(r, 60);
        vector<int> ll = processTime(l, 24);
		
        if (ll.empty()) {
            for (int i = 0; i < rr.size(); i++) {
                string tem = "";
                tem += "00:";
                if (rr[i] < 10) tem += "0";
                tem += to_string(rr[i]);
                rs.insert(tem);
            }
        }
        else if (rr.empty()) {
            for (int i = 0; i < ll.size(); i++) {
                string tem = "";
                if (ll[i] < 10) tem += "0";
                tem += to_string(ll[i]);
                tem += ":00";
                rs.insert(tem);
            }
        }
        else {
            for (int i = 0; i < ll.size(); i++) {
                for (int j = 0; j < rr.size(); j++) {
                    string tem = "";
                    if (ll[i] < 10) tem += "0";
                    tem += to_string(ll[i]);
                    tem += ":";

                    if (rr[j] < 10) tem += "0";
                    tem += to_string(rr[j]);
                    rs.insert(tem);
                }
            }
        }

        right--;
        left++;
    }

    for (set<string>::iterator it = rs.begin(); it != rs.end(); it++) {
        cout << *it << endl;
    }

    //system("pause");
    return 0;
}