Greenmoon55's Blog

Google Code Jam 2012

Greenmoon55 — Sat, 12 May 2012 12:12:33 +0800

Qualification Round
Problem A. Speaking in Tongues
简单的按规律替换字符串
Problem B. Dancing With the Googlers
忘记了具体内容了，反正要注意边界特殊情况。
Problem C. Recycled Numbers
比赛时想不明白 Case #4，于是没交大数据，后来看了 Contest Analysis 才知道有1212这种情况，会重复。比赛的时候移位是用字符串实现的。。后来才改过来。看了代码 Contest Analysis 的才知道不用数组记录数字是否出现的，只要移回原数就退出，即可避免循环节的问题。

#include <iostream>
#include <cstdio>
using namespace std;
 
int a, b;
long long ans;
 
void work(int num)
{
    int temp = num;
    int base = 1;
    int digit = 1;
    while (temp / 10 > 0)
    {
        base *= 10;
        temp /= 10;
        ++digit;
    }
    int move;
    int a[10];
    temp = num;
    for (int i = 0; i < digit - 1; i++)
    {
        move = temp % 10;
        temp /= 10;
        temp += base * move;
        a[i] = temp;
        if (temp > num && temp <= b)
        {
            ans++;
            // 判断 temp 是否出现过
            for (int j = 0; j < i; j++)
                if (a[i] == a[j])
                {
                    --ans;
                    break;
                }
        }
 
    }
}
 
int main()
{
    int t;
    cin >> t;
    for (int tcase = 1; tcase <= t; tcase++)
    {
        scanf("%d%d", &a, &b);
        ans = 0;
        for (int i = a; i < b; i++)
        {
            work(i);
        }
        printf("Case #%d: ", tcase);
        cout << ans << endl;
    }
    return 0;
}

Round 1B
Problem A. Safety in Numbers
这道题非常好玩。题意是这样的：每位选手的得分 = 评委给分 + 所有选手得到的评委给分和 * 这位选手的观众投票率(0-100%)。每个观众只能投一个选手，现在要淘汰得分最低的选手，若有多位选手得分相同，且都为最低分数，那么没人会被淘汰。求每位选手至少需要得到多少观众投票才能不被淘汰。

第一个想法就是先不考虑观众投票，对于当前选手A，找现在得分最低的选手B，算一下A要多少投票率才能超过剩下的票都投B的得分。这个想法是错误的。因为算完之后，其他多个选手可能比A、B得分都少，只需要让A的得分大于等于所有人都最低分数即可。

看看 Case #4，

Input: 3 24 30 21
Output: 34.666667 26.666667 38.666667

每个人的得分是相同的！这是一个巧合吗？不是的，由于评委给分已知，每个观众只能投一票，所有选手的得分总和是固定的，那么每个选手只要得到所有选手的得分总和 / 选手个数即可保证不被淘汰。那么，先求出平均得分，然后对每个选手解方程求投票率即可。

小数据里有这样一种情况。

8 0 0 0 0 72 0 0 0

每位选手的平均得分是(72 + 72) / 8 = 18，显然72已经远远超过18了。那么此时就不考虑72（也就是说72不需要观众投票），平均得分为(0 + 72) /7 = 10.2857143，然后投票率为 (10.2857143 – 0) / 72 = 14.2857143%。

这样就可以过小数据了，不过还有一个问题，如果去掉72之后，仍然有数字大于平均得分怎么办？
先从大到小排个序，然后依次考虑即可，大于平均得分就说明这位选手不需要投票，答案为 0。最后的就肯定需要投票啦，不管他的评委得分是多少，如果得到100%的观众投票就肯定不会被淘汰，如：

2 10 0

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int num[250],num2[250];
int main()
{
    int t;
    int n;
    cin >> t;
    for (int tcase = 1; tcase <= t; tcase++)
    {
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> num[i];
            sum += num[i];
        }
        memcpy(num2, num, sizeof(num2));
        sort(num, num+n, greater<int>());
        double temp = (sum * 2) / (double)n;
        int count = n;
        int total = sum;
        for (int i = 0; i < n; i++)
        {
            if (temp < num[i])
            {
                total-=num[i];
                --count;
                temp = (total + sum) / (double)count;
            }
        }
        printf("Case #%d: ", tcase);
        if (num2[0] > temp) printf("0");
        else printf("%lf", (temp - num2[0]) / sum * 100);
        for (int i = 1; i < n; i++)
        {
            if (num2[i] > temp) printf(" 0");
            else printf(" %lf", (temp - num2[i]) / sum * 100);
        }
        cout << endl;
    }
    return 0;
}

