hdoj 2436 Collision Detection

Collision Detection

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1207    Accepted Submission(s): 367

Problem Description
      In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.
Here comes an interesting problem, given a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

 

Input
      The first line of input is the number of test cases.
Each test case contains two lines, the first line contains 24 integers X1, Y1, Z1, …, X8, Y8, Z8, representing the 8 vertexes of the cuboid. Vertexes are given in random order and you can make sure that all edges of the cuboid are parallel to coordinate axes; the second line contains 4 integers X,Y,Z,R representing the central point of the ball and its radius. All integers given are non-negative and will be less than 100000.

 

Output
      For each case output “Yes” Or “No” on a single line.

 

Sample Input
2
0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1
2 2 2 2
0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1
2 2 2 1

 

Sample Output
Yes
No

 

Source

 

Recommend
lcy   |   We have carefully selected several similar problems for you:  2437 2429 2433 2435 2428
真是日了狗了。。。
读错题wa到死。。。
英文差的原因?
我以为长方体是空心的。。
然后球是有可能在内部
我说我怎么写的那么麻烦,又是判断点,又是判断边,又是判断面。。。。
然后全推了重写。。。
又WA到死。。。
最后发现又是强制转化类型的问题。。。
如果变量是int 类型,即使一出赋值给long long ,在赋值之前的计算也会溢出。。。
所以不溢出的办法就是之前的int 就写成 long long 类型的。。。

离散化的三种方法(转载)

题意:

n棵树依次排好,每棵树都有一个高度,树的顶端有一只鸟。

猎人会打M枪,每一枪都能从高度为X的树上打下一只鸟,问每一枪打下的鸟是从  编号多少的树 上掉下来的

 

 

 

题解思路:

因为树的高度能达到(10^9)  而树的数量最多10^5  所以离散化   将所有高度为X的树离散化为 高度为第X高的树

有多种方法。

 

 

