Monday 18 July 2016

 
 
 
 

F. Couple Cover
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Couple Cover, a wildly popular luck-based game, is about to begin! Two players must work together to construct a rectangle. A bag withn balls, each with an integer written on it, is placed on the table. The first player reaches in and grabs a ball randomly (all balls have equal probability of being chosen) — the number written on this ball is the rectangle's width in meters. This ball is not returned to the bag, and the second player reaches into the bag and grabs another ball — the number written on this ball is the rectangle's height in meters. If the area of the rectangle is greater than or equal some threshold p square meters, the players win. Otherwise, they lose.
The organizers of the game are trying to select an appropriate value for p so that the probability of a couple winning is not too high and not too low, but they are slow at counting, so they have hired you to answer some questions for them. You are given a list of the numbers written on the balls, the organizers would like to know how many winning pairs of balls exist for different values of p. Note that two pairs are different if either the first or the second ball is different between the two in pair, and two different balls with the same number are considered different.
Input
The input begins with a single positive integer n in its own line (1 ≤ n ≤ 106).
The second line contains n positive integers — the i-th number in this line is equal to ai (1 ≤ ai ≤ 3·106), the number written on the i-th ball.
The next line contains an integer m (1 ≤ m ≤ 106), the number of questions you are being asked.
Then, the following line contains m positive integers — the j-th number in this line is equal to the value of p (1 ≤ p ≤ 3·106) in the j-th question you are being asked.
Output
For each question, print the number of winning pairs of balls that exist for the given value of p in the separate line.
Examples
input
5
4 2 6 1 3
4
1 3 5 8
output
20
18
14
10
input
2
5 6
2
30 31
output
2









/*      my general mistakes that costed me a lot
          * check for overflows
          * check and mod and use int type variables where possible to avoid tles
          * while multiplying two variables whose value can exceed integer 
          limt make sure to typecase them
          * use scanf when you are not working with the best possible optimisation
          * return a value from a function that has a return type sometimes the 
          compiler may give the correct answer but there will be problem in the judge
          * be very cautious about uninitiaalised variables , infact never keep them
          or handle them properly
    *never use inbuilt log function or pow function it fucking ruins everything
    */
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long int
#define pp pair<int,int> 
#define ve vector
#define mod 1000000007
int dx[]={-1,-1,+0,+1,1,+1,+0,-1}; // anticlockwise starting from up!
int dy[]={+0,-1,-1,-1,0,+1,+1,+1};
/************************************CODE BEGINS HERE************************/

int cnt[3000010];
ll possible[3000010];
vector<int> v;
void pre()
{
        for(int i=1;i<=3000000;i++)
        {
             if(cnt[i]!=0)
             {
       
               for(int j=1;j*i<=3000001;j++)
               {
                  if(i!=j)
                   possible[j*i]+=(1ll*cnt[j]*cnt[i]);
       else
       possible[j*i]+=(1ll*(cnt[i]*(cnt[i]-1))); 
      }
      
     }
 }
}
int main()
{
 ll n;
cin>>n;
     for(int i=0;i<n;i++)
     {
             int aa;
             scanf("%d",&aa);
             if(cnt[aa]==0)
             v.pb(aa);
               cnt[aa]++;
  }
  sort(v.begin(),v.end());
  pre();
  int sz=v.size();
 for(int i=0;i<=3000001;i++)
 {
    possible[i]+=possible[i-1];
 }
 
  int q;
  cin>>q;
  while(q--)
  {
   int x;
     scanf("%d",&x);
   ll ans=1ll*(n*(n-1))-possible[x-1];
   cout<<ans<<"\n";
  }
  return 0;
}  






























Posted by



at





No comments:
  


































          

        

          

        

Tuesday 21 June 2016


          

        





















Subarray Removal



Time limit: 1000 ms
Memory limit: 128 MB







You are given an array of N integers. You should remove a non-emptysubarray of size at most N-1. Then you should compute the maximum sum subarray in the resulting array. Find out the maximum value you can get.



Standard input



The first line contains a single integer value N.



The second line contains N integers representing the elements of the array.



Standard output



The output should contain a single integer, the wanted answer.



Constraints and notes


    

  • 2 ≤ N ≤ 100 000
    • 

  • The elements of the array will be between -10^9 and 10^9
    • 





InputOutputExplanation



5
10 -2 3 -10 5


16





We eliminate -10, and the remaining array is the maximum sum subarray : 10 -2 3 5.