Round 1C
Problem A. Diamond Inheritance
判断是否有这种情况发生：D类继承自B类和C类，B类继承自A类，C类也继承自A类，这就形成了一个菱形。
我用并查集做的…DFS，如果结点被访问时已经和上一个结点在同一个集合里就说明出现了这种情况。
呃，似乎用不到并查集啊，用个bool used[]标记就行了吧。。
虽然共有1000个类，但每个类最多继承自10个类。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int nodeMax = 1010;
int p[nodeMax];//p:parent
int rank[nodeMax];
int map[nodeMax][nodeMax];
int n;
 
void make_set()
{
    for (int i=1;i<=n;i++) //pay attention!
    {
        p[i]=i;
        rank[i]=0;
    }
}
 
int find_set(int x)
{
    if (x!=p[x]) p[x]=find_set(p[x]);
    return p[x];
}
 
bool work(int a)
{
    int x, y;
    int temp;
    for (int i = 1; i <=map[a][0]; i++)
    {
        temp = map[a][i];
        x = find_set(a);
        y = find_set(map[a][i]);
        if (x != y)
        {
            if (rank[x]>rank[y]) p[y]=x;
            else
            {
                p[x]=y;
                if (rank[x]==rank[y]) rank[y]++;
            }
        }
        else return true;
    }
    for (int i = 1; i <= map[a][0]; i++)
    {
        if (work(map[a][i])) return true;
    }
    return false;
}
 
int main()
{
    int t;
 
    cin >> t;
    for (int tcase = 1; tcase <= t; tcase++)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> map[i][0];
            for (int j  = 1; j <= map[i][0]; j++) cin >> map[i][j];
        }
        bool yes = false;
        for (int i = 1; i <= n; i++)
        {
            make_set();
            if (work(i))
            {
                yes = true;
                break;
            }
        }
        printf("Case #%d: ", tcase);
        if (yes) printf("Yes\n");
         else printf("No\n");
    }
    return 0;
}

Problem B. Out of Gas
这完全是个物理题，读题很费时间。
你开一辆车，给定最大加速度，减速的加速度随意，也就是说可以瞬间停车。前面有一辆车一直匀速运动，不过它的速度在特定的点可以突然改变。求从起始点到指定位置的最短时间。
Small Input 最多只有两个点，比一下前面的车还是自己的车一直加速先到指定位置即可。刚花了一晚上写大数据，越写越烦，一看才73人A了这个。。还是算了吧。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
struct point
{
    double t;
    double x;
}p[5];
double acc[15];
int main()
{
    int t;
    double d;
    int n, a;
    cin >> t;
    for (int tcase = 1; tcase <=t; tcase++)
    {
        printf("Case #%d:\n", tcase);
        cin >> d >> n >> a;
        for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].t, &p[i].x);
        for (int i = 0; i < a; i++)
        scanf("%lf", &acc[i]);
        double t1, t2;
        if (n == 2)
        {
            t2 = p[0].t + (d - p[0].x) * (p[1].t - p[0].t) / (p[1].x - p[0].x);
            for (int i = 0; i < a; i++)
            {
                t1 = sqrt(2*d/acc[i]);
                if (t1 > t2) printf("%.7lf\n", t1);
                else printf("%.7lf\n", t2);
            }
        }
        else
        {
            for (int i = 0; i < a; i++)
            {
                t1 = sqrt(2*d/acc[i]);
                printf("%.7lf\n", t1);
            }
        }
    }
    return 0;
}

Code Jam 还是挺好玩的，而且比赛结束之后马上出排名。最后1015没进，明年再来吧。
还想看看 Round 1C 的 Problem C. Box Factory 和 Round 1B 的 Problem C. Equal Sums。

练习曲 (2006)

Greenmoon55 — Tue, 08 May 2012 16:04:47 +0800

图片来源：http://www.wretch.cc/blog/EtudeBike

评分：4/5
很像一部纪录片，没想到骑行的主人公听力不好，说话也不清楚。环岛游倒没什么特别，肯定在路上遇到一些好心人，电影后面一小段节奏有点慢。。

