A. Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Happy PMP is freshman and he is learning about algorithmic problems. He enjoys playing algorithmic games a lot.
One of the seniors gave Happy PMP a nice game. He is given two permutations of numbers 1 through n and is asked to convert the first one to the second. In one move he can remove the last number from the permutation of numbers and inserts it back in an arbitrary position. He can either insert last number between any two consecutive numbers, or he can place it at the beginning of the permutation.
Happy PMP has an algorithm that solves the problem. But it is not fast enough. He wants to know the minimum number of moves to convert the first permutation to the second.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·10⁵) — the quantity of the numbers in the both given permutations.
Next line contains n space-separated integers — the first permutation. Each number between 1 to n will appear in the permutation exactly once.
Next line describe the second permutation in the same format.

Output

Print a single integer denoting the minimum number of moves required to convert the first permutation to the second.

Sample test(s)

Input

3
3 2 1
1 2 3

Output

2

Input

5
1 2 3 4 5
1 5 2 3 4

Output

1

Input

5
1 5 2 3 4
1 2 3 4 5

Output

3

Note

In the first sample, he removes number 1 from end of the list and places it at the beginning. After that he takes number 2 and places it between 1 and 3.
In the second sample, he removes number 5 and inserts it after 1.
In the third sample, the sequence of changes are like this:

• 1 5 2 3 4
• 1 4 5 2 3
• 1 3 4 5 2
• 1 2 3 4 5

So he needs three moves.

 

 

Solution 

 

If we replace the array the 1st array with the corresponding position in 2nd array then the question simply reduces to sorting the first array.

Suppose now we postpone the placement of every last element till we find its appropriate place to put. Therefore  let i be the largest index for which 1 to i is sorted so the answer is n-i.

Let us take an example and justify 

suppose we have p1= 1 2 5 4 3

                           p2= 4 2 1 3 5

the new array acccording to position is   

3 2 1 5 4 

so the longest increasing sequence is 3

Now suppose we have 2 1 54 in our hands and then we place each elements in their respective postion to sort the array.

 

code

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int b[200010];
int h[200010];
int arr[200010];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
         cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
         cin>>b[i];
         h[b[i]]=i;
    }
    for(int i=0;i<n;i++)
    {
         arr[i]=h[a[i]];
    }
    int mx=-1;
    int cnt=1;
    for(int i=1;i<n;i++)
    {
          if(arr[i]>arr[i-1])
          cnt++;
          else
          break;
    }
    cout<<n-cnt<<endl;
    return 0;
}

C. Beautiful Numbers

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vitaly is a very weird man. He's got two favorite digits a and b. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits a and b. Vitaly calls a good number excellent, if the sum of its digits is a good number.

For example, let's say that Vitaly's favourite digits are 1 and 3, then number 12 isn't good and numbers 13 or 311 are. Also, number111 is excellent and number 11 isn't.

Now Vitaly is wondering, how many excellent numbers of length exactly n are there. As this number can be rather large, he asks you to count the remainder after dividing it by 1000000007 (109 + 7).

A number's length is the number of digits in its decimal representation without leading zeroes.

Input

The first line contains three integers: a, b, n (1 ≤ a < b ≤ 9, 1 ≤ n ≤ 106).

Output

Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Sample test(s)

input

1 3 3

output

1

input

2 3 10

output

165

First we need to make few observations ,as the number of digits is maximum 10^6 so the maximum value of the sum can go upto 9*10^6.  So looping once through all through all possible sum values can be plausible. So for each sum we first check if that is constructed only with a and bs . If it is then let the number have i's number of a and (n-i)'s number of bs. Hence the sum can be represented as ai+(n-i)b=sum.

THerefore for all values satisfying the equaiton we can add n!/i!(n-i)! to the answer.

The factorials and inverse factorials can be precomputed.

solution

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

 

#define mod 1000000007

typedef long long int ll;

ll f[1000010];

ll inv[1000010];

ll powmod(ll a,ll n,ll MOD)

{

ll p=1;

for(;n;)

{

if(n%2) p=(p)*a%MOD;

if(n/=2) a=(a)*a%MOD;

}

return p;

}

void pre()

{

 f[0]=1;

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

  {

    f[i]=(f[i-1]*i)%mod;

  }

  inv[0]=1;

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

  {

         inv[i]=powmod(f[i],mod-2,mod);

  }

}

int a,b;

bool check(int val)

{

   while(val!=0)

   {

    int rem=val%10;

    val=val/10;

    if(rem==a || rem== b )

    continue;

    else 

    return 0;

}

return 1;

}

int main()

{

pre();

int n;

//cout<<f[6]<<" "<<endl;

// int a,b;

cin>>a>>b;

if(b>a)

swap(a,b);

cin>>n;

ll ans=0;

int mx=9*n;

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

{

   if(check(i))

   {

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

       int checkval=i-b*n;

       if(checkval<0)

       continue;

           int temp=a-b;

           if(checkval%temp==0)

           {

//             cout<<"here "<<endl;

              int numbera=checkval/temp;

              int numberb=n-numbera;

//               cout<<"numer a "<<numbera<<" number b "<<numberb<<endl;

              if(numbera>=0 && numberb>=0)

              {

//               cout<<"inverses "<<inv[numbera]<<" "<<inv[numberb]<<endl;

     ll res=(((f[n]*inv[numbera])%mod)*inv[numberb])%mod;

                 ans=(ans+res)%mod;

             }

}

          

}

}

cout<<ans<<endl;

return 0;

}

