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;
}