几个印象深刻的情节：小虫爬过地图、镜头（小女孩）透过啤酒看别人、一条鱼从天而降，貌似是从海鸥嘴里掉下来的（？）、抗议女工租车，半价优惠。

另外感觉台湾人讲话跟以前室友的闽南话确实有点像。。

===
好久没看电影，好久没看纪录片了。
以前不知道在这里发海报算不算侵权，现在觉得应该算合理使用吧。

数学建模邀请赛

Greenmoon55 — Sun, 06 May 2012 03:10:24 +0800

从上周六到这周六，折腾一周数学建模。

两道题目，第一个是说水滴的高度和体积之间的关系，随着体积的增大高度先增大后减小，没注意具体什么问了什么。。
第二个什么条件都没给，直接问如何在城市布局 PM2.5 监测站。

完全是去打酱油，前几天每天晚上都语音好几个小时，查查论文，英文的看不懂，中文的没什么资料。大家都不怎么说话，。因为没思路。。我觉得非常非常痛苦。。后来H提出个想法，就是按风向和温度对 PM2.5 监测的影响，对上海地图拉伸两次，然后在地图里面画N个圆，要求半径相同，求出每个圆的位置，然后再把这些坐标转换到原来的上海地图上。

我就写了个凸包，让地图拉伸之后仍然是个凸多边形，不过由于我们没取几个点，其实肉眼看一下就行的…还写了一个显示这些点的程序，不过没用上，原来 MATLAB 直接就能弄。求圆的位置用的是 LINGO，貌似是线性规划，原来还有这种神奇的软件。。当然这些都不是我弄的。

最后我发的第一份pdf排版有点问题。。只好最后几分钟再发一遍。囧。。其实还有个大问题，这里就不说了= =

我们的假设是扩散快的地方少放监测站，因为这些地方的代表性不强。感觉怪怪的，不过细想还是有道理的。当然还要看环保局怎么想了，哪里有地方放设备，哪里空气质量比较好（貌似北京把一个监测站从前门挪到郊区了）。

找资料的时候还谈到了热岛效应、盛行风向、迎风坡背风坡（为啥迎风坡降水多、背风坡降水少来着？完全忘了！！）高中学地理那段时光多好啊～高中还选了地理选修课呢。。

还是对数学建模不太感兴趣。。当时想着为我们那个创新项目学点MATLAB，结果现在一点都没学，我也不想学。。

这一周大约在这上面花了多于（1号一天+3小时/天（其余天）），而且很影响心情。。好不容易有个作业这么少的假期啊。也是因为这个间接导致图形学作业没按时交。。就是不想做了。。晚了两天交，而且只写了旋转。当然很感谢两位队友～程序和论文基本都是他们写的。

以后还要不要参加数学建模呢…看到一个例子是根据客流量安排公交班次，那个倒是很好玩的。不过其他的都不好玩。

话说本来准备这周六从安亭北去苏州运转呢，结果没起来，还好没起来，否则被问到就尴尬了= =

====================
今天 codejam 太悲剧了。。纠结了半天到底睡不睡觉，在床上躺着玩手机没睡着，于是就起来喝杯咖啡写比赛。（第一次喝这种，雀巢醇品五毛钱一袋冲出来的味道和麦当劳的一样哦！）
A题想了半天才明白，大数据居然还挂了，不知道存在哪里。（输出里居然有-0.000333，难道是精度问题）
B不想看
C写了一半不想写了，于是过来写blog…

于是晚上再来一次吧～重在参与。。

====================
晚上搞完数学建模玩了会 openBVE，没想到这么小！听说很多年了，第一次玩。画面效果不错，就是。。AI不会动，而且限速提示、停站提示不清楚。玩到九点有点头晕就算了。

====================
呃。。最近在看Coursera上的编译原理。。视频大约两个多小时，作业还要花一两个小时啊，有的题目有点难/tricky，有论坛，不知道以后能不能坚持下去。

USTC1305 Maximum income

Greenmoon55 — Fri, 20 Apr 2012 00:20:22 +0800

来自 xw 和 wh：
维护一个递减的单调队列，因为后入队的数只有比前面所有的数小才有可能成为符合条件区间的起点，若不满足这个条件，就二分找当前最大区间。复杂度 nlogn。

