【UVA-340】Master-Mind Hints【紫书】

【UVA-340】Master-Mind Hints【紫书】

问题链接:https://vjudge.net/problem/UVA-340

udebug数据:https://www.udebug.com/UVa/340

核心思路:

由于要统计出两个数据——在正确位置上的数的个数(为方便表述,下文使用on表示)和不在正确位置上但数字正确的个数(为方便表述,下文使用cn表示)。对于数on,在已知本题中要求的code后,只需要在读入每一条数据时和存储的code比较一下就好,如果一样就自增1;对于数cn,考虑到on + cn是1-9这9个数字正确出现次数之和,即:

\(on + cn = \sum_{i=1}^9min(cnt[i], tmp\_cnt[i])\).

(备注:其中,使用cnt[i]表示数字i在正确序列中出现的次数,而tmp_cnt[i]表示数字i在猜测序列中出现的次数)

因此:

\(cn = \sum_{i=1}^9min(cnt[i], tmp\_cnt[i]) – on\).

 

Solution:

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1001;
const int SIZE= 10;
int cnt[SIZE];      // to store the appearance times of 1 ~ 9
int code[LIM];      // to store the code
int tmp_cnt[SIZE];

inline int mini(int a, int b) { return a < b ? a : b; }

int main(void) {
    int on, cn;     // "on" is the number of correct ordered number
    int n, t;
    for (int k = 1; ~scanf("%d", &n) && n; k++) {
        printf("Game %d:\n", k);
        memset(cnt, 0, sizeof cnt);

        // read the code
        for (int i = 0; i < n; i++) {
            scanf("%d", code + i);
            cnt[code[i]]++;
        }

        do {
            memset(tmp_cnt, 0, sizeof tmp_cnt);
            on = cn = 0;
            for (int i = 0; i < n; i++) {
                scanf("%d", &t);
                tmp_cnt[t]++;
                if (code[i] == t) on++;
            }

            for (int i = 1; i <= 9; i++)
                cn += mini(cnt[i], tmp_cnt[i]);

            if (t) printf("    (%d,%d)\n", on, cn - on);
        } while(t);
    }
    return 0;
}

 

相关阅读:

《算法竞赛入门经典》(紫书)全AC代码