sdut 1446スーパーマリー

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1446 スーパーマリオ
件名:
日本語…
 考え方:
試合の時、データが弱くなりました.O(10^12)のプログラムを全部パスしました.その後はあまり考えませんでした.データを入れてから.O(n)に変えたのは初めてです.エニュメレーションでスキップできる雲の数を数えて、ジャンプの長さDに対してデポジットを取り、剰余＋MとLの差(つまり雲の間の距離)を計算して、スキップできるかどうかを確認してみます.できないなら、ここでジャンプを続けません.
注意データタイプlong 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
", 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
",pos2);  

        }  

        else  

        {  

            ll ans = 0;  

            if (ct1 > ct2) ans = pos1;  

            else ans = pos2;  

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

        }  

    }  

    return 0;  

}