1  stl去重+set版:

 

  1. #include  
  2. #include  
  3. #include  
  4. #include  
  5. #include  
  6. #define MAXN  100050  
  7. using namespace std;  
  8. int h[MAXN];  
  9. int q[MAXN];  
  10. int s[MAXN*2];  
  11. set<int>ans[MAXN*2];  
  12. int main()  
  13. {  
  14.     int n,m,cnt;  
  15.     while(~scanf(“%d%d”,&n,&m))  
  16.     {  
  17.         cnt=0;  
  18.         for(int i=0;i
  19.         {  
  20.             scanf(“%d”,&h[i]);  
  21.             s[cnt++]=h[i];  
  22.         }  
  23.         for(int j=0;j
  24.         {  
  25.             scanf(“%d”,&q[j]);  
  26.             s[cnt++]=q[j];  
  27.         }  
  28.         sort(s,s+cnt);  
  29.         cnt=unique(s,s+cnt)-s;  
  30.         for(int i=0;i
  31.             ans[i].clear();  
  32.         for(int i=0;i
  33.         {  
  34.             int d=lower_bound(s,s+cnt,h[i])-s;  
  35.             ans[d].insert(i+1);  
  36.         }  
  37.         for(int j=0;j
  38.         {  
  39.             int d=lower_bound(s,s+cnt,q[j])-s;  
  40.             if(ans[d].empty())  
  41.                 printf(“-1n”);  
  42.             else  
  43.             {  
  44.                 printf(“%dn”,*ans[d].begin());  
  45.                 ans[d].erase(ans[d].begin());  
  46.             }  
  47.         }  
  48.     }  
  49.     return 0;  
  50. }  

 

 

 

 

土方法离散:

 

  1. #include  
  2. #include  
  3. #include  
  4. #include  
  5. #include  
  6. using namespace std;  
  7. #define maxn  100010  
  8. struct H  
  9. {  
  10.     int v,id;  
  11. }num[2*maxn];  
  12.   
  13. int w[2*maxn];  
  14. int vis[maxn<<1];  
  15.   
  16. bool cmp(H a,H b)  
  17. {  
  18.     return a.v
  19. }  
  20. vector <int> vc[maxn<<1];  
  21.   
  22. int main()  
  23. {  
  24.     int n,m;  
  25.     int cnt;  
  26.     while(~scanf(“%d%d”,&n,&m)){  
  27.         cnt=0;  
  28.         for(int i=0;i
  29.         {  
  30.             int xx;  
  31.             scanf(“%d”,&xx);  
  32.             num[i].v=xx;num[i].id=i;  
  33.         }  
  34.         for(int i=n;i
  35.         {  
  36.             int xx;scanf(“%d”,&xx);  
  37.             num[i].v=xx;num[i].id=i;  
  38.         }  
  39.         sort(num,num+n+m,cmp);  
  40.         int tot=0;w[num[0].id]=0;  
  41.         for(int i=1;i
  42.         {  
  43.             if(num[i].v==num[i-1].v){  
  44.                 w[num[i].id]=tot;  
  45.             }  
  46.             else w[num[i].id]=++tot;  
  47.         }  
  48.         memset(vis,0,sizeof(vis));  
  49.         for(int i=0;i
  50.         {  
  51.             vis[w[i]]++;vc[w[i]].push_back(i+1);  
  52.         }  
  53.         for(int i=n;i
  54.         {  
  55.             if(vis[w[i]]>0)  
  56.             {  
  57.                 int le=vc[w[i]].size()-vis[w[i]];  
  58.                 printf(“%dn”,vc[w[i]][le]);  
  59.                 vis[w[i]]–;  
  60.             }  
  61.             else printf(“-1n”);  
  62.         }  
  63.     }  
  64.     return 0;  
  65. }  

 

 

 

set+map:

 

  1. #include   
  2. #include   
  3. #include   
  4. #include   
  5. #include   
  6. #include 
      
  7. #include   
  8. #include   
  9. #include   
  10. #define read freopen(“q.in”,”r”,stdin)  
  11. #define LL long long  
  12. #define maxn 100005  
  13. using namespace std;  
  14. set<int>  mp[maxn];  
  15. map<int,int> c;  
  16. //http://www.2cto.com/kf/201108/100912.html  
  17. //http://blog.csdn.net/tyzhaoqi2004/article/details/6882660  
  18. int main()  
  19. {  
  20.     //read;  
  21.    int n,m;  
  22.    while(scanf(“%d%d”,&n,&m)!=EOF)  
  23.    {  
  24.        int i,j,q,x,t=0;  
  25.        for(i=1;i<=n;i++)  
  26.         mp[i].clear();  
  27.         c.clear();  
  28.        for(i=0;i
  29.        {  
  30.           scanf(“%d”,&x);  
  31.           if(!c[x])c[x]=++t;  
  32.           mp[c[x]].insert(i+1);  
  33.   
  34.          // cout<
  35.        }  
  36.        //for(i=1;i<=t;i++)cout<
  37.     //   cout<
  38.        for(i=0;i
  39.        {  
  40.           scanf(“%d”,&q);  
  41.           if(mp[c[q]].size()==0)  
  42.           {  
  43.              printf(“-1n”);  
  44.           }  
  45.           else  
  46.           {  
  47.             //  cout<
  48.              printf(“%dn”,*(mp[c[q]].begin()));  
  49.              mp[c[q]].erase(mp[c[q]].begin());  
  50.             // cout<
  51.           }  
  52.        }  
  53.   
  54.     }  
  55. }  

 

hdu 5233 Gunner II (bc #42 B) (离散化)

Gunner II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1433    Accepted Submission(s): 540

Problem Description

Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.

Jack will shot many times, he wants to know which bird will fall during each shot.

 

Input

There are multiple test cases (about 5), every case gives n, m in the first line, n indicates there are n trees and n birds, m means Jack will shot m times.

In the second line, there are n numbers h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

All input items are integers.

1<=n,m<=100000(10^5)

1<=h[i],q[i]<=1000000000(10^9)

 

Output

For each q[i], output an integer in a single line indicates the id of bird Jack shots down. If Jack can’t shot any bird, just output -1.

The id starts from 1.

 

Sample Input
5 5
1 2 3 4 1
1 3 1 4 2

 

Sample Output
1
3
5
4
2

Hint

Huge input, fast IO is recommended.

 

Source
因为一共才1E5的数据,而高度有1E9
所以考虑离散化
关于离散化的内容,这篇博客讲得很好。
http://blog.csdn.net/axuan_k/article/details/45954561
我是使用了第三种map+set的方法。。。
离散化大概是因为数据太大下表存不下。。。
然后map的key 值没有范围?所以实现了离散化(是这样嘛???)

还有一种写法,貌似要快一点,但是空间用的多一些:

bc #43(hdu 5265) pog loves szh II (单调性优化)

pog loves szh II

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2115    Accepted Submission(s): 609

Problem Description
Pog and Szh are playing games.There is a sequence with n numbers, Pog will choose a number A from the sequence. Szh will choose an another number named B from the rest in the sequence. Then the score will be (A+B) mod p.They hope to get the largest score.And what is the largest score?
 

 

Input
Several groups of data (no more than 5 groups,n1000).

For each case: 

The following line contains two integers,n(2n100000)p(1p2311)

The following line contains n integers ai(0ai2311)

 

 

Output
For each case,output an integer means the largest score.
 

 

Sample Input
4 4
1 2 3 0
4 4
0 0 2 2
 

 

Sample Output
3
2
 

 

Source
 

 

Recommend
hujie   |   We have carefully selected several similar problems for you:  5338 5337 5336 5335 5334 
对于读入的a[i] mod p后
对于任意 0=
所以a[i]+a[j]的结果只有两种情况,一种是 =p  <=2p-2   a[i]+a[j]-p 是答案
把a[i]升序排列,如果存在a[i]+a[j]>=p ,那么最大的一定是a[n-1]+a[n-2]
对于a[i]+a[j]小于p的,我们枚举i,找到最大的j,使得a[i]+a[j]
如果直接枚举O(N2)会超时
由于a[i]数组已经是有序的了
我们可以利用a[i]的单调性,从两边往中间找。
这样复杂度就是O(N)了
这个优化前几天刚遇到过。。。。
 

sgu 455. Sequence analysis (floyd 判圈算法,O(1)空间复杂度求循环节)

455. Sequence analysis

Time limit per test: 1 second(s)
Memory limit: 4096 kilobytes
input: standard
output: standard

Due to the slow ‘mod’ and ‘div’ operations with int64 type, all Delphi solutions for the problem 455 (Sequence analysis) run much slower than the same code written in C++ or Java. We do not guarantee that Delphi solution exists. 

You are given a sequence of signed 64-bit integers defined as follows:

  • x0 = 1,
  • ,

where

mod

is a remainder operator. All arithmetic operations are evaluated without overflow checking. Use standard “remainder” operator for programming languages (it differs from the mathematical version; for example  in programming, while  in mathematics).

Let’s call a sequence element xp repeatable if it occurs later in the sequence — meaning that there exists such qq > p, that xq = xp. The first repeatable element M of the sequence is such an element xmthat xm is repeatable, and none of the xp where p < m are repeatable.

Given AB and C, your task is to find the index of the second occurence of the first repeatable element M in the sequence if the index is less or equal to 2 · 106. Per definition, the first element of the sequence has index 0.

Input

The only line of input contains three signed 64-bit integers: AB and C (B > 0, C > 0).

Output

Print a single integer  — the index of the second occurence of the first repeatable member if it is less or equal to 2 · 106. Print -1 if the index is more than 2 · 106.

Example(s)

 

 

 

Note

In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The first repeatable element is 3. The second occurence of 3 has index 4.

In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The first repeatable element is 0. The second occurence of 0 has index 5.

In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The first repeatable element is 1. The second occurence of 1 has index 4.

 

比赛的时候逗了,往看空间限制了….

直接开了个set判重。。。显然MLE 了。。。

然后这道题的正解是 floyd判圈算法(也叫龟兔算法?)

http://www.cnblogs.com/oyking/p/4286916.html  这份题解讲得很详细

sgu 463 – Walking around Berhattan

K – Walking around Berhattan

Time Limit:250MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Description

As you probably know, Berhattan is a district of Berland’s largest city and it consists of equal square blocks. There are n block lines in the east-west direction and m block lines in the south-north direction. The map shows Berhattan as a rectangle with n rows and mcolumns, so there are nm blocks in total.

There are n+1 streets running parallel in the east-west direction (horizontally), and there are m+1 avenues running parallel in the south-north direction (vertically). Streets and avenues split the district into blocks and separate Berhattan from other districts of Berland. Each block in Berhattan is characterized by its beauty bij.

A pedestrian can walk only along streets and avenues. When the pedestrian walks along any of four sides of a block, we say he passes the block. Every time the pedestrian passes a block his satisfaction is increased by bij. If the pedestrian has already passed the block one or more times his satisfaction is increased only by bij/2 rounded down when he passes the block again.

You are given the map of Berhattan with the information about the blocks’ beauty and the pedestrian’s path along the streets and avenues. The path is given as a string containing letters ‘

‘, ‘

‘ and ‘

‘, where ‘

‘ means a 90 degree left turn, ‘

‘ means a 90 degree right turn, and ‘

‘ means walking one block forward by a street or avenue. Facing the east, the pedestrian starts his path in the north-west corner of Berhattan having zero satisfaction level. His path can cross itself and go along the same streets or avenues several times. Pedestrian’s satisfaction is increased every time he moves according to the rules described above.

Your task is to calculate the total satisfaction the pedestrian will get after finishing his route.


Picture of the sample test

Input

The first line of input contains two integers n and m (1 ≤ nm ≤ 100), where n is a number of block lines in Berhattan running in the east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 9) — the beauty of the corresponding block. The last line of input contains a path in the format specified above. The path consists of 1 up to 500 characters, inclusively. It is guaranteed that the given path doesn’t go outside Berhattan.

Output

Print a single integer to the output — the total pedestrian’s satisfaction.

Sample Input


 

 

简单模拟,n,m貌似给反了(两个地方给的不一致 )  害我wa了两发

SGU 456 Annuity Payment Scheme

D – Annuity Payment Scheme

Time Limit:500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Description

At the peak of the Global Economic Crisis BerBank offered an unprecedented credit program. The offering was so attractive that Vitaly decided to try it. He took a loan of s burles for m months with the interest rate of p percent. 

Vitaly has to follow the scheme of annuity payments, meaning that he should make fixed monthly payments — x burles per month. Obviously, at the end of the period he will pay m · x burles to the bank in total. 

Each of the monthly payments is divided by BerBank into two parts as follows:

  • The first part ai is used to pay off the percent p of the current debt. It’s clear that ai=s’ · p / 100 where s‘=s for the first month and equals to the remaining debt for each of the subsequent months.
  • The second part bi is used to pay off the current debt. The sum of all bi over the payment period is equal to s, meaning that the borrower needs to pay off the debt completely by decreasing it from s to 0 in m months.

BerBank uses calculations with floating-point numbers, and the value of x is uniquely determined by sm and p

For example, if s=100, m=2, p=50 then x=90. For the first month a1 = s‘ · p / 100 = s · p / 100 = 50 and b1 = 90 – 50 = 40. For the second month a2 = (100-40) · 50 / 100 = 30, so b2 = 90 – 30 = 60 and the debt is paid off completely. 

Your task is to help Vitaly and write a program that computes x given the values of sm and p.

Input

The single line of the input contains three integers sm and p (1 ≤ s ≤ 10 6, 1 ≤ m ≤ 120, 0 ≤ p ≤ 100).

Output

Output the single value of monthly payment x in burles. An absolute error of up to 10 -5 is allowed.

Sample Input

 

 

水题,推个公式出来,注意精度…一遍A

SPOJ AMR10F Cookies Piles

AMR10F – Cookies Piles

no tags 

 

The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns.  They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp.  The cookies were all of uniform size.  Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total? 
 
INPUT 
The first line contains the number of test cases T. T lines follow, one corresponding to each test case, containing 3 integers : N, A and D. 
 
OUTPUT
Output T lines, each line containing the required answer for the corresponding test case. 
 
CONSTRAINTS 
T <= 100 
1 <= N, A, D <=100 
 
SAMPLE INPUT 

1 1 1 
3 5 6 
2 1 2 
 
SAMPLE OUTPUT 

33 

 
EXPLANATION 
In the second test case the sequence is: 5, 11, 17 whose sum is 33.

 

水.

poj 2823 Sliding Window (单调队列)

Sliding Window
Time Limit: 12000MS Memory Limit: 65536K
Total Submissions: 46705 Accepted: 13485
Case Time Limit: 5000MS

Description

An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7  -1 3
 1 [3  -1  -3] 5  3  6  7  -3 3
 1  3 [-1  -3  5] 3  6  7  -3 5
 1  3  -1 [-3  5  3] 6  7  -3 5
 1  3  -1  -3 [5  3  6] 7  3 6
 1  3  -1  -3  5 [3  6  7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

Sample Output

Source

关于单调队列的讲解:

看这个问题:An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position.Your task is to determine the maximum and minimum values in the sliding window at each position.

也就是有一个数列a,要求你求数列b和c,b[i]是a[i]…a[i+w-1]中的最小值,c[i]是最大值。如果a是1,3,-1,-3,5,3,6,7,则b为-1,-3,-3,-3,3,3,c为3,3,5,5,6,7。

这个问题相当于一个数据流(数列a)在不断地到来,而数据是不断过期的,相当于我们只能保存有限的数据(sliding window中的数据,此题中就是窗口的宽度w),对于到来的查询(此题中查询是每时刻都有的),我们要返回当前滑动窗口中的最大值最小值。注意,元素是不断过期的。

解决这个问题可以使用一种叫做单调队列的数据结构,它维护这样一种队列:

a)从队头到队尾,元素在我们所关注的指标下是递减的(严格递减,而不是非递增),比如查询如果每次问的是窗口内的最小值,那么队列中元素从左至右就应该递增,如果每次问的是窗口内的最大值,则应该递减,依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾,元素对应的时刻(此题中是该元素在数列a中的下标)是递增的,但不要求连续,这是为了保证最左面的元素总是最先过期,且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列,首先,只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢?无非是处理插入和查询两个操作。

对于插入,由于性质b,因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立,即元素在我们关注的指标下递减,从队尾插入新元素的时候可能要删除队尾的一些元素,具体说来就是,找到第一个大于(在所关注指标下)新元素的元素,删除其后所有元素,并将新元素插于其后。因为所有被删除的元素都比新元素要小,而且比新元素要旧,因此在以后的任何查询中都不可能成为答案,所以可以放心删除。

对于查询,由于性质b,因此所有该时刻过期的元素一定都集中在队头,因此利用查询的时机删除队头所有过期的元素,在不含过期元素后,队头得元素就是查询的答案(性质a),将其返回即可。

由于每个元素都进队出队一次,因此摊销复杂度为O(n)。

POJ2823就是上面描述的那道题。

http://www.cnblogs.com/Jason-Damon/archive/2012/04/19/2457889.html

讲得很好.我认为重点的地方加颜色了.

如果要找最大值,那么比新加入的元素小且旧的元素是不可能成为答案的,可以放心删去!

理解了这句话就理解了单调队列…

上面那个博客将得是挺好,只是代码写得略丑.

自己按照思想写了个还看得过去的

更新一个双端队列实现的(为毛交g++会Tle,交c++才能过2333):

(bc #45) A – Dylans loves numbers (hdu 5272)

快要炸了..
tle成狗
因为是tle,看了下自己没有写cin cout,估计就是算法的问题…
我是先存了二进制的每一位到数组,然后扫一遍…
嗯,这都tle…
那我不存不扫,直接记录当前二进制位和之前二进制位..
logn的复杂度总可以了吧啊?
还TLE……….
嗯,其实已经发现 n是小于等于1e18的,没开long long
但是一位没开long long 会是wa…就没理…
之后实在黔驴技穷,改了下,竟然过了…
然后想明白了.
因为存二进制的时候有一个while
没开long long 的话就炸了,不知道读进去的是什么,while就出不来,于是就tle了.T T
果然太年轻.

codeforces 442C. Artem and Array

C. Artem and Array
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Artem has an array of n positive integers. Artem decided to play with it. The game consists of n moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets min(a, b) points, where a and b are numbers that were adjacent with the removed number. If the number doesn’t have an adjacent number to the left or right, Artem doesn’t get any points.

After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of elements in the array. The next line contains n integers ai(1 ≤ ai ≤ 106) — the values of the array elements.

Output

In a single line print a single integer — the maximum number of points Artem can get.

Sample test(s)
input

output

input

output

input

output

 

 

并不会做.

接触了一个交单调栈的东西…

又是单调栈又是单调队列

是时候仔细了解下了.

cf 442B Andrey and Problem

B. Andrey and Problem
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Andrey needs one more problem to conduct a programming contest. He has n friends who are always willing to help. He can ask some of them to come up with a contest problem. Andrey knows one value for each of his fiends — the probability that this friend will come up with a problem if Andrey asks him.

Help Andrey choose people to ask. As he needs only one problem, Andrey is going to be really upset if no one comes up with a problem or if he gets more than one problem from his friends. You need to choose such a set of people that maximizes the chances of Andrey not getting upset.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of Andrey’s friends. The second line contains n real numbers pi(0.0 ≤ pi ≤ 1.0) — the probability that the i-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.

Output

Print a single real number — the probability that Andrey won’t get upset at the optimal choice of friends. The answer will be considered valid if it differs from the correct one by at most 10 - 9.

Sample test(s)
input

output

input

output

Note

In the first sample the best strategy for Andrey is to ask only one of his friends, the most reliable one.

In the second sample the best strategy for Andrey is to ask all of his friends to come up with a problem. Then the probability that he will get exactly one problem is 0.1·0.8 + 0.9·0.2 = 0.26.

 

可以选1个,可以选2个,选i个….

但是选哪i个,似乎还要枚举…这样计算起来很麻烦

但是再一看,很容易发现,选i个概率最大的情况一定是选本身概率最大的i个的情况

那么我们只需要枚举选的个数,取每种情况的最大值就好了.

cf 443B Kolya and Tandem Repeat

B. Kolya and Tandem Repeat
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kolya got string s for his birthday, the string consists of small English letters. He immediately added k more characters to the right of the string.

Then Borya came and said that the new string contained a tandem repeat of length l as a substring. How large could l be?

See notes for definition of a tandem repeat.

Input

The first line contains s (1 ≤ |s| ≤ 200). This string contains only small English letters. The second line contains number k (1 ≤ k ≤ 200) — the number of the added characters.

Output

Print a single number — the maximum length of the tandem repeat that could have occurred in the new string.

Sample test(s)
input

output

input

output

input

output

Note

A tandem repeat of length 2n is string s, where for any position i (1 ≤ i ≤ n) the following condition fulfills: si = si + n.

In the first sample Kolya could obtain a string aabaab, in the second — aaabbbbbb, in the third — abracadabrabracadabra.

 

大力出奇迹2333

 

(BC 一周年) hdu 5312 Sequence

Sequence

 

 Accepts: 25

 

 Submissions: 1442
 Time Limit: 2000/2000 MS (Java/Others)

 

 Memory Limit: 262144/262144 K (Java/Others)
问题描述

输出描述

输入样例

输出样例

比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15…..)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好:

这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k (k > 2)k(k>2), 使得(m – k) mod 6 = 0(mk)mod6=0即可.

证明如下: 3n(n-1)+1 = 6(n*(n-1)/2)+13n(n1)+1=6(n(n1)/2)+1, 注意到n*(n-1)/2n(n1)/2是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要kk个, 那么显然m=6(km=6(k个三角形数的和)+k)+k, 由于k ge 3k3, 只要m-kmk是6的倍数就一定是有解的.

事实上, 打个表应该也能发现规律.

另外还有一点,特判一个和两个的情况时,一个的好判断,扫一遍就好了

两个的话,由于这个数列是递增的,我们可以从两边往中间,算是一个不错的优化,具体见代码.

三角形数_百度百科

它有一定的规律性,排列如下(构成图),像上面的1、3、6、10、15等等这些能够表示成三角形的形状的总数量的数,叫做三角形数。
一定数目的点或圆在等距离的排列下可以形成一个等边三角形,这样的数被称为三角形数。比如10个点可以组成一个等边三角形,因此10是一个三角形数:
x
x x
x x x
x x x x
x x x x x
开始个18个三角形数是1、3、6、10、15、21、28、36、45、55、66、78、91、105、120、136、153、171……(OEIS中的数列A000217)

第n个三角形数的公式是

或者

第n个三角形数是开始的n个自然数的和。
所有大于3的三角形数都不是质数
开始的n个立方数的和是第n个三角形数的平方(举例:1 + 8 + 27 + 64 = 100 =102)
所有三角形数的倒数之和是2。
任何三角形数乘以8再加1是一个平方数
一部分三角形数(3、10、21、36、55、78……)可以用以下这个公式来表示:n × (2n + 1);而剩下的另一部分(1、6、15、28、45、66……)则可以用n × (2n – 1)来表示。

一种检验正整数x是否三角形数的方法,是计算:

如果n是整数,那么x就是第n个三角形数。如果n不是整数,那么x不是三角形数。这个检验法是基于恒等式8Tn + 1 = S2n + 1.
特殊的三角形数
55、5,050、500,500、50,005,000……都是三角形数。
第11个三角形数(66)、第1111个三角形数(617,716)、第111,111个三角形数(6,172,882,716)、第11,111,111个三角形数(61,728,399,382,716)都是回文式的三角形数,但第111个、第11,111个和第1,111,111个三角形数不是。
和其他数的关系
四面体数是三角形数在立体的推广。
两个相继的三角形数之和是平方数。
三角平方数是同时为三角形数和平方数的数。
三角形数属於一种多边形数
所有偶完美数都是三角形数。
任何自然数是最多三个三角形数的和。高斯发现了这个规律。他在1796年7月10日在日记中写道:EYPHKA! num = Δ + Δ + Δ
任意一个自然数最多只需要3个三角形数即可表示.