Uva10161 Ant on a Chessboard
Uva10161 Ant on a Chessboard
10161 Ant on a Chessboard
One day, an ant called Alice came to an M*M chessboard. She wanted to go around all the grids. So she began to walk along the chessboard according to this way: (you can assume that her speed is one grid per second) At the first second, Alice was standing at (1,1). Firstly she went up for a grid, then a grid to the right, a grid downward. After that, she went a grid to the right, then two grids upward, and then two grids to the left¡ in a word, the path was like a snake. For example, her first 25 seconds went like this: ( the numbers in the grids stands for the time when she went into the grids)
见下图
At the 8-th second , she was at (2,3), and at 20-th second, she was at (5,4). Your task is to decide where she was at a given time (you can assume that M is large enough).
Input Input file will contain several lines, and each line contains a number N (1 ≤ N ≤ 2∗109), which stands for the time. The file will be ended with a line that contains a number ‘0’.
Output
For each input situation you should print a line with two numbers (x,y), the column and the row number, there must be only a space between them.
Sample Input
8 20 25 0
Sample Output
2 3 5 4 1 5
找出对角线的规律后,进行计算
/*
Author:ZCC;
Time:2015-6-4
Solve:对角线成差成等差数列。所以能够算出通项公式A_n=n*n-n+1
*/
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int maxn=44725;
typedef long long LL;
LL a[maxn];
int main(){
//freopen("Text//in.txt","r",stdin);
for(int i=0;i<maxn;i++){
a[i]=(LL)i*i-i+1;
// if(a[i]>2000000000){cout<<i<<endl;break;}
}
LL n;
while(scanf("%lld",&n)&&n){
int pos=lower_bound(a+1,a+maxn,n)-a;
// cout<<"**"<<pos<<"**"<<endl;
int x=pos,y=pos;
if(pos&1){
if(n>=a[pos]-pos+1){
while(n<a[pos])n++,y--;
}
else {
x--;
y=pos-1;
pos--;
while(n>a[pos])n--,y--;
}
}
else {
if(n>=a[pos]-pos+1){
while(n<a[pos])n++,x--;
}
else {
y--;
x=pos-1;
pos--;
while(n>a[pos])n--,x--;
}
}
printf("%d %d\n",x,y);
}
return 0;
}
相关文章
- [Remoting FAQ]Loading a Remoting Host On IIS得到BadImageFormatException
- check user valid on JQuery
- Spark On K8S与Spark On YARN方案相比之劣势
- 如何在 SAP BTP ABAP 编程环境里直接调用 ABAP On-Premises 系统的 RFC 函数
- SAP concur image download on request
- Atitit s2018.6 s6 doc list on com pc.docx Atitit s2018.6 s6 doc list on com pc.docx Aitit algo fix 算法系列补充.docx Atiitt 兼容性提示的艺术 attilax总结.docx Atitit 应用程序容器化总结 v2 s66.docx Atitit file cms api
- 联机事务处理OLTP(on-line transaction processing)和联机分析处理OLAP(On-Line Analytical Processing)
- 【文献学习】Channel Estimation Method Based on Transformer in High Dynamic Environment
- DB2 11.5.7.0 Installation Guide on Linux
- 基于JAVA实现的WEB端UI自动化 - WebDriver框架篇 - ant使用 - ant安装、环境变量配置、ant实例及运行Ant Build 出现问题的解决方法