当前位置: 首页 > 工具软件 > geeks-diary > 使用案例 >

【Gym - 101350K Owl Geeks Gym - 101350K】

陈坚
2023-12-01

The owls have the following equation:

Y = a × x2 + b × x

With a, b, and N given, they decide to put into a set the integer values of Y that are less than or equal to N and that are outputted from the equation from any positive integer x.

With that set of numbers, they come up with the problem of finding the winning digit among them.

The winning digit is a digit from 0 to 9 that will get the maximum number of points. How are points for a digit calculated you may ask? Well, be a bit more patient, I’m going to tell you now.

For each number in the set, if the digit was the most repeated digit or tied with other digits as the most repeated digit in the ith number of set S, then it would get one point from that ith number.

Can you tell the owls what the winning digit is?

Input
The first line of input is T – the number of test cases.

The first line of each test case is a, b, and N (1 ≤ a, b, N ≤ 105).

Output
For each test case, print on a line the winning digit with the maximum number of points. If there is a tie, print the minimum digit among them. If the set is empty, print  - 1.

Example
Input
2
1 2 50
20 3 10
Output
3
-1

题意 : 给出方程组 Y = a × x ^ 2 + b × x ,(x 为正整数,且 Y <= N)给出 a,b,N,对于每个满足条件 Y ,组成 Y 的数字 0 ~ 9 出现次数最多的数字贡献 + 1,求贡献最多的数字,满足贡献最多的前提下输出较小的数字,没有满足条件的 Y 的话输出 -1

思路 : 题意理解的话,就不难想了,暴力找 Y,统计每个数字的贡献

AC代码:

#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1e5 + 10;
typedef long long LL;
int m[12],mm[12];
int main()
{
    int T; scanf("%d",&T);
    while(T--){
        int a,b,n; scanf("%d %d %d",&a,&b,&n);
        int r = 0;
        memset(m,0,sizeof(m));
        for(int i = 1; a * i * i + b * i <= n; i++) r = i;
        if(r == 0){
            puts("-1"); continue;
        }
        for(int i = 1; i <= r; i++){
            int o = i * i * a + b * i;
            memset(mm,0,sizeof(mm));
            int v = 0;
            while(o){
                int u = o % 10;
                mm[u]++;
                v = max(v,mm[u]);
                o /= 10;
            }
            for(int j = 0; j <= 9; j++)
                if(mm[j] == v)
                    m[j]++;
        }
        int u = 0;
        for(int i = 0; i <= 9; i++) if(m[i] > m[u]) u = i;
        printf("%d\n",u);
    }
    return 0;
}
 类似资料:

相关阅读

相关文章

相关问答