sdut 1446 超级玛丽

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1446超级玛丽

题意:

中文...

 思路:

比赛时,数据弱了,让我一个O(10^12)的程序都过了,后来就没多想,加上数据后。改为O(n)的才过。枚举能跳过的云彩数,然后对跳跃的长度D取余求商,计算余数+ M与L的差值(即云彩之间的距离)在检查看看能否跳过,如果不能,就截止在这里不会继续往下跳了。

注意数据类型long long

//#pragma comment(linker,"/STACK:327680000,327680000")  

#include <iostream>  

#include <cstdio>  

#include <cmath>  

#include <vector>  

#include <cstring>  

#include <algorithm>  

#include <string>  

#include <set>  

#include <functional>  

#include <numeric>  

#include <sstream>  

#include <stack>  

#include <map>  

#include <queue>  

  

#define CL(arr, val)    memset(arr, val, sizeof(arr))  

  

#define ll long long  

#define inf 0x7f7f7f7f  

#define lc l,m,rt<<1  

#define rc m + 1,r,rt<<1|1  

#define pi acos(-1.0)  

#define ll long long  

#define L(x)    (x) << 1  

#define R(x)    (x) << 1 | 1  

#define MID(l, r)   (l + r) >> 1  

#define Min(x, y)   (x) < (y) ? (x) : (y)  

#define Max(x, y)   (x) < (y) ? (y) : (x)  

#define E(x)        (1 << (x))  

#define iabs(x)     (x) < 0 ? -(x) : (x)int  

#define OUT(x)  printf("%I64d\n", x)  

#define lowbit(x)   (x)&(-x)  

#define Read()  freopen("din.txt", "r", stdin)  

#define Write() freopen("dout.txt", "w", stdout);  

  

  

  

using namespace std;  

  

ll N[2],D[2],M[2],L[2];  

  

int main()  

{  

    int i;  

    ll pos1,pos2;  

    ll ct1,ct2 ;  

    int T;  

    scanf("%d",&T);  

    while (T--)  

    {  

        ct1 = ct2 = 0;  

        cin>>N[0]>>D[0]>>M[0]>>L[0];  

        cin>>N[1]>>D[1]>>M[1]>>L[1];  

  

        ll sh = 0, yu = 0;  

        for (i = 0; i < N[0]; ++i)  //枚举跳过云彩的数量

        {  

            pos1 = i*M[0] + L[0];  //计算长度

            sh = pos1/D[0];  //取余求商

            yu = pos1%D[0];  

            pos1 = sh*D[0] + D[0];  //跳了cnt1后的距离

            ll s = yu + M[0] - L[0];  //这是关键来决定是否能够继续往下跳

            if (s > D[0])  

            {  

                ct1 = pos1/D[0];  

                break;  

            }  

        }  

        if (i >= N[0])  

        {  

            pos1 = sh*D[0] + D[0];  

            ct1 = pos1/D[0];  

        }  

  

  

        for (i = 0; i < N[1]; ++i)  

        {  

            pos2 = i*M[1] + L[1];  

            sh  = pos2/D[1];  

            yu = pos2%D[1];  

            pos2 = sh*D[1] + D[1];  

  

            ll s = yu + M[1] - L[1];  

            if (s > D[1])  

            {  

                ct2 = pos2/D[1];  

                break;  

            }  

        }  

        if (i >= N[1])  

        {  

            pos2 = sh*D[1] + D[1];  

            ct2 = pos2/D[1];  

  

        }  

  

        if (ct1 == ct2)  

        {  

            printf("Az is Winner at %lld\n",pos2);  

        }  

        else  

        {  

            ll ans = 0;  

            if (ct1 > ct2) ans = pos1;  

            else ans = pos2;  

            printf("Lz is Winner at %lld\n",ans);  

        }  

    }  

    return 0;  

}  

   

  

 

你可能感兴趣的