NC54663. 走迷宫
描述
Tyl 喜欢走迷宫，他走迷宫的策略如下：
while(1){ if (前面没有障碍 && 前面还没有走过) 前进一步(); else if(右边没有障碍 && 右边还没有走过){ 右转(); 前进一步(); } else 原地愣住(); } 现在他位于一个 n*m 的迷宫中（一共 n 行，每行 m 格）的第 1 行的第 1 格，幸运的是这个迷宫除了边缘的墙壁以外没有别的障碍。
他最初总是位于迷宫第一行的第一格，并且朝着右边，现在他想知道 k 秒后他的坐标（上述策略中循环 1 次就是 1 秒）。如果位于第 x 行第 y 格，坐标就是 (x,y) 。
以 3*3 的迷宫为例，Tyl 依次走过的区域如下：
1 2 3 8 9 4 7 6 5
输入描述
第一行是一个整数 T(1<=T<=100)，表示数据组数。
对于每一组数据：
第一行是两个整数 n,m (1<=n,m<=50000) ，表示迷宫的尺寸。
第二行是一个整数 q(1<=q<=100000) 表示询问个数。
接下来 q 行，每行一个整数 k(0<=k<=1000000000) ，表示一次询问。
输出描述
对于每一次询问，输出一行信息：k 秒后 Tyl 的坐标。
示例1
输入:
1 2 2 5 0 1 2 3 4
输出:
(1,1) (1,2) (2,2) (2,1) (2,1)
C++14(g++5.4) 解法, 执行用时: 162ms, 内存消耗: 5652K, 提交时间: 2019-11-19 22:20:14
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int t,q;
long long k,m,n;
scanf("%d",&t);
while(t--)
{
scanf("%lld %lld",&n,&m);
scanf("%d",&q);
while(q--)
{
scanf("%lld",&k);
k++;
if(k>n*m)
k=n*m;
int M=min((n+1)/2,(m+1)/2);
long long l=1,h=M;
long long ans;
while(l<=h)
{
long long mid=(l+h)/2;
if(k>n*m-(n-2*(mid-1))*(m-2*(mid-1)))
{
ans=mid;
l=mid+1;
}
else
{
h=mid-1;
}
}
long long s=m-2*(ans-1);//lie
long long e=n-2*(ans-1);//hang
k-=n*m-s*e;
if(k<=s)
printf("(%lld,%lld)\n",ans,ans+k-1);
else if(k>s && k<=s+e-1)
{
k-=s;
printf("(%lld,%lld)\n",ans+k,ans+s-1);
}
else if(k>s+e-1 && k<=2*s+e-2)
{
k-=s+e-1;
printf("(%lld,%lld)\n",ans+e-1,ans+s-k-1);
}
else
{
k-=2*s+e-2;
printf("(%lld,%lld)\n",ans+e-1-k,ans);
}
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 135ms, 内存消耗: 5540K, 提交时间: 2019-11-18 17:39:58
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
void solve(ll n,ll m,ll k){
if(k>=n*m) k=n*m;
ll d=((n+m)*2-ceil(sqrt((n+m)*(n+m)*4-k*16)))/8;
d=min(min(n/2,m/2),d);
ll x=1+d,y=1+d;
k-=(d*(n+m)*4-d*d*8)/2;
n-=d*2,m-=d*2;
if(!k) y--;
else if(n==1) y+=k-1;
else if(m==1) x+=k-1;
else{
if(k<=m) y+=k-1;
else if(k<=n+m-1) y+=m-1,x+=k-m;
else if(k<=n+m*2-2) x+=n-1,y+=m*2+n-k-2;
else x+=(n+m)*2-k-3;
}
printf("(%d,%d)\n",x,y);
}
int main(){
int t,q;
ll n,m,k;
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&m);
scanf("%d",&q);
while(q--){
scanf("%lld",&k);
solve(n,m,k+1);
}
}
return 0;
}