[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]A Anticlockwise Motion

Zarxdy34 posted @ 2017年10月11日 10:34 in Codeforces with tags 模拟 , 7 阅读

    求在一个32001*32001,中间为1,中心3*3为\[7     6     5\]\[8     1     4\]\[9     2     3\]的蛇形矩阵中,数字a,b的曼哈顿距离。

    题解:注意到从1开始向左下角延伸依次为9,25,49,81,121,即奇数的平方,由此来进行模拟。

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int a,b,ma,mb,xa,ya,xb,yb;
	scanf("%d%d",&a,&b);
	ma=1;
	while (a>ma*ma) ma+=2;
	xa=ya=16002-(ma+1)/2;
	if (ma*ma-ma<a) ya+=ma*ma-a;
	else {
		ya+=ma-1;
		if (ma*ma-ma*2+1<a) xa+=ma*ma-ma+1-a;
		else {
			xa+=ma-1;
			if (ma*ma-ma*3+2<a) ya-=ma*ma-ma*2+2-a;
			else {
				ya-=ma-1;
				xa-=ma*ma-ma*3+3-a;
			}
		}
	}
	mb=1;
	while (b>mb*mb) mb+=2;
	xb=yb=16002-(mb+1)/2;
	if (mb*mb-mb<b) yb+=mb*mb-b;
	else {
		yb+=mb-1;
		if (mb*mb-mb*2+1<b) xb+=mb*mb-mb+1-b;
		else {
			xb+=mb-1;
			if (mb*mb-mb*3+2<b) yb-=mb*mb-mb*2+2-b;
			else {
				yb-=mb-1;
				xb-=mb*mb-mb*3+3-b;
			}
		}
	}
	printf("%d\n",abs(xa-xb)+abs(ya-yb));
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1