2014
03-06

# Tetrahedral Stacks of Cannonballs

WALL.ETM, as he cleans up and organizes the depopulated Earth, has come upon some Civil War memorials. He is consolidating the cannonballs into one location, and decides to use pyramids with triangular bases rather than ones with square bases.

In Civil War memorials with cannons and stacks of cannonballs, the cannonballs were sometimes stacked as a four-sided pyramid, with the base as a square of cannonballs with n balls on each side. An alternative is to stack them in a three-sided pyramid, which is in fact one of the Platonic solids, a tetrahedron.

This tetrahedron of cannonballs has a base that is an equilateral triangle of cannonballs with n balls on each side. The number of balls in that triangle is given simply by adding together the numbers from 1 to n. On top of each layer (starting from the base) is a triangle with one less ball on each side, up to the top-most layer with a single ball.

Given the number of cannonballs on each side of the base, compute the total number of cannonballs in the entire tetrahedral stack.

The first line contains a single number n, giving the number of tetrahedral problems posed, for a maximum of 100 problems. Following that are exactly n lines, each with a single number giving the number of cannonballs on each side of the base for a tetrahedron of cannonballs, a number greater than 0 and less than 1000.

The first line contains a single number n, giving the number of tetrahedral problems posed, for a maximum of 100 problems. Following that are exactly n lines, each with a single number giving the number of cannonballs on each side of the base for a tetrahedron of cannonballs, a number greater than 0 and less than 1000.

6
1
2
3
5
27
999

1: 1 1
2: 2 4
3: 3 10
4: 5 35
5: 27 3654
6: 999 166666500

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

#define Maxn 300005
int median(int *a,int *b,int length)
{
if(length == 1) return a[0] < b[0] ? a[0] : b[0];
int mid = (length - 1)/2;
if(a[mid] == b[mid]) return a[mid];
if(a[mid] < b[mid])
{
return median(&a[length - mid -1],b,mid+1);
}
else
{
return median(a,&b[length - mid -1],mid+1);
}
}

int a[Maxn],b[Maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t;
int n;
int A,B,C,D;
int q;
int len;
scanf(" %d",&t);
while(t--)
{
scanf(" %d",&n);
for(int i=0; i<n; i++) scanf(" %d",&a[i]);
for(int i=0; i<n; i++) scanf(" %d",&b[i]);
scanf(" %d",&q);
for(int i=0; i<q; i++)
{
scanf(" %d %d %d %d",&A,&B,&C,&D);
len = B-A+1;
int ans = median(a+A,b+C,len);
printf("%d\n",ans);
}
}
return 0;
}

1. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