C. MUH and House of Cards

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev decided to build a house of cards. For that they've already found a hefty deck of n playing cards. Let's describe the house they want to make:

1. The house consists of some non-zero number of floors.
2. Each floor consists of a non-zero number of rooms and the ceiling. A room is two cards that are leaned towards each other. The rooms are made in a row, each two adjoining rooms share a ceiling made by another card.
3. Each floor besides for the lowest one should contain less rooms than the floor below.

Please note that the house may end by the floor with more than one room, and in this case they also must be covered by the ceiling. Also, the number of rooms on the adjoining floors doesn't have to differ by one, the difference may be more.

While bears are practicing to put cards, Horace tries to figure out how many floors their house should consist of. The height of the house is the number of floors in it. It is possible that you can make a lot of different houses of different heights out of n cards. It seems that the elephant cannot solve this problem and he asks you to count the number of the distinct heights of the houses that they can make usingexactly n cards.

Input

The single line contains integer n (1 ≤ n ≤ 1012) — the number of cards.

Output

Print the number of distinct heights that the houses made of exactly n cards can have.

Sample test(s)

input

13

output

1

input

6

output

0

Note

In the first sample you can build only these two houses (remember, you must use all the cards):

Thus, 13 cards are enough only for two floor houses, so the answer is 1.

The six cards in the second sample are not enough to build any house.

First of make us few observations

suppose we fix r rooms in a floor then we will see that the number of cards needed for the same are 2*R+(R-1)

2 cards for each rooms and R-1 cards for the ceiling

Suppose we construct F floors with the same then number of cards N required for the same are 

2*r1+(r1-1)+ 2*r2+(r2-1) +2*r3+(r3-1)........=N

  

therfore  if the number of floors is equal to F then the rooms needed are 

          3*r1+3*r2+3*r3+......+3*rf+.....=N+F

implies

               3(r1+r2+r3+.....+rf)=N+F

First observation is that to be a valid frame the factor N+F should be totally divisble by 3 else we cannot for a 

valid house of cards. 

Moving to the second step, for a house with height f since number of floors should be monotonically increasing therefore

our greedy to of assignment is 1 room on first floor 2 room on second and so on.....

Lets resolve the for any height we need atleast 3 *F*(F+1)/2 cards if this is applicable (meaning if for any 

floor F we have more than this number of cards) and if (N+F) is divisible by 3 then we can construct the house.

The code goes below 

#include "assert.h"
#include <iostream>

typedef long long int LL;

using namespace std;

LL getNumberOfCardsInFullHouse(LL floors) {
  return 3 * floors * (floors + 1) / 2 - floors;
}
 
LL solve(LL n) {
  LL res = 0;
  for (LL floors = 1 ; getNumberOfCardsInFullHouse(floors) <= n ; floors++)
    if ((n + floors) % 3 == 0)
      res++;
  return res;
}
 
int main() {
  LL n; cin >> n;
  cout << solve(n); 
}

A. Bear and Poker

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are n players (including Limak himself) and right now all of them have bids on the table. i-th of them has bid with size ai dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input

First line of input contains an integer n (2 ≤ n ≤ 105), the number of players.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109) — the bids of players.

Output

Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

Sample test(s)

input

4
75 150 75 50

output

Yes

input

3
100 150 250

output

No

Note

In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

We can numltiply any number with 2 and 3 any number of times that means in general a number can be multiplied with 2^p*3^q. As each number can be broken in prime as 

x=2^a*3^b*5^c*7^d 

therefore intuitively we can increase a and and b to any number we want but the rest must be same. Hence the solution is that all numbers should have same powers of other terms except 2 and 3 

code

#include<bits/stdc++.h>

using namespace std;

int a[100010];

int main()

{

int n;

cin>>n;

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

{

cin>>a[i];

}

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

{

    while(a[i]%2==0)

    a[i]/=2;

    while(a[i]%3==0)

    a[i]/=3;

}

bool f=0;

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

{

   if(a[i]!=a[0])

   {

    f=1;

    break;

}

}

if(f)

cout<<"No"<<endl;

else

cout<<"Yes"<<endl;

return 0;

}

The Chef is given a sequence of N integers A₁, A₂, ..., A_N. He has to process Q queries on the above sequence. Each query is represented by three integers:

• L R K => report cardinality of { i : K divides A_i, L ≤ i ≤ R }. In other words, how many integers in the subsequence starting at L^th element and ending at R^th element are divisible by K.

Input

The first line of the input contains two space separated integer N and Q.
The following line contains N space separated integers giving the sequence A₁, A₂, ..., A_N.
Then there will be Q lines each containing three space separated integers L R K, representing a query.

