第十二届北京师范大学程序设计竞赛决赛 C. 方(芳)格(哥)取数【思维】

xiaoxiao2021-02-28  80

C. 方(芳)格(哥)取数

Time Limit: 3000ms Memory Limit: 65536KB 64-bit integer IO format:  %lld      Java class name:  Main Submit  Status  PID: 34980

师大有三宝,妹子真不少,芳姐or芳哥,认路本领好!

众所周知,师大的芳哥带队本领高强,被众粉丝尊称为“地图”!芳哥对任意时刻,任意地点,任意地形都驾轻就熟,比如校园,密室,KTV,地铁,机场,山间,田野,丘陵等等等等。

嗯,有一天芳哥带着小伙伴来到一片丘陵,这片丘陵广袤无垠,层峦叠嶂,就像一个二维数组的样子,于是芳哥花了0.2333秒记住了这片土地。

芳姐将这片丘陵分为N*M个区域,然后她记住了每个区域的海拔。厉害吧~而且芳哥发现一个有趣的地方,就是对于同一个纬度,东边总是比西边高;对于同一个经度,南边总是比北边高

晚上在芳哥清点人数时发现小胖不见了,赶紧打电话给小胖,小胖也不知道自己现在在哪儿,只知道自己现在所在位置的海拔为K。芳哥太担心小胖以至于不能思考了,于是判断小胖是否还在这片丘陵的任务就落到了你的头上。值得欣慰的是,芳姐最多还能回答你N+M次询问,你可以询问她X,Y这个坐标的海拔是多少。如果你发现某个位置的海拔恰好等于小胖所在的海拔,那么你就认为小胖还在这片丘陵。

如果你发现小胖还在这片丘陵,输出YES,否则输出NO。如果你没在限定的次数内判断出来,芳哥让我给你一个WA。

Input

首先是一个整数T(T<=50),表示数据组数。

每组数据首先是三个整数N, M(1 <= N, M <= 1000), K(int范围),表示矩阵行数、列数和小胖所在的海拔。

然后对于你的程序的每个询问,结果也会作为输入返回,保证询问结果都在int内。

Output

在确定答案之前,每行输出一个询问,为两个整数X,Y,用空格隔开,表示询问A[X][Y]这个数是多少。

当你的程序能够判断结果时,按照题意输出一行结果 “YES” 或 “NO”(引号作为强调),如果答案正确将直接进入下一组数据,否则本次提交结果为WA。

注意不合法的询问或判断将直接导致WA、RE或TLE。

Hint

比如这片丘陵是这个样子的:

大小为4 x 3

1       9       99

2       19     100

30     300  3000

99     999  9999

如果小胖告诉你他所在的海拔为300。一种可能判断过程如下:

询问1 2

芳哥告诉你9

询问4 3

芳哥告诉你9999

询问3 2

芳哥告诉你300

这时你可以判断小胖还在这片丘陵上。输出YES即可。

注意:二维数组的下标从1开始。

===============================

特别鸣谢Liserious赞助题目名。

===============================

特别注意:

对于C/C++选手,请在每个输出后加上fflush(stdout);

对于JAVA选手,请在每个输出后加上System.out.flush();

对于Python选手,请在每个输出后加上sys.stdout.flush()。需要import sys。

对于Pascal选手,请在每个输出后加上Flush(StdOut),或者使用writeln()来输出。

思路:

我们以右上角作为起点,然后判定这个点是否为答案,如果不是,分成两种情况去讨论:

①如果这个点(x,y)的值大于我们要找的数的值,那么我们将y减少1,然后继续去判定。

②如果这个点(x,y)的值小于我们要找的数的值,那么我们将x增大1,然后继续去判定。

我们以右上角的点作为起点的话:

进行①操作可以确定当前列(第y列)是不会存在解的。因为这一列上的值都大于(x,y)这个位子的值。

进行②操作可以确定当前行(第x行)是不会存在解的。因为这一行左边的值都小于(x,y)这个位子的值。

所以我们最多需要n+m-1步就能知道这个矩阵中是否存在解。

Ac代码:

#include<stdio.h> #include<string.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,m,k; scanf("%d%d%d",&n,&m,&k); int posx=1,posy=m; int tmp=n+m-1; int ok=0; while(tmp--) { if(posx<1||posx>n||posy<1||posy>m)break; printf("%d %d\n",posx,posy);fflush(stdout); int val;scanf("%d",&val); if(val>k)posy--; else if(val<k)posx++; else { printf("YES\n");fflush(stdout); ok=1; break; } } if(ok==0) { printf("NO\n");fflush(stdout); } } }

转载请注明原文地址: https://www.6miu.com/read-55019.html

最新回复(0)