专栏首页csxiaoyaoHDU 1030 纯数学 找规律

HDU 1030 纯数学 找规律

题目如下:大意是求两个三角形之间要通过多少条边

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);
	}
}

主要是分两个方向划分到同一个正三角形里面,然后中间的行数*2+头尾吧,头尾三角形分为正反两种,分情况讨论,也不怎么能说清楚啊。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1027 组合数学

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

    csxiaoyao
  • HDU 1085 母函数 硬币组合

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

    csxiaoyao
  • Angularjs和jQuery的ajax的请求区别

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

    csxiaoyao
  • 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...

    glm233
  • 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 可不仅仅只有这...

    IT可乐

扫码关注云+社区

领取腾讯云代金券