===
最近好忙= =

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
int queue[MAXN];
int day[MAXN];
int main()
{
    int t;
    int n, c;
    int p, ans;
    cin >> t;
    while (t--)
    {
        scanf("%d%d", &n, &c);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
 
        queue[0] = a[0];
        day[0] = 0;
        p = 0;
        ans = 0;
 
        for (int i = 1; i < n; i++)
        {
            if (a[i] < queue[p])
            {
                queue[++p] = a[i];
                day[p] = i;
            }
            else
            {
                int l = 0, r = p;
                int mid;
                while (l < r)
                {
                    mid = (l + r)/2;
                    if (queue[mid] <= a[i])
                    {
                        r = mid;
                    }
                    else l = mid + 1;
                }
                if (i - day[l] > ans) ans = i - day[l];
            }
        }
        if (ans) ans = (++ans)*c;
        printf("%d\n", ans);
    }
    return 0;
}

USTC1300 Big grid

Greenmoon55 — Fri, 20 Apr 2012 00:10:30 +0800

USTC1300

DP，dp[i][SAME 或 DIFF] 表示格子[0][i]和[1][i-1]相同颜色或不同颜色有多少种情况。然后就很好写了。

数学解法不会= =

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int SAME = 1;
const int DIFF = 0;
long long dp[10010][2];
int main()
{
    int t,n,m,k;
    long long ans;
    cin >> t;
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &n, &m, &k);
        if (n == 1)
        {
            ans = k;
            for (int i = 1; i < m; i++)
            {
                ans *= k - 1;
                ans %= 1000000007;
            }
        }
        else
        {
            if (m == 1)
            {
                ans = k*(k - 1);
                ans %= 1000000007;
            }
            else
            {
                dp[1][SAME] = k*(k - 1);
                dp[1][SAME] %= 1000000007;
                dp[1][DIFF] = k*(k - 1)*(k - 2);
                dp[1][DIFF] %= 1000000007;
                for (int i = 2; i < m; i++)
                {
                    dp[i][SAME] = dp[i - 1][DIFF]*(k - 2) + dp[i - 1][SAME]*(k - 1);
                    dp[i][SAME] %= 1000000007;
                    dp[i][DIFF] = dp[i - 1][SAME]*(k - 1)*(k - 2) + dp[i - 1][DIFF]*(k - 2)*(k - 2);
                    dp[i][DIFF] %= 1000000007;
                }
                ans = (dp[m - 1][SAME]*(k - 1) + dp[m - 1][DIFF]*(k - 2)) % 1000000007;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

HDU4193 Non-negative Partial Sums

Greenmoon55 — Sat, 14 Apr 2012 23:39:19 +0800

HDU4193
终于知道单调队列了！其实挺简单的。搜到了这个：补缺补漏：单调队列- Blog of Felix021 – TechOnly

因为每个元素最多入队出队一次，所以复杂度是O(n)的。

这道题怎么做呢？开一个 2n 的数组，sum[i] 记录 a[1] 到 a[i] 的和。若在某个长度为 n 的区间里的最小 sum 大于等于区间左侧的 sum，也就是说区间里没有负数，答案计数加一。

// cin 会超时，不用 deque 会快一点
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 2000010;
int a[MAXN];
int main()
{
    int n;
    while (scanf("%d", &n))
    {
        if (n == 0) break;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            a[i+n] = a[i];
        }
        for (int i = 1; i <= n*2; i++)
        {
            a[i] += a[i-1];
        }
 
        deque<int> q;
        int ans = 0;
        for (int i = 1; i <= n*2; i++)
        {
            while (!q.empty() && a[q.back()]>=a[i]) q.pop_back();
            q.push_back(i);
            if (i > n && a[i - n] <= a[q.front()]) ++ans;
            if (!q.empty() && i - q.front() >= n - 1) q.pop_front();
        }
        printf("%d\n", ans);
    }
    return 0;
}

===
还有一些问题

单调队列的英文是什么
队尾去掉元素的时候等号可以不考虑吧，貌似那个文章有很多问题…
好像还有什么，突然忘了…

HDU4190 Distributing Ballot Boxes

Greenmoon55 — Sat, 14 Apr 2012 22:47:11 +0800

HDU 4190
举行大选，N (1<=N<=500,000) 个城市，一共 B(N<=B<=2,000,000) 个投票箱，每个城市人口为 ai(1<=ai<=5,000,000)，求怎么分配投票箱，使放选票最多的那个投票箱里的选票最少。

怎么办呢？xw想到的，二分答案就行…然后算投票箱个数。

120405

Greenmoon55 — Thu, 05 Apr 2012 22:33:05 +0800

这么快一天就过去了，今天大部分时间都在看Struts、Spring、Hibernate框架，结果还没弄好最简单的login…

原计划第七节上课之前看完，然后想晚饭之前看完，结果最后也没弄好…

我没搜到特别靠谱的教程，英文的搜到了一个，还是印度的网站，中午去图书馆借了本书，太厚完全没用。看了以前借的比较薄的书。感觉今天还是太着急了，虽然不是老师留的作业，我心里还是当成有个deadline那样写的，想着早点写完早点结束。欲速则不达= =

我对Java、JavaEE不是很感兴趣，以前觉得最有可能退掉这门课，老师的英语不错，很幸运进了非常靠谱的组，希望能在这学期多学点html, css, js等等等。。以前连css和html有什么关系都不知道，高中的时候觉得ul、li特别神秘…当时我怎么就不知道去搜搜呢…

Codeforces Round #104 (Div. 2)

Greenmoon55 — Fri, 16 Mar 2012 20:54:02 +0800

Codeforces Round #104 (Div. 2)
Editorial

比赛时做出三题

A略 B忘了题意，也略吧…

C Lucky Conversion
只需记录两字符串相应位置分别出现47和74的次数，输出这两个数的最大值

D Lucky Number 2
这个看了题解
想象删除所有相邻重复数字，可以得到形如47474747474747的串，所以 a3 与 a4 的差的绝对值一定小于等于1。然后分三种情况讨论：

a3 = a4，若 a1 = a3，则说明4不够多，生成的串以7开头，如74747，多余的7插入到最右面，多余的4放在最左边的4。。否则形如47474，多余的7插入到最右面的7，多余的4放在最左边。
a3 > a4，形如47474747，多余的4放在最前面，7放在最后面
a3 < a4，形如74747474，多余的4插入到1位置，7插入到最后面的7

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
    int a1, a2, a3, a4;
    cin >> a1 >> a2 >> a3 >> a4;
    if (abs(a3 - a4) > 1)
    {
        puts("-1");
        return 0;
    }
    string str;
    if (a3 == a4)
    {
        if ((a1 == a3 && a2 == a3) ||
        a1 < a3 || a2 < a3)
        {
            puts("-1");
            return 0;
        }
        // '4' is not enough
        if (a1 == a3)
        {
            for (int i = 0; i < a3; i++) str += "74";
            str += "7";
            if (a2 > a3 + 1)
            {
                string temp(a2 - a3 - 1, '7');
                str.append(temp);
            }
        }
        else // '4' is enough
        {
            for (int i = 0; i < a3; i++) str += "47";
            str += "4";
            if (a1 > a3 + 1)
            {
                /*
                string ( size_t n, char c );
                Content is initialized as a string formed
                by a repetition of character c, n times.
                */
                string temp(a1 - a3 - 1, '4');
                str.insert(0, temp);
            }
            if (a2 > a3)
            {
                string temp(a2 - a3, '7');
                str.insert(str.find_last_of('7'), temp);
            }
        }
    }
    else if (a3 < a4)
    {
        for (int i = 0; i < a4; i++) str += "74";
        if (a1 < a4 || a2 < a4)
        {
            puts("-1");
            return 0;
        }
        if (a1 > a4)
        {
            string temp(a1 - a4, '4');
            str.insert(1, temp);
        }
        if (a2 > a4)
        {
            string temp(a2 - a4, '7');
            str.insert(str.find_last_of('7'), temp);
        }
    }
    else // a3 > a4
    {
        for (int i = 0; i < a3; i++) str += "47";
        if (a1 < a3 || a2 < a3)
        {
            puts("-1");
            return 0;
        }
        if (a1 > a3)
        {
            string temp(a1 - a3, '4');
            str.insert(0, temp);
        }
        if (a2 > a3)
        {
            string temp(a2 - a3, '7');
            str.insert(str.find_last_of('7'), temp);
        }
    }
    cout << str << endl;
    return 0;
}