Output

For each query output the result in one line.

Constraints

• 1 ≤ N, Q ≤ 100000 (10⁵)
• 1 ≤ A_i ≤ 100000 (10⁵)
• 1 ≤ L ≤ R ≤ N
• 1 ≤ K ≤ 100000 (10⁵)

Example

Input:
8 5
3 5 1 4 6 9 12 6
3 6 2
3 6 4
4 8 3
2 6 7
8 8 6

Output:
2
1
4
0
1

size of 10^5 gives an idea of initially  finding factors of all array elements in nsqrt(n) times.

We use a vector to push all the indexes where k occurs.

Now we , simply store them in a 2d vector and then binary search on it to give the answer.

#include<bits/stdc++.h>
using namespace std;
vector<int> fact[100010];
int arr[100010];

int main()
{
 int n;
 cin>>n;
 int q;
 cin>>q;
 
 for(int i=1;i<=n;i++)
 {
   scanf("%d",&arr[i]);
 }
 for(int i=1;i<=n;i++)
 {
    int val=sqrt(arr[i]);
    for(int j=1;j<=val;j++)
    {
       if(arr[i]%j==0)
       {
            fact[j].push_back(i);
            if(j!=arr[i]/j)
            fact[arr[i]/j].push_back(i);
    }
    }
 }
 

    while(q--)
    {
        int l,r,k;
        scanf("%d %d %d",&l,&r,&k);
        vector<int> ::iterator low,high;
        
        low=lower_bound(fact[k].begin(),fact[k].end(),l);
        high=upper_bound(fact[k].begin(),fact[k].end(),r);
        int ans=high-low;
        cout<<ans<<endl;
    }
 return 0;
}

Gukiz is obsessed with binary operations. He is trying to solve a task with the binary operation XOR, but he can’t seem to figure out one problem. Can you help?

You are given an array a with n elements. Calculate the number of ways to split this array into 2 disjoint non-empty groups with equal XOR value between their elements.

A disjoint group means that each element of array a is located in exactly 1 group. The answer can be very large, so print it by modulo (109+7).

Input Format

The first line of input contains one integer n: the size of array a. The second line contains nseparated integers a1,a2,…,an, representing array a.

Constraints:

1≤n≤105
0≤ai≤109

Note: The scoring for this problem is binary. You have to pass all the testcases to get a positive score.

Output Format

In a single line, print one integer - number of ways for splitting the array into two groups with equal XOR by modulo 109+7.

Sample Input 1

3
0 1 1

Sample Output 1

3

Sample Input 2

4
5 2 3 2

Sample Output 2

0

Explanation

In the first example, we have array a with three elements a={0,1,1}. We can split this array in the following ways:

1. {1,1},{0}. The XOR of the first group is equal to 0 (1 XOR 1 = 0). The XOR of the second group is equal to 0.
2. {0,1}, {1}. The XOR of the first and second group is equal to 1.
3. {0,1}, {1}. Same case as above.

We have two ones, so we have two possible groups {0,1}. Answer is 3.

In the second example, we cannot split the array. Answer is 0.

Note: The xor operator exists in most programming languages, for example, in C++, Java and Python xor is represented as ^, in Pascal — as xor.

his is a trick question.

If you have integers a1...an and you can divide them into two parts such that their XORs are equal, this just means that a1 xor a2 xor ... xor an equals zero. When that holds, ANY partition works, e.g. (a1) xor (a2 xor a3 xor ... xor an) == 0 by the above, so it must be that a1 == a2 xor ... xor an. Hence ANY partition works. Given that, you just either select an empty partition and full partition, if that is allowed, or the smallest integer into a singleton partition and put everything else into the second one.

Lets us suppose the xor of subset 1 is X1 and that of subset 2 is X2 

now given X1=X2 which implies X1^X2 =0 that means a1^a2^a^3.....=0;

therefore we can choose any partition of the array given on the constraint that is(it must contain a single element to derive our forumla)

How 2^n-2/2

let us construct subset A thereby B is constructed automatically from the reamining elements of the array 

 the number of ways to select elements for set A are

let Q=

 nc1+ cn2+........ncn-1  (considering we have to choose 1 elem atleast)

Now we know

nc0+ nc1+ nc2+.....+nCn=pow(2,n)

therefore 

Q=2^n-2

now we notice that halfway through we have doubly computed our answers as set A and set B are not ordered pairs therefore we divide the result by 2.

Code

#include<iostream>
#include<stdio.h>

using namespace std;

const int m=1e9+7;
const int maxN=1e6;

int x,xs,n,st[maxN];

int main()
 {
   scanf("%d\n",&n);

   xs=0; 
   st[0]=1;
   for (int i=1;i<n;i++)
   st[i]=(st[i-1]*2)%m;


   for (int i=0;i<n;i++)
   {
       scanf("%d",&x);
       xs=xs^x;
   }

   if (xs!=0) printf("%d",0); else
       printf("%d",(st[n-1]+m-1)%m);

   return 0;
}