2522 - 有趣的游戏

近来，信阳师院ACM成员为备战省赛而奋力拼搏。大家每天很早就来到了304实验室，晚上又很晚才回宿舍，很是辛苦。

一天，小Q忙里偷闲，看到实验室地上铺的地板砖，便想出来一个小游戏，让大家娱乐一下，游戏规则如下：

在三维空间中，有L块地板砖铺成一条线段（有边界，可以掉下去），上边站有n个人，每个人要么往左走，要么往右走，速度为1

块砖/秒。当两个人相遇后，便同时掉头（掉头时间忽略不计）。给出每个人的初始位置和朝向，计算T秒后每个人的位置。

Input

输入的第一行为数据组数。

每组数据的第一行为3个正整数L，T，n（0<=n<=10000）;

以下n行每行描述一个人的初始位置，其中整数x为人距离该线段左端的距离（单位：块），

字母表示初始朝向（L表示向左，R表示向右）

Output

对于每组数据，输出n行，按输入顺序输出每个人的位置和朝向（Turning表示正在相遇）。

在第T秒之前已经掉下地板砖的人（正好走到地板砖边界的不算）输出Fell off。

Examples

Input

Output

Case #1:
2 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R

Solution C

#include"stdio.h"
#include"string.h"
struct erbi
{
    float l;
    char w;
}s[10001];
int main()
{
    int m,g=1;
    scanf("%d",&m);
    while(m--)
    {
        int len,t,n;
        scanf("%d%d%d",&len,&t,&n);
        int i,j,k;
        for(i=0;i<n;i++)
            scanf("%f %c",&s[i].l,&s[i].w);
        for(j=1;j<=t*2;j++)
        {
            for(i=0;i<n;i++)
            {
                if(s[i].w=='R')
                    s[i].l+=0.5;
                else s[i].l-=0.5;
            }
            for(i=0;i<n;i++)
            {
                for(k=0;k<n;k++)
                {
                    if(i==k)
                        continue;
                    if(s[i].l==s[k].l)
                        {
                            if(s[i].w=='R')
                                s[i].w='L';
                            else
                                s[i].w='R';
                        }
                }
            }
        }
        printf("Case #%d:\n",g++);
        for(i=0;i<n;i++)
        {
            int flage=1;
            if(s[i].l<0||s[i].l>10)
                printf("Fell off\n");
            else
        {
            for(j=0;j<n;j++)
               {
                   if(i==j)
                    continue;
                if(s[i].l==s[j].l)
                {
                    printf("%.0f Turning\n",s[i].l);
                    flage=0;
                    break;
                }
               }
               if(flage)
                printf("%.0f %c\n",s[i].l,s[i].w);
            }
        }
    }
    return 0;
}

Solution C++

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 10000+5;
const char dirName[][10]={"L","Turning","R"};
int order[maxn];//输入的第i只蚂蚁是最终状态下从左往右第order[i];

struct Ant
{
    int id;//输入顺序
    int p;//位置
    int d;//朝向，-1：左，0：转身，1：右
    bool operator < (const Ant&a) const
    {
        return p<a.p;
    }
}before[maxn],after[maxn];

int main()
{
    int tcase,L,T,n;
    scanf("%d",&tcase);
    int caseID=tcase;
    while(tcase--)
    {
        scanf("%d%d%d",&L,&T,&n);
        for(int i=0;i<n;i++)
        {
            int p,d;
            char c;
            scanf("%d %c",&p,&c);
            d=(c=='L'?-1:1);
            before[i]=(Ant){i,p,d};
            after[i]=(Ant){0,p+T*d,d};
        }
        sort(before,before+n);
        for(int i=0;i<n;i++)
            order[before[i].id]=i;
        sort(after,after+n);
        for(int i=0;i<n-1;i++)
            if(after[i].p==after[i+1].p)
                after[i].d=after[i+1].d=0;
        printf("Case #%d:\n",caseID-tcase);
        for(int i=0;i<n;i++)
        {
            int a=order[i];
            if(after[a].p<0||after[a].p>L)
                printf("Fell off\n");
            else
                printf("%d %s\n",after[a].p,dirName[after[a].d+1]);
        }
    }
    return 0;
}

Time Limit	1 second
Memory Limit	256 MB

Discuss Stats

上一题下一题