Not a Triangle

All submissions for this problem are available.

You have N (3 ≤ N ≤ 2,000) wooden sticks, which are labeled from 1 to N. The i-th stick has a length of L_i (1 ≤ L_i ≤ 1,000,000). Your friend has challenged you to a simple game: you will pick three sticks at random, and if your friend can form a triangle with them (degenerate triangles included), he wins; otherwise, you win. You are not sure if your friend is trying to trick you, so you would like to determine your chances of winning by computing the number of ways you could choose three sticks (regardless of order) such that it is impossible to form a triangle with them.

Input

The input file consists of multiple test cases. Each test case starts with the single integer N, followed by a line with the integers L₁, ..., L_N. The input is terminated with N = 0, which should not be processed.

Output

For each test case, output a single line containing the number of triples.

Example

Input:
3
4 2 10
3
1 2 3
4
5 2 9 6
0

Output:
1
0
2

For the first test case, 4 + 2 < 10, so you will win with the one available triple. For the second case, 1 + 2 is equal to 3; since degenerate triangles are allowed, the answer is 0.

**********************************************************code/**********************************************************************

#include<iostream>

#include<algorithm>

using namespace std;

int arr[100001];

  int b_srch(int a,int b,int val)

 {

  if(a==b) return a;

  else if(a+1==b) return a;

  else

   {

    int mid=(a+b)/2;

     if(arr[mid]>val)

      b_srch(a,mid-1,val);

      else 

      b_srch(mid+1,b,val);

     

   }

     

  return 0; 

 }

 int main()

  {

  int t;

  cin>>t;

      while(t--)

      {

      int n;

       cin>>n;

     

          for(int i=0;i<n;i++)

            cin>>arr[i];

            int ans=0;

              for(int i=0;i<n-1;i++)

{

 for(int j=i+1;j<n-1;j++)

  {

   int val=arr[i]+arr[j];

   int temp= b_srch(j+1,n-1,val);

    if(arr[temp]==val) temp+=1;

    else if(arr[temp]<val) temp+=1;

     ans+=(n-temp);

  }

} 

      }

      return 0;

  }

A. Rank List

A. Rank List

Another programming contest is over. You got hold of the contest's final results table. The table has the following data. For each team we are shown two numbers: the number of problems and the total penalty time. However, for no team we are shown its final place.

You know the rules of comparing the results of two given teams very well. Let's say that team a solved pa problems with total penalty time ta and team b solved pb problems with total penalty time tb. Team a gets a higher place than team b in the end, if it either solved more problems on the contest, or solved the same number of problems but in less total time. In other words, team a gets a higher place than team b in the final results' table if either pa > pb, or pa = pb and ta < tb.

It is considered that the teams that solve the same number of problems with the same penalty time share all corresponding places. More formally, let's say there is a group of x teams that solved the same number of problems with the same penalty time. Let's also say that yteams performed better than the teams from this group. In this case all teams from the group share places y + 1, y + 2, ..., y + x. The teams that performed worse than the teams from this group, get their places in the results table starting from the y + x + 1-th place.

Your task is to count what number of teams from the given list shared the k-th place.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 50). Then n lines contain the description of the teams: the i-th line contains two integers pi and ti (1 ≤ pi, ti ≤ 50) — the number of solved problems and the total penalty time of the i-th team, correspondingly. All numbers in the lines are separated by spaces.

Output

In the only line print the sought number of teams that got the k-th place in the final results' table.

Sample test(s)

input

7 2
4 10
4 10
4 10
3 20
2 1
2 1
1 10

output

3

input

5 4
3 1
3 1
5 3
3 1
3 1

output

4

Note

The final results' table for the first sample is:

• 1-3 places — 4 solved problems, the penalty time equals 10
• 4 place — 3 solved problems, the penalty time equals 20
• 5-6 places — 2 solved problems, the penalty time equals 1
• 7 place — 1 solved problem, the penalty time equals 10

The table shows that the second place is shared by the teams that solved 4 problems with penalty time 10. There are 3 such teams.

The final table for the second sample is:

• 1 place — 5 solved problems, the penalty time equals 3
• 2-5 places — 3 solved problems, the penalty time equals 1

The table shows that the fourth place is shared by the teams that solved 3 problems with penalty time 1. There are 4 such teams

************************************

#include<iostream>

#include<vector>

using namespace std;

#include<algorithm>

int dp[10001];

int main()

 {

  int n,p;

  cin>>n>>p;

  vector<pair<int,int> >v;

    for(int i=0;i<n;i++)

     {

      int a,b;

      cin>>a>>b;

      v.push_back(make_pair(a,b));

     }

   //  sort(v.begin(),v.end());

   //  reverse(v.begin(),v.end());

   for(int i=0;i<n;i++)

    {

        for(int j=0;j<n;j++)

        {

            if(v[i].first>v[j].first)

            {

                swap(v[i].first,v[j].first);

                swap(v[i].second,v[j].second);

            }

            else

            if(v[i].first==v[j].first)

                if(v[i].second<v[j].second)

                    swap(v[i].second,v[j].second);

        }

    }

   /*  cout<<"sorted order \n";

      for(int i=0;i<n;i++)

       {

        cout<<v[i].first<<" "<<v[i].second<<endl;

       }*/

     int c=1;

     dp[0]=1;

     int last_index=0;

  for(int i=1;i<n;i++)

   {

    //cout<<"i "<<i<<endl;

    //cout<<"c "<<c<<endl;

    int f=0;

    if(v[i].first ==v[i-1].first && v[i].second==v[i-1].second)

    {

    //cout<<"in if \n";

    // cout<<"i "<<i<<" and "<<i-1<<"matched"<<endl;

    c++;

    }

     else

     {

     // cout<<"in else \n";

      //f=1;

     // cout<<"i "<<i<<" and "<<i-1<<" not matched"<<endl;

      for(int ll=last_index;ll<i;ll++)

      {

      dp[ll]=c;

      }

      c=1;

      last_index=i;

     }

     if(i==n-1)

     {

     

      for(int ll=last_index;ll<=i;ll++)

      {

      dp[ll]=c;

      }

      c=1;

      last_index=i;

     }

   }

  // dp[n-1]=c;

  /* cout<<"dp table ";

     for(int i=0;i<n;i++)

      cout<<dp[i]<<" ";*/

   cout<<dp[p-1]<<endl;    

  return 0;

 }