HDU4096 Universal Question Answering System

Greenmoon55 — Sun, 11 Mar 2012 14:27:07 +0800

其实是2010年上海赛区F题，现场读入数据就写了很久…交上去之后是个诡异的错误，现在忘了是啥错误了…

连边判断连通性即可。这个题比较坑人…输入数据就比较恶心，当时还不会sscanf。名词和动词可能一样，所以需要两个map来存，还可能直接问are cat cat?要输出Y…

BFS和DFS时间差不多…
http://acm.fudan.edu.cn 还有数据呢。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
//#include <assert.h>
using namespace std;
 
const int N = 205;
 
map<string, int> nmap, vmap;
int mapcount;
 
int getn(char* ch)
{
    if (!nmap.count(ch)) nmap[ch] = mapcount++;
    return nmap[ch];
}
 
int getv(char* ch)
{
    if (!vmap.count(ch)) vmap[ch] = mapcount++;
    return vmap[ch];
}
 
struct edge
{
    int v, next;
}e[N * N];
int head[N], edgenum;
 
void addedge(int a, int b)
{
    e[edgenum].v = b;
    e[edgenum].next = head[a];
    head[a] = edgenum++;
}
 
void workstatement(char *buf)
{
    char n1[20], n2[20];
    int a, b;
    if (sscanf(buf, "%s are %s", n1, n2) == 2)
    {
        a = getn(n1);
        b = getn(n2);
    }
    else if (sscanf(buf, "%s can %s", n1, n2) == 2)
    {
        a = getn(n1);
        b = getv(n2);
    }
    else if (sscanf(buf, "everything which can %s can %s", n1, n2) == 2)
    {
        a = getv(n1);
        b = getv(n2);
    }
    else if (sscanf(buf, "everything which can %s are %s", n1, n2) == 2)
    {
        a = getv(n1);
        b = getn(n2);
    }
    //else assert("workstatement error");
    addedge(a, b);
}
 
