Project Spoon  Problem code: SPOONS

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Lo and Behold! For you may be surprised by what our chief chef Noodle has in mind for this season! Today, Noodle announced one of his most extra-ordinary ideas ever - Project Spoon. 

Noodle plans to deploy large spoons in the atmosphere so that people all around the world can download food directly from his kitchen thereby saving him a lot of overhead cost. Yes, you read that right. Large spoons suspended in the atmosphere.

Noodle decides the following strategy to implement his idea. He will deploy exactly N spoons in the country. Every spoon can cater to as many cities as it wants. The only catch is that between every pair of spoons Aand B, A must cater to at-least one city that B doesn't cater to, and B must cater to at-least one city that Adoesn't cater to.

Noodle would like to know what is the minimum number of cities a country must have for his strategy to be successful. Since, he is not all that good with calculation, he asks you to help him with it.

Input

The first line contains an integer T denoting the number of test cases. Each of the next T lines contain an integer N, the number of spoons that Noodle plans to deploy in the country.

Output

For every test case, print in a single line the number of minimum cities required.

Constraints

• 1 ≤ T ≤ 100000
• 2 ≤ N ≤ 10¹⁸

Example

Input:
2
2
3

Output:
2
3

Explanation

Example case 1.

Each spoon caters to a different city. Since there are two spoons, two cities are sufficient. 

Example case 2.

Again, each spoon needs to cater to one city and there are three spoons. So, three cities are required at minimum. 

Pre-requisites:

Sperner's Theorem

Problem:

Given an integer N, find the size of smallest set S such that there exists an antichain of size N among the subsets of S.

Explanation:

The relation between groups of cities A and B served by two spoons can be equivalently stated as: A-B is not empty andB-A is not empty, which is same as A ⊄ B and B ⊄ A.

If we consider the poset of all subsets of a set S, then the two elements A and B above are incomparable, therefore all the N sub-sets form an antichain.

People could obtain the solution by

• guess work, or,
• evaluating the first few few terms and then using oies to get the required sequence, or,
• reinventing proof of Sperner's Theorem.

The statement and proof of Sperner's Theorem is given below in very simple language.

Given the Sperner's Theorem, we would still need to find smallest M such that M choose ⌊ M/2 ⌋ is at least N. For N ≤ 10¹⁸, M ≤ 64, and therefore, one could compute these values offline(or online in his code itself), and do a binary search to lookup the best value. Time complexity O(T).

Proof of Sperner's Theorem

Given a set S of size M, you want to pick a family F of subsets of S (i.e. F ⊂ 2^S) such that no set in the family is subset of another set in the family (i.e. x, y ∈ F ⇒ x ⊄ y). The maximum possible size of such a family of subsets is M choose ⌊ M/2 ⌋

It is clear that if we choose all subsets in the family F to be of same size, k, then the family would satisfy the above property, and its size will be M choose k. This is maximum when k=⌊ M/2 ⌋. Therefore, the bound suggested above can be attained by picking all sbsets of size ⌊ M/2 ⌋. Now it remains to show that this is also the best possible bound.

Lets say we have got a family F of subsets satisfying above property, and it has a₁ subsets of size 1, a₂ subsets of size 2... a_M subsets of size M.

Then we can generate a permutation of S by selecting a set S' in F and concatenating a permutation of the elements ofS' with a permutation of the non-members. If |S'| = i, it will be associated in this way with i!(n − i)! permutations. Each permutation can only be associated with at most one set in F. This is because otherwise two different prefixes of a single permutation would be associated with different subsets(say S₁ and S₂) in F, in which case, one(out of S₁ andS₂) would be a subset of the other. Therefore, the number of permutations that can be generated by this procedure is

sum [i=1 to M] a_i * i! (M-i)!

And the above number is no more than M!. For k=⌊ M/2 ⌋ we already have

   sum [i=1 to M] a_i * k! (M-k)! ≤ sum [i=1 to M] a_i * i! (M-i)! ≤ M!

⇒ sum [i=1 to M] a_i ≤ M!/ (k! * (M-k)!)

Setter's Solution:

Can be found here

Tester's Solution:

1. Mahbub's code
2. Sergey's code

Editorialist's Solution:

Can be found here, and code used to generate values offline is here

#include<bits/stdc++.h>

using namespace std;

long long int nCr[66][66];

void pre()

{

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

        nCr[i][0] = 1 ;

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

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

            nCr[i][j] = ( nCr[i-1][j-1] + nCr[i-1][j] ) ;

}

long long int limit[66];

int main()

{

pre();

limit[0]=0;

limit[1]=1;

limit[2]=2;

limit[3]=3;

limit[4]=6;

for(int i=5;i<=65;i++)

{

 limit[i]=nCr[i][i/2];

}

int t;

cin>>t;

while(t--)

{

long long int i,n;

cin>>n;

for(i=0;i<=65;i++)

{

if(limit[i]>=n)

{

cout<<i<<endl;

break;

}

}

}

return 0;

}

D. The Child and Zoo

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains ai animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.

Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).

After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105). The second line contains n integers: a1, a2, ..., an(0 ≤ ai ≤ 105). Then follow m lines, each line contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the road between areas xiand yi.

All roads are bidirectional, each pair of areas is connected by at most one road.

Output

Output a real number — the value of .

The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Sample test(s)

input

4 3
10 20 30 40
1 3
2 3
4 3

output

16.666667

input

3 3
10 20 30
1 2
2 3
3 1

output

13.333333

input

7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7

output

18.571429

Note

Consider the first sample. There are 12 possible situations:

• p = 1, q = 3, f(p, q) = 10.
• p = 2, q = 3, f(p, q) = 20.
• p = 4, q = 3, f(p, q) = 30.
• p = 1, q = 2, f(p, q) = 10.
• p = 2, q = 4, f(p, q) = 20.
• p = 4, q = 1, f(p, q) = 10.

Another 6 cases are symmetrical to the above. The average is .

Consider the second sample. There are 6 possible situations:

• p = 1, q = 2, f(p, q) = 10.
• p = 2, q = 3, f(p, q) = 20.
• p = 1, q = 3, f(p, q) = 10.

Another 3 cases are symmetrical to the above. The average is .

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

#include <vector>

#define rep(i, a, b) for (int i = a; i < b; ++i)

#define dep(i, a, b) for (int i = a; i > b; --i)

#define N 300005

using namespace std;

typedef long long i64;

int rank[N], eva[N], val[N], u[N], v[N], f[N], sz[N];

int n, m;

double ans, base;

bool rk_cmp(const int &a, const int &b)

{

return eva[a] > eva[b];

}

int father(int u)

{

if (f[u] == u)  return u;

f[u] = father(f[u]);

return f[u];

}

int main()

{

scanf("%d %d", &n, &m);

base = (double) n*(n-1);

rep(i, 0, n) scanf("%d", &val[i+1]);

rep(i, 0, m)

{

scanf("%d %d", &u[i], &v[i]);

eva[i] = min(val[u[i]], val[v[i]]);

rank[i] = i;

}

rep(i, 0, n)

{

f[i+1] = i+1;

sz[i+1] = 1;

}

sort(rank, rank+m, rk_cmp);

rep(i, 0, m)

{

int now = rank[i], nu = father(u[now]), nv = father(v[now]);

if (nu != nv)

{

i64 add = (i64) sz[nu] * sz[nv];

ans += add / base * eva[now];

sz[nu] += sz[nv];

f[nv] = nu;

}

}

printf("%.7lf\n", ans*2);

}

C. Xenia and Weights

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Xenia has a set of weights and pan scales. Each weight has an integer weight from 1 to 10 kilos. Xenia is going to play with scales and weights a little. For this, she puts weights on the scalepans, one by one. The first weight goes on the left scalepan, the second weight goes on the right scalepan, the third one goes on the left scalepan, the fourth one goes on the right scalepan and so on. Xenia wants to put the total of m weights on the scalepans.
Simply putting weights on the scales is not interesting, so Xenia has set some rules. First, she does not put on the scales two consecutive weights of the same weight. That is, the weight that goes i-th should be different from the (i + 1)-th weight for any i (1 ≤ i < m). Second, every time Xenia puts a weight on some scalepan, she wants this scalepan to outweigh the other one. That is, the sum of the weights on the corresponding scalepan must be strictly greater than the sum on the other pan.
You are given all types of weights available for Xenia. You can assume that the girl has an infinite number of weights of each specified type. Your task is to help Xenia lay m weights on ​​the scales or to say that it can't be done.

Input

The first line contains a string consisting of exactly ten zeroes and ones: the i-th (i ≥ 1) character in the line equals "1" if Xenia has i kilo weights, otherwise the character equals "0". The second line contains integer m (1 ≤ m ≤ 1000).

Output

In the first line print "YES", if there is a way to put m weights on the scales by all rules. Otherwise, print in the first line "NO". If you can put m weights on the scales, then print in the next line m integers — the weights' weights in the order you put them on the scales.
If there are multiple solutions, you can print any of them.

Sample test(s)

Input

0000000101
3

Output

YES
8 10 8

Input

1000000000
2

Output

NO

This was a very nice dfs type dp question accompanied by few observations.
First of all we notice that if the difference at any point of time is greater than 10 then the state cannot be
continued. 
Suppose the weight configuration in the pan is (16,20,10) where 16 is the sum of weight in left pan, 20 is the sum 
of weight in right pan and last used weight is 10 this can be simplified to the state as (4,10,number of steps) 
where 4 is the difference and 10 is the last used weight in right pan. So we keep a state 
dp[difference][last used weight][number of steps]. And whenever we assign a new weight we want the present weight
to be greater than the difference. 

The code for clarity

#include<bits/stdc++.h>
using namespace std;
int dp[30][12][1010]  ;// dp[diiference][last][steps]
char h[12];
int arr[1010];
bool f=0;
int m;
bool solve(int diff, int last, int steps,int fill[],int pos)
{
  // cout<<diff<<" "<<last<<" "<<steps<<endl;
   if(steps==0)
   {
   // cout<<"return "<<endl;
      if(f==0)
      {
       cout<<"YES"<<endl;
          for(int i=0;i<m;i++)
    cout<<fill[i]<<" ";
    f=1; 
    }
   return 1;
      
   }
   if(dp[diff][last][steps]!=-1)
   {
    //cout<<"ret "<<endl;
   return dp[diff][last][steps];
      }
   bool ret=0;
   for(int i=0;i<10;i++)
   {
   // cout<<"enter "<<endl;
            if(h[i]=='1' && i+1!=last && i+1>diff)
            {
    //         cout<<"call solve "<<endl;
             fill[pos]=i+1;
                      ret=solve(i+1-diff,i+1,steps-1,fill,pos+1); 
    }
    if(ret==1)
    break;
   }
   dp[diff][last][steps]=ret;
   return ret;
}
int main()
{
 //int m;
 string s;
 cin>>s;
 for(int i=0;i<10;i++)
 {
    h[i]=s[i];
 }
 memset(dp,-1,sizeof(dp));
 cin>>m;
 bool ans=0;
 ans=solve(0,0,m,arr,0);
 if(!ans)
 {
   cout<<"NO"<<endl;
   return 0;
 }
 
 return 0;
}