HDU 2446 Shell Pyramid(二分查找 数学)

2023-10-19 03:20

本文主要是介绍HDU 2446 Shell Pyramid(二分查找 数学),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2446


Problem Description
In the 17th century, with thunderous noise, dense smoke and blazing fire, battles on the sea were just the same as those in the modern times. But at that time, the cannon ,were extremely simple. It was just like an iron cylinder, with its rearward end sealed and forward end open. There was a small hole at the rearward end of it, which was used to install the fuse. The cannons on the warships were put on small vehicles which had four wheels and the shells were iron spheres with gunpowder in them.

At that time, it was said that there was an intelligent captain, who was also a mathematician amateur. He liked to connect everything him met to mathematics. Before every battle, he often ordered the soldiers to put the shells on the deck and make those shells to form shell pyramids.

Now let's suppose that a shell pyramid has four layers, and there will be a sequence of ordinal numbers in every layer. They are as the following figure:



In the figure, they are the first layer, the second layer, the third layer and the fourth layer respectively from the left to the right.

In the first layer, there is just 1 shell, and its ordinal number is 1. In the second layer, there are 3 shells, and their ordinal numbers are 1, 2, and 3. In the third layer, there are 6 shells, and their ordinal numbers are 1, 2, 3, 4, 5, and 6. In the fourth layer, there are 10 shells, and their ordinal numbers are shown in the figure above.

There are also serial numbers for the whole shell pyramid. For example, the serial number for the third shell in the second layer is 4, the serial number for the fifth shell in the third layer is 9, and the serial number for the ninth shell in the fourth layer is 19.

There is also a interrelated problem: If given one serial number s, then we can work out the s th shell is in what layer, what row and what column. Assume that the layer number is i, the row number is j and the column number is k, therefore, if s=19, then i=4, j=4 and k=3.

Now let us continue to tell about the story about the captain.
A battle was going to begin. The captain allotted the same amount of shells to every cannon. The shells were piled on the deck which formed the same shell pyramids by the cannon. While the enemy warships were near, the captain ordered to fire simultaneously. Thunderous sound then was heard. The captain listened carefully, then he knew that how many shells were used and how many were left. 

At the end of the battle, the captain won. During the break, he asked his subordinate a question: For a shell pyramid, if given the serial number s, how do you calculate the layer number i, the row number j and column number k? 
Input
First input a number n,repersent n cases.For each case there a shell pyramid which is big enough, a integer is given, and this integer is the serial number s(s<2^63). There are several test cases. Input is terminated by the end of file.
Output
For each case, output the corresponding layer number i, row number j and column number k.
Sample Input
  
2 19 75822050528572544
Sample Output
  
4 4 3 769099 111570 11179
Source
2008 Asia Regional Harbin



题意:

叠金字塔,最顶层数量是1,第二层数量是3,之后每一层的数量都是上面一层的数量加当前层数的值啦。一层金字塔有1个球,两层金字塔有1+3 = 4个球,三层金字塔就有1+3+6 = 10个的球。

现在给出一个编号s,问它在金字塔中的第几层,第几行,第几列。

例如19,在第四层,第四行,第三列。

PS:

首先打表出每一座金字塔的数量, 和第n座金字塔的编号(也就是前n座金字塔共有的数量);

然后先二分查找出给出的编号所在的金字塔,然后再一次二分找出给出的编号在当前金字塔的哪一行哪一列!

代码如下:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64 LL;#define N 2000017
LL p[N] = {0}, sn[N] = {0};
//a每一个位置的数,b:SnLL findd1(LL n)
{LL s = 1, e = N, mid;while(s < e){mid = (s+e)/2;if(sn[mid] < n)s = mid+1;else if(sn[mid] > n)e = mid-1;elsereturn mid;}return s;
}LL findd2(LL n, LL endd)
{LL s = 1, e = endd, mid;while(s < e){mid = (s+e)/2;if(p[mid] < n)s = mid+1;else if(p[mid] > n)e = mid-1;elsereturn mid;}return s;
}int main()
{LL t;LL n;memset(p,0,sizeof(p));memset(sn,0,sizeof(sn));for(int i = 1; i < N; i++)//每一堆{p[i] = p[i-1]+i;}for(int i = 1; i < N; i++)//Sn{sn[i] = p[i]+sn[i-1];}/* for(int i = N-10; i < N; i++){printf("%I64d\n",sn[i]);}*///2^63 = 9223372036854775808scanf("%I64d",&t);while(t--){scanf("%I64d",&n);LL weizhi = findd1(n);// printf("pos:%I64d\n",weizhi);if(sn[weizhi] < n)weizhi+=1;LL tt = n-sn[weizhi-1];//本堆的个数LL r = findd2(tt,weizhi);//printf("R:%I64d\n",r);if(p[r] == tt){printf("%I64d %I64d %I64d\n",weizhi,r,r);}else{if(p[r] < tt)r++;LL c = tt - p[r-1];printf("%I64d %I64d %I64d\n",weizhi,r,c);}/*else{LL c = tt - p[r-1];printf("%I64d %I64d %I64d\n",weizhi,r,c);}*/}return 0;
}/*
2
14
15
*/


这篇关于HDU 2446 Shell Pyramid(二分查找 数学)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/236960

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=