AGGRCOW - Aggressive cows

#binary-search

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a
straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put
into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such
that the minimum distance between any two of them is as large as possible. What is the largest
minimum distance?

Input
t – the number of test cases, then t test cases follows.
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output
For each test case output one integer: the largest minimum distance.

Example
Input:

5 3

Output:

Output details:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8,
resulting in a minimum distance of 3.

EKO - Eko
#binary-search

Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a
nifty new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed
to cut a single row of trees.
Mirko‟s machine works as follows: Mirko sets a height parameter H (in metres), and the machine
raises a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher
than H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree
row contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15
metres, the remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while
Mirko will take 5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).
Mirko is ecologically minded, so he doesn‟t want to cut off more wood than necessary. That‟s why
he wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of
the sawblade that still allows him to cut off at least M metres of wood.

Input
The first line of input contains two space-separated positive integers, N (the number of trees, 1 ≤ N ≤ 1
000 000) and M (Mirko‟s required wood amount, 1 ≤ M ≤ 2 000 000 000).
The second line of input contains N space-separated positive integers less than 1 000 000 000,
the heights of each tree (in metres). The sum of all heights will exceed M, thus Mirko will always be able
to obtain the required amount of wood.

Output
The first and only line of output must contain the required height setting.

Example

Input:

4 7

20 15 10 17

Output:

15
Input:

5 20

4 42 40 26 46

Output:

36

HORRIBLE - Horrible Queries

#tree #binary-search

World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary
Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a
PhD in horribleness (but not in Computer Science). You are given an array of N elements, which are
initially all 0. After that you will be given C commands. They are -
* 0 p q v - you have to add v to all numbers in the range of p to q (inclusive), where p and q are two
indexes of the array.
* 1 p q - output a line containing a single integer which is the sum of all the array elements between p
and q (inclusive)

Input
In the first line you'll be given T, number of test cases.
Each test case will start with N (N <= 100 000) and C (C <= 100 000). After that you'll be given C
commands in the format as mentioned above. 1 <= p, q <= N and 1 <= v <= 10^7.

Output
Print the answers of the queries.

Example

Input:
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8
0 5 7 14
1 4 8

Output:
80
508

Calculating n-th real root using binary search

Given two number x and n, find n-th root of x.
Examples:
Input : 5 2
Output : 2.2360679768025875

Input : x = 5, n = 3
Output : 1.70997594668
In order to calculate nth root of a number, we can use the following procedure.
1. If x lies in the range [0, 1) then we set the lower limit low = x and upper limit high =
1, because for this range of numbers the nth root is always greater than the given
number and can never exceed 1.
eg-
2. Otherwise, we take low = 1 and high = x.
3. Declare a variable named epsilon and initialize it for accuracy you need.
Say epsilon=0.01, then we can guarantee that our guess for nth root of the given
number will be
correct up to 2 decimal places.
4. Declare a variable guess and initialize it to guess=(low+high)/2.
5. Run a loop such that:
 if the absolute error of our guess is more than epsilon then do:
1. if guessn > x, then high=x
2. else low=x
3. Making a new better guess i.e., guess=(low+high)/2.
 If the absolute error of our guess is less than epsilon then exit the loop.
Absolute Error: Absolute Error can be calculated as abs(guessn -x)
// C++ Program to find
// n-th real root of x
#include<bits/stdc++.h>
using namespace std;
void findNthRoot(double x, int n)
{

// Initialize boundary values

double low, high;
if (x >= 0 and x <= 1)
{
low = x;
high = 1;
}
else
{
low = 1;
high = x;
}

// used for taking approximations

// of the answer
double epsilon = 0.00000001;

// Do binary search
double guess = (low + high) / 2;
while (abs((pow(guess, n)) - x) >= epsilon)
{
if (pow(guess, n) > x)
{
high = guess ;
}
else
{
low = guess ;
}
guess = (low + high) / 2;
}

cout << fixed << setprecision(16)

<< guess;
}

// Driver code
int main()
{
double x = 5;
int n = 2;
findNthRoot(x, n) ;
}

// This code is contributed

Output:
2.2360679768025875

Explanation of first example with epsilon = 0.01

Since taking too small value of epsilon as taken in our program might not
be feasible for
explanation because it will increase the number of steps drastically so
for the sake of
simplicity we are taking epsilon = 0.01
The above procedure will work as follows:

Say we have to calculate the then x = 5, low = 1, high = 5.

Taking epsilon = 0.01
First Guess:
guess = (1 + 5) / 2 = 3
Absolute error = |32 - 5| = 4 > epsilon
guess2 = 9 > 5(x) then high = guess --> high = 3

Second Guess:
guess = (1 + 3) / 2 = 2
Absolute error = |22 - 5| = 1 > epsilon
guess2 = 4 > 5(x) then low = guess --> low = 2

