问题描述
p340原题链接：UVaOJ 340 - Master-Mind Hints
相关说明：本题为《算法竞赛入门经典（第2版）》例题 3-4
解法一：模拟
注意：统计数值和位置正确的元素对数量（记为 strong ）很简单，可是直接统计数值正确但位置不对的元素对数量（记为 weak）有点麻烦，需要找找规律。先放宽条件：试着统计两个序列中数值正确的元素对数量 —— 很容易发现，只需要计算数值 0~9 分别在两个序列中成对出现的次数并求和（记为 both ），然后发现 both = strong + weak 恒成立这一规律，就可以算出 weak 的值。
|
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 |
#include <bits/stdc++.h> using namespace std; int main() { int n, temp, game_number = 0; while (cin >> n && n) { cout << "Game " << (++game_number) << ":" << endl; vector<int> secret_code; for (int i = 0; i < n; ++i) { cin >> temp; secret_code.push_back(temp); } while (true) { bool all_zeros = true; vector<int> guess_code; for (int i = 0; i < n; ++i) { cin >> temp; if (temp != 0) all_zeros = false; guess_code.push_back(temp); } if (all_zeros) // no more guess break; int strong = 0, weak = 0, both = 0; array<array<int, 10>, 2> cnt = {0}; for (int i = 0; i < n; ++i) { if (guess_code[i] == secret_code[i]) strong += 1; cnt[0][guess_code[i]] += 1; cnt[1][secret_code[i]] += 1; } for (int i = 0; i < 10; ++i) both += min(cnt[0][i], cnt[1][i]); weak = both - strong; cout << " (" << strong << "," << weak << ")" << endl; } } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
game_number = 0 while True: n = input() if n == "0": break game_number += 1 print(f"Game {game_number}:") secret_code = [int(i) for i in input().split()] while True: guess_code = [int(i) for i in input().split()] if not any(guess_code): # all numbers are zero break strong = sum([(a == b) for a, b in zip(secret_code, guess_code)]) both = sum([min(secret_code.count(i), guess_code.count(i)) for i in range(10)]) weak = both - strong print(f" ({strong},{weak})") |
