CF976B Lara Croft and the New Game 题解

前言

本文为本蒟蒻第一篇在洛谷题库过审的题解，写得不好请见谅。

题目简介

这是一道很考验思维的数学题。

题意

一个 $n \times m$ 的矩阵，从左上角 $(1,1)$ 出发，从上走到下之后按照蛇形方式走到终点 $(1,2)$ 。给定一个步数 $k$ ，求走 $k$ 步之后的坐标。

分析

通过数据量 $2\le n,m \le 10^9,0\le k \le n \cdot m$ 得知模拟小人走的路径是不可以的。因此，我们考虑常数时间复杂度的数学算法。

分析一下，可以得知小人走的路径分为两部分：从左上角走到左下角和从左下角走到终点两部分。

第一部分

走一步时，小人在 $(2,1)$ ；走两步时，小人在 $(3,1)$ ……走 $k(k<n)$ 步时，小人在 $(k+1,1)$ 。

所以我们可以得到第一部分的代码：

1	if(k<n) cout<<k+1<<" "<<1<<endl;

第二部分

第二部分的路径可以分为两种情况：从左往右走和从右往左走。设 $k_1=k-n$ ，那么 $k_1$ 即为第二部分走的步数。

通过分析 $k_1$ 我们可以得到一个规律：

当 $\left \lfloor \dfrac{k_1}{m-1} \right \rfloor$ 为偶数时，即为从左往右走，此时小人的坐标为 $(n-\dfrac{k_1}{m-1},k_1 \bmod (m-1)+2)$
当 $\left \lfloor \dfrac{k_1}{m-1} \right \rfloor$ 为奇数时，即为从右往左走，此时小人的坐标为 $(n-\dfrac{k_1}{m-1},m-k_1 \bmod (m-1))$

于是我们可以得到第二部分的代码：

1
2
3

long long k1=k-n;
if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;

完整代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long n,m,k;
	cin>>n>>m>>k;
	if(k<n) cout<<k+1<<" "<<1<<endl;
	else
	{
		long long k1=k-n;
		if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
		else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;
	}
	return 0;
}

最后提醒：注意数据范围，此题需要开 long long！

后记

1 2	if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl; // ^ I even wrote this 1 as 0! What am I thinking??????

1	//I spent about two and a half hours on this question.