Third Guess:
guess = (2 + 3) / 2 = 2.5
Absolute error = |2.52 - 5| = 1.25 > epsilon
guess2 = 6.25 > 5(x) then high = guess --> high = 2.5

and proceeding so on we will get the correct up to 2 decimal places

i.e., = 2.23600456
We will ignore the digits after 2 decimal places since they may or may not
be correct.
Find square root of number upto given precision using
binary search
Given a positive number n and precision p, find the square root of number upto p decimal
places using binary search.
Examples:
Input : number = 50, precision = 3

Output : 7.071

Input : number = 10, precision = 4

Output : 3.1622

Approach :
1) As the square root of number lies in range 0 <= squareRoot <= number, therefore,
initialize start and end as : start = 0, end = number.
2) Compare the square of mid integer with the given number. If it is equal to the number,
then we found our integral part, else look for the same in left or right side depending upon
the scenario.
3) Once we are done with finding the integral part, start computing the fractional part.
4) Initialize the increment variable by 0.1 and iteratively compute the fractional part upto p
places. For each iteration, increment changes to 1/10th of it’s previous value.
5) Finally return the answer computed.
Below is the implementation of above approach :
// C++ implementation to find
// square root of given number
// upto given precision using
// binary search.
#include <bits/stdc++.h>
using namespace std;

// Function to find square root

// of given number upto given
// precision
float squareRoot(int number, int precision)
{
int start = 0, end = number;
int mid;

// variable to store the answer

float ans;
 // for computing integral part
// of square root of number
while (start <= end) {
mid = (start + end) / 2;
if (mid * mid == number) {
ans = mid;
break;
}

// incrementing start if integral

// part lies on right side of the mid
if (mid * mid < number) {
start = mid + 1;
ans = mid;
}

// decrementing end if integral part

// lies on the left side of the mid
else {
end = mid - 1;
}
}

// For computing the fractional part

// of square root upto given precision
float increment = 0.1;
for (int i = 0; i < precision; i++) {
while (ans * ans <= number) {
ans += increment;
}

// loop terminates when ans * ans > number

ans = ans - increment;
increment = increment / 10;
}
return ans;
}

// Driver code
int main()
{
// Function calling
cout << squareRoot(50, 3) << endl;
 // Function calling
cout << squareRoot(10, 4) << endl;

return 0;
}
Output :
7.071
3.1622
Time Complexity : The time required to compute the integral part is O(log(number)) and
constant i.e, = precision for computing the fractional part. Therefore, overall time
complexity is O(log(number) + precision) which is approximately equal to O(log(number))

A temple of Snakes
You want to build a temple for snakes. The temple will be built on a mountain range, which
can be thought of as n blocks, where height of i-th block is given by hi. The temple will be
made on a consecutive section of the blocks and its height should start from 1 and increase
by exactly 1 each time till some height and then decrease by exactly 1 each time to height
1, i.e. a consecutive section of 1, 2, 3, .. x-1, x, x-1, x-2, .., 1 can correspond to a temple.
Also, heights of all the blocks other than of the temple should have zero height, so that the
temple is visible to people who view it from the left side or right side.

You want to construct a temple. For that, you can reduce the heights of some of the blocks.
In a single operation, you can reduce the height of a block by 1 unit. Find out minimum
number of operations required to build a temple.

Input

The first line of the input contains an integer T denoting the number of test cases. The
description of T test cases follows.

The first line of each test case contains an integer n.

The next line contains n integers, where the i-th integer denotes hi

Output

For each test case, output a new line with an integer corresponding to the answer of that
testcase.

Constraints
 1 ≤ T ≤ 10
 2 ≤ n ≤ 105
 1 ≤ hi ≤ 109

Example
Input

121

1121

12621

Output

Explanation

Example 1. The entire mountain range is already a temple. So, there is no need to make
any operation.

Example 2. If you reduce the height of the first block to 0. You get 0 1 2 1. The blocks 1, 2,
1 form a temple. So, the answer is 1.

Example 3. One possible temple can be 1 2 3 2 1. It requires 3 operations to build. This is

the minimum amount you have to spend in order to build a temple.
Lowest Sum
The Head Chef is studying the motivation and satisfaction level of his chefs . The motivation
and satisfaction of a Chef can be represented as an integer . The Head Chef wants to know
the N th smallest sum of one satisfaction value and one motivation value for various values
of N . The satisfaction and motivation values may correspond to the same chef or different
chefs . Given two arrays, the first array denoting the motivation value and the second array
denoting the satisfaction value of the chefs . We can get a set of sums(add one element
from the first array and one from the second). For each query ( denoted by an integer qi ( i =
1 to Q ) , Q denotes number of queries ) , find the qi th element in the set of sums ( in non-
decreasing order ) .

