Enumeration[枚举]在数学题上的表现

HZJ's Blog / 2024-03-06 / 原文

转跳题目： 夜魔赛

夜魔赛

题目背景

$\text{EiffelCryOI}$团队举行了一场抢答赛 —— 「 夜魔赛 Round 1 」，并荣幸地请来了 HZJ。

这一次抢答赛，由 HZJ 担任评委，但由于团队工作的紧张， HZJ 要参与分配分数、审核考题。

与此同时，孔明灯收到了比赛通知。

题目描述

经过讨论，此次抢答赛共若干道题目，答对一道加 $5$ 分，答错一道扣 $8$ 分，不答不扣分也不加分。

此时孔明灯也获得 $n$ 分，现在请你分析一下，他最少答了几道题，答对了多少道题？

输入格式

输入共 $1$ 行：

一个正整数 $n$ ，表示孔明灯当前的得分。

输出格式

输出共 $2$ 行：

第一行输出孔明灯最少答的题数。
第二行输出孔明灯答对题目题数。

如果没有答案，就输出一行 Unsolvable

样例 #1

样例输入 #1

样例输出 #1

5
4

提示

【数据范围】

对于 $20\%$ 的数据， $0 \le n \le 10$。

对于 $100\%$ 的数据， $0 \le n \le 2 \times 10^2 $。

【广告】

$\text{EiffelCryOI}$出题组欢迎你。

$\huge \color{red} \text{题解}$

我们用枚举思维来看，无非就 $2$ 种数据值得我们枚举：

答对的题目和 未答对的题目

我们先简单打表枚举

Right Wrong Score
0       0     0
0       1     -8
1       1     -3
2       1     2
3       1     7
……

公式就是 $Right \times 5 + Wrong \times 8 = Score$。
由于数据范围小，所以说这道题枚举到 $100$ 都没问题的。 $\text{枚举时间复杂度为} O(n^2)$

#include <cstdio>
#include <iostream>
using namespace std;
int n;
int main()
{
    scanf("%d",&n);
    for (int i=0;i<=n;i++)//枚举错误
    {
        for (int j=0;j<=n;j++)//枚举正确
        {
            if (j*5<=i*8)   continue;//如果说错误的分数大于了正确的分数，就跳过。
            if (j*5-i*8==n)// 如果刚好达到，输出并结束。
            {
                printf("%d\n%d",i+j,j);
                return 0;
            }
        }
    }
    printf("Unsolvable");//如果没有正确答案，输出Unsolvable结束。
    return 0;
}

也是特别简单好吧！