常州模拟赛d3t1 神在夏至祭降下了神谕

题目描述

我们村子在过去的400年中,断绝与下界的接触,过着自给自足的生活。

夏至祭是一场迎接祖灵于夏季归来,同时祈求丰收的庆典。

村里的男人会在广场上演出夏之军和冬之军的战争。夏之军会打倒冬之军的大将冬男,再放火将他连山车一起烧掉。

参与这场演出的一共有N+M位战士,其中N个人是冬之军,M个人是夏之军。

冬之军的大将冬男拥有改变季节的力量。他每次可以任意选取恰好K名战士,然后把这K个人中所有的夏之军变成冬之军,所有的冬之军变成夏之军。

冬男可以使用任意多次改变季节的力量,直到他将所有的人都变成了冬之军。

如果冬男将所有的人都变成了冬之军,那么冬男就获得了胜利。

我想要知道,对于给定的N,M,K,冬男是否有可能获得胜利。

神有时会降下神谕,帮助你作出判断。

输入输出格式

输入格式:

第一行包括一个正整数year,表示进行夏至祭的年份。

第二行包括一个正整数T,表示数据的组数。

接下来T行,每行三个非负整数N,M,K,每一行表示一组数据。输入数据保证K>0。

输出格式:

共T行,每行为一个字符串“Case x: S”,不包含引号。

输入输出样例

输入样例#1:

1924
9
2 0 3
2 1 4
2 6 3
100 5 12
7 6 10
6 6 10
1000000000000000000 1 2
500000000 500000000 987654321
1000000000 1000000000 987654321

输出样例#1:

Case 1: Winter
Case 2: Summer
Case 3: Winter
Case 4: Summer
Case 5: Winter
Case 6: Winter
Case 7: Summer
Case 8: Winter
Case 9: Winter

说明

若冬男有可能获得胜利,S为Winter,否则S为Summer。

n,m,k <= 10^18

分析:这道题真的是神题一道!首先这肯定是一道结论题,因为数据范围大到你没有其他任何方法。先推几个小结论:1.当m%k = 0时,Winter,显然的. 2.n + m <= k且m != 0时,Summer,也是显然的. 3.m = 0,Winter,也很显然. 4.当m为奇数,k为偶数时,Summer,这个需要脑补一下,首先如果换掉奇数个夏之军,那么还剩下偶数个,但是因为k是偶数个,所以还有奇数个冬之军被翻成了夏之军,所以还是奇数个,如果换掉偶数个夏之军,还是奇数个,所以无论如何都还是奇数个,无解.

      如果排除了以上情况,就有一个重要结论了:如果n + m > k,Winter.为什么呢?如果m > k,则把m mod k,这样把m缩小到k以下的范围,考虑如下两种翻法:1.全部翻夏之军,那么还会有k-i个夏之军.2.全部翻冬之军,那么还会有k + 2 – i个夏之军,列个表可以发现k以下的数都会存在,如果还剩下2个夏之军,我们用第二种翻法,还会剩下k个夏之军,最后一次翻完.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>

using namespace std;

int year, t;
long long n, m, k;

int main)
{
    scanf"%d%d", &year, &t);
    for int i = 1; i <= t; i++)
    {
        printf"Case %d: ", i);
        scanf"%lld%lld%lld", &n, &m, &k);
        if !m)
            printf"Winter
");
        else
            if m % k == 0)
                printf"Winter
");
            else
            if m % 2 == 1 && k % 2 == 0)
                printf"Summer
");
            else
                if n + m > k)
                    printf"Winter
");
                else
                    printf"Summer
");
    }

    return 0;
}

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注