MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 340 - Master-Mind Hints
AOAPC II

UVaOJ 340 - Master-Mind Hints

Chai
2021-11-24 0:00:00在线评测阅读 224

问题描述

p340

原题链接:UVaOJ 340 - Master-Mind Hints

相关说明:本题为《算法竞赛入门经典(第2版)》例题 3-4

解法一:模拟

注意:统计数值和位置正确的元素对数量(记为 strong )很简单,可是直接统计数值正确但位置不对的元素对数量(记为 weak)有点麻烦,需要找找规律。先放宽条件:试着统计两个序列中数值正确的元素对数量 —— 很容易发现,只需要计算数值 0~9 分别在两个序列中成对出现的次数并求和(记为 both ),然后发现 both = strong + weak 恒成立这一规律,就可以算出 weak 的值。

C++
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;
}
Python
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})")

AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz