uva 10161 Ant on a Chessboard

本文主要是介绍uva 10161 Ant on a Chessboard，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一个足够大的棋盘，有一只蚂蚁按照一定的方式走，问你在时间t，它的坐标是多少。走的方式是，一上，一右，一下，一右，二上，二左。。。。

如果我们从对角线看呢，1 3 7 13 21
公差是1 2 4 6 8 首项为1，公差为2的等差数列的前n项和。首先找出对应的位置，用Lower_bound（）找出的是位置pos，但是可能的位置是pos,pos-1，判断是这两个位置的哪一个，然后分奇数偶数处理。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=70000;
const int INF=2000000000;
int a[N];
void fun(int,int);
int main()
{int cnt=2;a[1]=1;while(1){a[cnt]=a[cnt-1]+(cnt-1)*2;if(a[cnt]>INF) break;cnt++;}int n;while(scanf("%d",&n)!=EOF){if(n==0) break;int pos=lower_bound(a+1,a+cnt,n)-a;if(a[pos]-n<pos) fun(pos,n-a[pos]);else if(n-a[pos-1]<pos-1) fun(pos-1,n-a[pos-1]);}return 0;
}
void fun(int x,int y)
{if(x%2){if(y>0) printf("%d %d\n",x-y,x);else printf("%d %d\n",x,x+y);}else{if(y>0) printf("%d %d\n",x,x-y);else printf("%d %d\n",x+y,x);}
}

这篇关于uva 10161 Ant on a Chessboard的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---