Delta-wave

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4938    Accepted Submission(s): 1875

Problem Description

A triangle field is numbered with successive integers in the way shown on the picture below.

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller's route.  Write the program to determine the length of the shortest route connecting cells with numbers N and M.

Input

Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).

Output

Output should contain the length of the shortest route.

Sample Input

6 12

Sample Output

3

#include<stdio.h>
#include<math.h>
void main()
{
int m,n,h1,h2,x,y,temp,num,p1,p2;
while(scanf("%d %d",&m,&n)!=EOF)
{
h1=sqrt((float)m);
if(h1!=sqrt((float)m))
h1++;
h2=sqrt((float)n);
if(h2!=sqrt((float)n))
h2++;
x=m-(h1-1)*(h1-1);
y=n-(h2-1)*(h2-1);
p1=(h1*h1-m)/2+1;
p2=(h2*h2-n)/2+1;
if(h1>h2)
{
temp=h2;
h2=h1;
h1=temp;
temp=x;
x=y;
y=temp;
temp=p1;
p1=p2;
p2=temp;
}
num=(h2-h1-1)*2;
if(x%2==0)
num++;
if(y%2==0&&x<=y&&p1<=p2)
num++;
else
num+=2;
if(x>y)
num+=x-y;
if(p1>p2)
num+=y-2*(h2-p1)-1;
printf("%d\n",num);
}
}

0 条评论

• HDU 1027 组合数学

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Ot...

• HDU 1085 母函数 硬币组合

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Ot...

• Angularjs和jQuery的ajax的请求区别

Angularjs和jQuery的ajax的请求是不同的。在jquery中，官方文档解释contentType默认是application/x-www-fo...

• kafka学习二 -发送消息

从源码中我们发现在Sender的run方法中，并没有涉及到append追加操作。因此可以看到源码中，如果消息收集器中的消息收集结果为空或者新的消息批次已经创建好...

• 浅析PHP7 的垃圾回收机制

垃圾回收机制是一种动态存储分配方案。它会自动释放程序不再需要的已分配的内存块。 自动回收内存的过程叫垃圾收集。垃圾回收机制可以让程序员不必过分关心程序内存分配，...

• Codeforces Beta Round #8 A. Train and Peter

Peter likes to travel by train. He likes it so much that on the train he falls a...

• Codeforces 660C-Hard Process【尺取法练习】

C. Hard Process time limit per test 1 second memory limit per test 256 megabyt...

• 一种注册表沙箱的思路、实现——研究Reactos中注册表函数的实现4

今天为了KPI，搞了一天的PPT，搞得恶心想吐。最后还是回到这儿，这儿才是我的净土，可以写写我的研究。

• B - They Are Everywhere CodeForces - 701C

题目链接 Sergei B., the young coach of Pokemons, has found the big house which cons...

• Nginx（一）------简介与安装

说到 Nginx ，可能大家最先想到的就是其负载均衡以及反向代理的功能。没错，这也是当前使用 Nginx 最频繁的两个功能，但是 Nginx 可不仅仅只有这...