Sunday, May 1, 2016

UVA 914 - Jumping Champion

#include<bits/stdc++.h>
#define i64 long long
#define mx(a,b,c) max(a,max(b,c))
#define mn(a,b,c) min(a,min(b,c))
#define eef else if
#define ff(i,s,e) for(int i=(s); i<e; i++)
#define ff2(i,s,e) for(int i=(s); i>=e; i--)
#define sf scanf
#define pf printf
#define dbug(x) cout<<"x = "<<x<<endl
#define newl cout<<"\n"
#define putcase cout<<"Case "<<++cse<<":"
using namespace std;
bool isPrime(int x)
{
    int sqr=sqrt(x);
    ff(m,2,sqr+1){
        if(x%m==0){
            return false;
        }
    }
    return true;
}
int main()
{
   int t;
    vector<int>primeNum;
   ff(i,2,1000001){
        if(isPrime(i)==true)
            primeNum.push_back(i);
       }
   cin>>t;
   while(t--){
        int a , b,cnt=0,low=0,high=0,highdiff=0;
      cin>>a>>b;
       int diff[150];
       memset(diff,0,sizeof(diff));
       ff(i,0,primeNum.size()){
        if(primeNum[i]>=a && cnt==0){
            low=i;
           cnt++;
        }
        else if(primeNum[i]<=b){
            high=i;
        }
          //  cout<<low<<" "<<high;
       }
     /*  dbug(primeNum[low]);
       dbug(primeNum[high]);*/
       if(cnt!=0){
           ff(i,low+1,high+1){
            int d=primeNum[i]-primeNum[i-1];
            diff[d]++;
           }
           ff(i,0,121){
               if(diff[i]>diff[highdiff]){
                    highdiff=i;
               }
           }
           sort(diff,diff+120);
           if(diff[119]==diff[118])
            cout<<"No jumping champion\n";
           else
            cout<<"The jumping champion is "<<highdiff<<endl;
       }
       else
        cout<<"No jumping champion\n";
   }
    return 0;
}

No comments:

Post a Comment