Vanya and Lanterns

B. Vanya and Lanterns

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th lantern is at the point ai. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns.

Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?

Input

The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 109) — the number of lanterns and the length of the street respectively.

The next line contains n integers ai (0 ≤ ai ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.

Output

Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Sample test(s)

input

7 15
15 5 3 7 9 14 0

output

2.5000000000

input

2 5
2 5

output

2.0000000000

Note

Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment[3, 5]. Thus, the whole street will be lit.

#include<iostream>

using namespace std;

#include<bits/stdc++.h>

typedef long long int lli;

int main()

 {

  lli n,dis;

   cin>>n>>dis;

  lli arr[n+10];

  for(int i=0;i<n;i++)

    cin>>arr[i];

  double  left=0;

  double right =dis;

  sort(arr,arr+n);

  double ans=dis;

   while(right-left>0.0000000001)

    {

     double mid=((double)left+(double)right)/2.0;

       //printf("%.9lf\n",mid);

     int f=0;

     if(double(arr[0]-mid>0.0)) f=1;

     

      for(int i=0;i<n-1;i++)

       {

        if(f==1) break;

        if(((double)arr[i]+mid-(double(arr[i+1])-mid)>=0.0) )

        {

        // cout<<"cover range forard"<<(double)arr[i]+mid<<" backward "<<(double(arr[i+1])-mid);

        continue;

        }

       

        else

        {

        f=1;

        break;

        }

       }

       if((double)arr[n-1]+mid<dis) f=1;

       if(f==1)

        {

        left=mid+(0.00000000001);

        }

        else

        {

        if(ans-mid>0.0) ans=mid;

        right=mid;

        }

    }

     //cout<<ans<<endl;

     printf("%.9lf\n",ans);

 }

Vasya and Beautiful Arrays

C. Vasya and Beautiful Arrays

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya's got a birthday coming up and his mom decided to give him an array of positive integers a of length n.

Vasya thinks that an array's beauty is the greatest common divisor of all its elements. His mom, of course, wants to give him as beautiful an array as possible (with largest possible beauty). Unfortunately, the shop has only one array a left. On the plus side, the seller said that he could decrease some numbers in the array (no more than by k for each number).

The seller can obtain array b from array a if the following conditions hold: bi > 0; 0 ≤ ai - bi ≤ k for all 1 ≤ i ≤ n.

Help mom find the maximum possible beauty of the array she will give to Vasya (that seller can obtain).

Input

The first line contains two integers n and k (1 ≤ n ≤ 3·105; 1 ≤ k ≤ 106). The second line contains n integers ai (1 ≤ ai ≤ 106) — arraya.

Output

In the single line print a single number — the maximum possible beauty of the resulting array.

Sample test(s)

input

6 1
3 6 10 12 13 16

output

3

input

5 3
8 21 52 15 77

output

7

Note

In the first sample we can obtain the array:

3 6 9 12 12 15

In the second sample we can obtain the next array:

7 21 49 14 77

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int main()

 {

  int n,k;

  cin>>n>>k;

    int arr[n+10];

    int min=INT_MAX;

     for(int i=0;i<n;i++)

      {

      cin>>arr[i];

      

     

      }

        sort(arr,arr+n);

      if(arr[0]<k+1)

       {

        cout<<arr[0]<<endl;

        return 0;

       }

       else

        {

          for(int i=arr[0];i>=k+1;i--)

           {

            int l=0;

            int u=0;

            int r=0;

            for(int j=0;j<=arr[n-1]/i;j++)

             {

              l=lower_bound(arr,arr+n,j*i)-arr;

              u=upper_bound(arr,arr+n,j*i+k)-arr;

              r+=(u-l);

              //  cout<<r<<endl;

             }

              //cout<<"i "<<i<<" r "<<r<<endl;

             if(r==n)

              {

              cout<<i<<endl;

              return 0;

              }

           }

        }

    //  cout<<"wtf"<<endl;  

      return 0;

 

 }