bool vis[N];
/*
bool dfs(int a, int b)
{
    vis[a] = true;
    if (a == b) return true;
    for (int i = head[a]; i != -1; i = e[i].next)
    {
        if (!vis[e[i].v])
        {
            if (dfs(e[i].v, b)) return true;
        }
    }
    return false;
}
*/
 
bool bfs(int a, int b)
{
    if (a == b) return true;
    int q[N], begin, end;
    begin = 0;
    end = 0;
    q[end++] = a;
    vis[a] = true;
    while (begin != end)
    {
        int x = q[begin++];
        for (int i = head[x]; i != -1; i = e[i].next)
        {
            if (!vis[e[i].v])
            {
                vis[e[i].v] = true;
                if (e[i].v == b) return true;
                q[end++] = e[i].v;
            }
        }
    }
    return false;
}
 
void workquestion(char* buf)
{
    char n1[20], n2[20];
    int a, b;
    if (sscanf(buf, "can everything which can %s %s", n1, n2) == 2)
    {
        a = getv(n1);
        b = getv(n2);
    }
    else if (sscanf(buf, "are everything which can %s %s", n1, n2) == 2)
    {
        a = getv(n1);
        b = getn(n2);
    }
    else if (sscanf(buf, "are %s %s", n1, n2) == 2)
    {
        a = getn(n1);
        b = getn(n2);
    }
    else if (sscanf(buf, "can %s %s", n1, n2) == 2)
    {
        a = getn(n1);
        b = getv(n2);
    }
    //else assert("workquestion error");
    memset(vis, 0, sizeof(vis));
    if (bfs(a, b)) printf("Y");
    else printf("M");
}
 
int read()
{
    char buf[200];
    int length;
    while (true)
    {
        gets(buf);
        length = strlen(buf);
 
        if (buf[length - 1] == '!') return 0;
        else
        if (buf[length - 1] == '.')
        {
            buf[length - 1] = 0;
            workstatement(buf);
        }
        else
        {
            buf[length - 1] = 0;
            workquestion(buf);
        }
    }
}
 
int main()
{
    //freopen("universal.in","r",stdin);
    int t;
    scanf("%d", &t);
    getchar();
 
    for (int tcase = 1; tcase <= t; ++tcase)
    {
        printf("Case #%d:\n", tcase);
        mapcount = 0;
        edgenum = 0;
        memset(head, -1, sizeof(head));
        nmap.clear();
        vmap.clear();
 
        while (read());
        printf("\n");
    }
    return 0;
}