MENU

URAL2105 Alice and Bob are on Bikes(模拟)

2018 年 08 月 29 日 • 阅读: 1000 • 练习阅读设置

Alice and Bob are on Bikes

  • Time limit: 1.0 second
  • Memory limit: 64 MB

Alice and Bob, after played enough and completely figured out the game with colored strip, decided to ride bikes around the fountain on a circular path of length L. Alice rides with a speed vA, Bob — with a speed vB, and they have started in different directions. At the initial moment the kids were in the same point. When they “meet” (i.e., at some moment they are in the same point as in the previous were not), they joyfully exclaim (“Oh, Bob!” or “Oh, Alice!” respectively). But sometimes along the way, the kids stop to feed the squirrels. Find, how many times Alice and Bob “have met”.

Input

The first line contains integers L, T, vA, and vB that are the length of the path, the riding time and the speed of Alice and Bob, respectively (1 ≤ L ≤ 109; 1 ≤ T ≤ 106; 1 ≤ vA,vB ≤ $10^3$).

The next line contains a single integer n, that is the number of intervals in which children were feeding squirrels (0 ≤ n ≤ $10^5$). The next n lines describe those intervals. Each description consists of three integers: typei ti di, meaning who was feeding (1 for Alice and 2 for Bob), at what moment the feeding started and how much time it lasted, respectively (0 ≤ ti, diT; ti + diT).

It is guaranteed that for one kid any two intervals intersect in no more than one point. The intervals are given in order of non-decreasing ti.

Output

Output the number of “meetings” of Alice and Bob.

Sample

  • input

    10 10 2 1
    3
    1 1 1
    1 2 2
    2 2 1
  • output

    2

链接

https://cn.vjudge.net/problem/URAL-2105

题意

A和B在一个轨迹为圆形的路上骑自行车,最开始A和B都在同一点,然后A和B开始往相反的方向前进,但是中间A和B都可能有一些停留,路径长度L,时间T,A的速度va,B的速度vb,问A和B会相遇多少次。【在同一个时间路过同一个点】

题解

比赛的时候没看懂题目,被这句话as in the previous were not坑了很久,以为统计次数时需要去掉原来已经经过的点,其实这句话并没有什么用,还是太浮躁了,没有模拟样例,纠结了很久。

做法其实很简单,统计A在时间T内走的总路径la,B在时间T内走的总路径lb(都去掉了停留时间),然后答案就是(la+lb)/L。为什么呢?因为运动是绝对的,静止是相对的,我们只需要让A在原点保持不动,让B一直骑一直骑,那么B骑行的相对距离就是la+lb,然后(la+lb)/L就代表了经过原点的次数,即相遇次数。

代码

StatusAccepted
Time15ms
Memory408kB
Length612
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int n, l, t, va, vb, sa, sb, type, ti, di;
    while (scanf("%d%d%d%d", &l, &t, &va, &vb) != EOF)
    {
        scanf("%d", &n);
        sa = sb = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%d%d%d", &type, &ti, &di);
            if (type == 1)
                sa += di; // a停留时间
            else
                sb += di; // b停留时间
        }
        int la = (t - sa) * va; // a走的距离
        int lb = (t - sb) * vb; // b走的距离
        int ans = (la + lb) / l; // 总距离除以长度l就是碰面的次数
        printf("%d\n", ans);
    }
    return 0;
}

The end.
2018-08-29 星期三