0%

2020工大杯题解-B

个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - B - Classmate L’s PE course.

题目描述

Classmate L forgot to elect his course, so he had to take a strange PE course. On this strange course, students will play a weird game: each male student represent aa, and each female students represent bb. When a teacher says a non-zero positive integer number of cc, xx male students and yy female students need to gather together and keep .

Classmate L is bad at math, he wants to know how many people he will be gathering together with.

Lots of students forgot to elect courses too, so we can assume that there is an infinite number of male and female students.

输入数据

One line containing three non-zero positive integer nn, aa, bb. (0n100,2a,b104)\left(0 \leq n \leq 100, 2 \leq a,b \leq 10^4 \right).

Meaning of aa and bb are described above. nn means there will be nn queries.

For the next nn line, each line contains a non-zero positive integer cc. (0c106)\left( 0 \leq c \leq 10^6 \right)

输出数据

For each query, output the number of male students and the number of
female students separated by a space.

If it’s not possible form cc, output ARE YOU KIDDING ME?.

If there are multiple answers, output the answer as the greatest
number of male students
.

样例输入

2 2 3
1
100

样例输出

ARE YOU KIDDING ME?
49 0

题目大意

每个男生代表 aa,每个女生代表bb。每次询问一个数cc,问你 L 同学需和要哪些人一起才能凑出来cc。输出男生人数最大的方案。

相当于是求以下方程中 x,yx, y 的正整数解,同时要求x1x \ge 1, 输出x1,yx-1, y

ax+by=cax + by = c

思路

读入 a,b,na, b, n。 每次查询读入 cc , 起手直接 c=cac = c - a 。然后就是解方程。

进行时间复杂度分析:0c1060 \leq c \leq 10^6, 直接暴力即可。

伪代码

读入a,b,n
循环 n 次:
	读入 c
	c = c - a
	枚举男生人数: 从(c/a) 到 0:
		算女生人数是否是整数, 是就输出
	如果失败, 输出ARE YOU KIDDING ME?

代码

#include 
using namespace std;
int main(){
    int n,a,b,c;
    cin>>n>>a>>b;
    while(n--){
        cin>>c;
        int x = 0;
        int y = 0;
        c -= a;
        for(x = c / a; x >= 0; x --){
            if ((c - a * x) % b == 0){
                y = (c - a * x) / b;
                break;
            }
        }
        if (x == -1) {
            cout<<"ARE YOU KIDDING ME?"<

欢迎关注我的其它发布渠道