Input

 The first line of the input contains an integer T denoting the number of test cases. The
description of T test cases follows.
 The first line of each test case contains a two space seperated integers K and Q
denoting the number of chefs and the number of queries .
 The second line of each test case contains K space-separated integers A1, A2, ..., AK
denoting the motivation of Chefs.
 The third line of each test case contains K space-separated integers B1, B2, ..., BK
denoting the satisfaction of Chefs.
 The next Q lines contain a single integer qi ( for i = 1 to Q ) , find the qi th element in the
set of sums .

Output

 For each query of each test case, output a single line containing the answer to the query
of the testcase

Constraints

Should contain all the constraints on the input data that you may have. Format it like:

 1≤T≤5
 1 ≤ K ≤ 20000
 1 ≤ Q ≤ 500
 1 ≤ qi ( for i = 1 to Q ) ≤ 10000
 1 ≤ Ai ≤ 10^18 ( for i = 1 to K )
 1 ≤ Bi ≤ 10^18 ( for i = 1 to K )

Example
Input:
1

31

123

456

Output:

Explanation

Example case 1. There are 9 elements in the set of sums :

1+4=5
2+4=6
1+5=6
1+6=7
2+5=7
3+4=7
2+6=8
3+5=8
3+6=9
The fourth smallest element is 7.

Find an element in hidden array

There is an array of length N consisting of non-negative integers. The array is sorted in non-
decreasing order. Each number in the array appears exactly K times, except one element,
which appears at least once, but less than K times. Your task is to identify that element.

This is an interactive problem. You are only given the integer N in the input. Both the array
and the value of K are hidden. You are allowed to ask the judge the following queries: What
is the value of the element at index i of the array? Identify the value of the element with
frequency less than K by asking at most 60 such queries.

Input and Output

The first line of the input contains a single integer T denoting the number of test cases.

For each test case, you should start by reading a single line containing one integer N from
the input.

You can interact with the judge using the standard input and output. There are two types of
operations: to perform one operation, you should print to the standard output a line
containing two space-separated integers type and val.

 If type = 1, you are asking the judge a query for the value of the element of the array at
index val. After printing this line, the judge will print to the standard input a line
containing one integer corresponding to the value of the element at index val.
 If type = 2, you are telling the judge that the element with frequency less than K is val.
For each test case, you should perform this operation exactly once at the end. This is
not counted towards the 60 queries.

Note

Don't forget to flush the standard output after printing each line. It can be done using
fflush(stdout) in C/C++, System.out.flush() in Java and sys.out.flush() in Python.

If you ask more than 60 queries, your program will get the verdict Wrong Answer.

Constraints

 1 ≤ T ≤ 104
 3 ≤ N ≤ 105
 2≤K≤N-1
 each element of the array lies between 1 and 109 inclusive

Example
Input / judge feedback your output

1 2

1 3

5
 1 1

25

Explanation

Example case 1: Suppose the array is [1, 1, 5]. Note that the value of K is 2, but it is
hidden from you.

In the first query, you request the value of the 2nd element and the judge answers 1. Then
you request the value of the 3rd element and the judge answers 5, then the value of the first
element and the judge answers 1.

Now, you tell the judge that the answer is 5. You made a total of 3 queries.

Our Base is Under Attack

Chef has recently learned about number bases and is becoming fascinated.

Chef learned that for bases greater than ten, new digit symbols need to be introduced, and
that the convention is to use the first few letters of the English alphabet. For example, in
base 16, the digits are 0123456789ABCDEF. Chef thought that this is unsustainable; the
English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is
no problem for Chef, because Chef is very creative and can just invent new digit symbols
when she needs them. (Chef is very creative.)

Chef also noticed that in base two, all positive integers start with the digit 1! However, this is
the only base where this is true. So naturally, Chef wonders: Given some integer N, how
many bases b are there such that the base-b representation of N starts with a 1?

Input

The first line of the input contains an integer T denoting the number of test cases. The
description of T test cases follows.

Each test case consists of one line containing a single integer N (in base ten).

Output
For each test case, output a single line containing the number of bases b, or INFINITY if
there are an infinite number of them.

Constraints

Subtasks
Subtask #1 (16 points):

 1 ≤ T ≤ 103
 0 ≤ N < 103
Subtask #2 (24 points):

 1 ≤ T ≤ 103
 0 ≤ N < 106
Subtask #3 (28 points):

 1 ≤ T ≤ 103
 0 ≤ N < 1012
Subtask #4 (32 points):

 1 ≤ T ≤ 105
 0 ≤ N < 1012

Example
Input:

11

24

Output:

8
14

Explanation

In the first test case, 6 has a leading digit 1 in bases 2, 4, 5 and 6: 610 = 1102 = 124 = 115 =
106.