7
-3 2 -1 5 -7 9 -10


15





We eliminate -7. The resulting array is: -3 2 -1 5 9 -10. The maximum sum subarray is : 2 -1 5 9 



THIS CAN BE REDUCED AS A CLASSIC MAXIMUM SUBARRAY SUM PROBLEM , REMEMBER YOU ALWAYS NEED TO REMOVE A SEGMENT , SO FIRST CALCULATE THE PREFIX AND SUFFIX FOR EVERY i . NOW WE CHECK FROM THE BACK FOR REMOVING SEGMENTS



****SEE THE CODE********



#include<bits/stdc++.h>



using namespace std;



#define ll long long int







int main()



{



   int n;



   cin>>n;



   string temp="";



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



   {



      string s;



      cin>>s;



      sort(s.begin(),s.end());



      temp+=s[0];



   }



   sort(temp.begin(),temp.end());



   cout<<temp<<endl;



   return 0;







}



                                                                     




















Posted by



at





No comments:
  


































          

        

          

        

Friday 27 May 2016


          

        































C. Prime Swaps





time limit per test

2 seconds





memory limit per test

256 megabytes





input

standard input





output

standard output







You have an array a[1], a[2], ..., a[n], containing distinct integers from 1 to n. Your task is to sort this array in increasing order with the following operation (you may need to apply it multiple times):


    

  • choose two indexes, i and j (1 ≤ i < j ≤ n; (j - i + 1) is a prime number);
    • 

  • swap the elements on positions i and j; in other words, you are allowed to apply the following sequence of assignments:tmp = a[i], a[i] = a[j], a[j] = tmp (tmp is a temporary variable).
    • 




You do not need to minimize the number of used operations. However, you need to make sure that there are at most 5n operations.







Input



The first line contains integer n (1 ≤ n ≤ 105). The next line contains n distinct integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).







Output



In the first line, print integer k (0 ≤ k ≤ 5n) — the number of used operations. Next, print the operations. Each operation must be printed as "i j" (1 ≤ i < j ≤ n; (j - i + 1) is a prime).



If there are multiple answers, you can print any of them.







Examples







input


3
3 2 1







output


1
1 3







input


2
1 2







output


0







input


4
4 2 3 1







output


3
2 4
1 2
2 4























  HERE WE GO THROUGH A GREEDY STRATEGY AND ALWAYS BRING THE NUMBER TO ITS NEAREST POSITION THAT CAN BE DONE USING A VALID SWAP. IT IS ALWAYS CORRECT BECAUSE WE CAN SWAP TWO NEIGHBORING NUMBERS ALWAYS SO THIS WILL LEAD TO A SOLUTION.







            LOOK AT THE EASY CODE





#include<bits/stdc++.h>



using namespace std;



#define ll long long int 



bool pr[100010];



#define ff first



#define ss second



#define mp make_pair



#define pb push_back



vector<int> v;



int l;



void pre()



{



     for(int i=2;i<=100000;i++)



     {



         if(!pr[i])



         {



             v.pb(i);



             for(int j=2*i;j<=100000;j+=i)



             {



                   pr[j]=1; 



       }



      }



  }



  l=v.size();



}



int pos[100010];



int a[100010];



int main()



{



      pre();



       int n;



       cin>>n;



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



       {



          cin>>a[i];



          pos[a[i]]=i;



    }



    vector<pair<int,int> > res;



    



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



    {



            while(pos[i]!=i)



            {



                int lst=pos[i];



             



                 int shiftm=abs(pos[i]-i)+1;



         vector<int> ::iterator it;



         it=upper_bound(v.begin(),v.end(),shiftm);



      it--;



      int val=*it;



     // cout<<"value "<<val<<endl;



            int idx=pos[i]+1-val;



     //       cout<<"idx "<<idx<<endl;



            res.pb(mp(pos[i],idx));



            



            pos[a[idx]]=pos[i];



            pos[i]=idx;



            



           // cout<<"sert pos of "<<i<<" as "<<pos[i]<<" and pos of "<<a[idx]<<" = "<<pos[a[idx]]<<endl;



            swap(a[idx],a[lst]);



    



      }



         



   }



   int sz=res.size();



   cout<<sz<<endl;



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



   cout<<min(res[i].ff,res[i].ss)<<" "<<max(res[i].ff,res[i].ss)<<endl;



    return 0;



    }






































Posted by



at





No comments:
  


































        

      









Subscribe to:
Posts (Atom)