Binary search

Plus

Problem description Progress

ID 32967. The best place

In the waiting room at the station there are N rows of M seats. So that those who are waiting do not get bored, K powerful Wi-Fi routers are installed instead of some chairs. Those who are waiting try to take places closer to the routers, as then they will be able to watch videos from Youtube or VK with a higher resolution, without delay. If the passenger is seated in seat number c in row r, and the i-th router is seated in seat C_i in row R_i, then the distance to the i-th router is calculated as max(|r−R_i|,|c−C_i|), where |x| – the absolute value of x. Seats in the waiting room were given priority from 1 to N⋅M−K, smaller numbers received seats with a shorter distance to the nearest router, among seats with the same distance to routers, the seats in the row with the smaller number are considered more comfortable, and among them &mdash ; with the lower number in the row. The figure shows seat priority in a waiting room with 4 rows of 7 seats, in which 2 routers are installed (their positions are marked in black). Armchairs located at a distance of 1 from the routers are highlighted in dark gray, light gray — at a distance of 2, white — 3.

Write a program that calculates the distance to the nearest router from a chair with some given priority.

The first line of input contains four integers — number of rows N (2 ≤ N ≤ 10⁹) and seats in row M (2 ≤ M ≤ 10⁹), number of routers K (1 ≤ K < 100, K < N⋅ M), number of requests Q (1 < Q < 100). This is followed by K lines containing two integers — location of routers: row number Ri (1 ≤ R_i ≤ N) and location number in row C_i (1 ≤ С_i ≤M). None of them match. This is followed by a line containing Q integers ranging from 1 to N⋅M−K – seat priorities.

Output for each query on a separate line one integer — distance to the nearest router from a chair with a given priority.

Input	Output
4 7 2 4 2 5 4 4 1 6 16 26	1 1 2 3

ID 33009. Binary search complexity

Темы: Binary search Binary search in an array

Vasya guessed a number from 1 to N. What is the least number of questions (to which Vasya answers "yes" or "no") that Petya can guess Vasya's number?

Input

One number N is entered

Output

Print the least number of questions that are guaranteed to be enough for Petya to guess Vasya's number.

Input	Output
5	3

ID 34879. K-quest

Темы: Binary search Quick sort

In one of the computer quest games there is the following task. There are N characters on the map of the game world, each of which the player can meet. From communication with the i-th character, the player's karma changes by the value ai, which can be either positive or negative or even zero.

Initially, the player's karma is zero. In order to pass to the next level, you need to have karma exactly equal to the value of K, while karma can also take both positive and negative values.

The rooms where the characters are located are connected by one-way magical portals, so the player will have to meet the characters in a certain sequence: after the character number i, he gets to the character number i + 1, then to the character number i + 2, and so on. .d. There is no portal to another character in the room of the last character with number N.

To move between characters, you can also use teleportation spells, but unfortunately the hero has only two scrolls with spells left. Therefore, one of these scrolls will have to be used in order to teleport to any of the characters, and the second scroll — to leave the game world after the hero's karma reaches K.

Help the player determine which room to teleport to at the beginning and which room to leave the game world to reach Karma K, or tell them it's not possible.

Input
The first line of the input contains two numbers: the number of characters N and the required level of karma K (|K| ≤ 109, K ≠ 0). The second line contains N space-separated integers a1, a2, ..., aN — values by which the hero's karma changes after communicating with characters with numbers 1, 2, ..., N, respectively.

Imprint
Print the number of the room the player must enter and the number of the room from which the player must exit in order to collect karma K. big number. If it is impossible to achieve karma K by consistently communicating with the characters, then print a single number - 1.

Input	Output
5 3 -2 2 -1 2 4	2 4
7 1 1 -1 1 -1 1 -1 2	5 5
4 3 2 2 2 2	-1

ID 28311. nearest number

Темы: Binary search

Write a program that finds the element in an array that is closest in value to a given number.

Input:

- the first line contains one natural number N, not exceeding 1000 – array size;

- the second line contains N numbers – array elements (integers not exceeding 1000 in modulus);

- the third line contains one integer x, modulo not exceeding 1000.

Output: print the value of the array element closest to x. If there are several such numbers, print any of them.

Examples

#	Input	Output
1	5 1 2 3 4 5 6	5
2	5 5 4 3 2 1 3	3

ID 27279. Approximate Binary Search

Темы: Binary search Binary search in an array

Implement an approximate binary search algorithm.

Input:

- the first line of the input contains numbers N and K (\(0< N,\ K < 100001\));
- the second line contains N numbers of the first array, sorted in non-decreasing order;
- the third line contains K numbers of the second array.
Each number in both arrays does not exceed \(2 \cdot 10^9\).

Output: For each of the K numbers, print the number from the first array that is closest to the given number on a separate line. If there are several of them, print the smallest one.

Examples

#	Input	Output
1	5 5 1 3 5 7 9 2 4 8 1 6	1 3 7 1 5

ID 38466. Agar.io

Темы: Binary search Binary search by answer

In the multiplayer game Agar.io, players control bacteria. Each bacterium has size — a positive integer. If two bacteria of different sizes meet, the larger bacterium engulfs the smaller bacterium. In this case, the smaller bacterium disappears, and the size of the larger bacterium increases by the size of the smaller bacterium. If two bacteria of the same size meet, nothing happens. The winner is the player whose bacterium remains on the game
field one.
There are n players in the game, you are given the sizes of their bacteria. Determine which of the players have the opportunity to win in this game.

Input data format
The program receives an integer n, 1 ≤ n≤ 10⁵ — number of players. The next n lines contain one number each a_i — bacteria sizes, 1 ≤ a_i ≤ 10⁹. The numbers a_i are in non-decreasing order.
Output data format
The program should output n numbers equal to "0" or "1", one number per line. If the i-th number is equal to 0, then this means that the i-th player (whose bacterium size was originally
a_i) cannot under any circumstances win this game. If the i-th number is equal to 1, then this means that the i-th player has the opportunity to win in this game.

Examples

#	Input	Output	Explanation
1	4 1 1 3 4	0 0 1 1	In the example from condition 4, bacteria of size 1, 1, 3, 4. Bacteria of size 1 can't do anything eat, so they can't win. A size 4 bacterium can eat everyone. Bacteria size 3 can eat two bacteria in turn of size 1. Then her size will become 5, after that she can eat bacteria size 4 and win. Answer: 0, 0, 1, 1.

ID 39381. Harmonious sequence

Темы: Binary search Prefix sums(minimums, ...)

A series of lectures at the University of Flatland is devoted to the study of sequences.

The professor calls a sequence of integers \(a_1, a_2, ..., a_n\) harmonious if every number except \(a_1\) and \(a_n\), equals the sum of adjacent: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). For example, the sequence [1,2,1,–1] is harmonic because 2=1+1, and 1=2+(–1) .

Consider sequences of equal length: \(A=[a_1,a_2, ... a_n]\) and \(B=[b_1,b_2, ... b_n]\). The distance between these sequences will be called the value \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . For example, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2| ++|1–0|+|–1–0|=0+0+1+1=2 \)

At the end of the lecture, the professor wrote on the blackboard a sequence of n integers \(B=[b_1,b_2, ... b_n]\)and asked the students to find harmonious sequence \(A=[a_1,a_2, ... a_n]\) such that \(d( A, B)\) is minimal. To make it easier for himself to check, the professor asks you to write as an answer only the desired minimum distance \(d(A,B)\) .

It is required to write a program that, given a sequence B, determines at what minimum distance from sequence B there is a harmonic sequence A.

Input
The first line of the input file contains the integer n – the number of elements in the sequence ( \(3 \le n \le 300 000\)).

The second line contains n integers \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .< br />
Imprint
The output file must contain a single integer: the minimum possible distance from the sequence in the input file to a harmonic sequence.

Examples

#	Input	Output
1	4 1 2 0 0	2

ID 43351. Tommy's books

Темы: "Two Pointers" Binary search Implementation task

Tommy loves to read. He took n books from the library (in the ith book a_i pages, pages are numbered with < code>1). Tommy is very careful with books, so he wrapped each of them in a cover. But, since he did not have any transparent covers, he numbered the books from 1 to n and wrote the number on the cover of each book.

Tommy has been reading for m days in a row. He reads books strictly in order, starting with book number 1. Every day, he writes down on the board the total number of pages he has read so far.

For example, if Tommy took 2 books and, at the same time, there were 3 pages in the first book, and 5 pages in the second, then after reading 2 pages on the first day, and 4 pages on the second day, Tommy had on the board two numbers 2 and 6 would be written.

Tommy took a short break, and when he returned to reading, he realized that he had forgotten which book he was reading and which page he had stopped on. He also does not want to lose statistics, but wants to correct it by adding on what day which book he read and on which page he stopped. Help Tommy, by the numbers written on the board, to determine on what day what book he read and on what page he stopped.

Input
The program receives several lines as input. The first line contains two integers n and m (1 <= n, n <= 2·10⁵) - the number of books Tommy borrowed from the library and the number of days that Tommy read books. The second line contains the sequence a₁, a₂, ... a_n (1 <= a₁<= 10¹⁰), where a_i equals the number of pages in the ith book. The third line contains the sequence d₁, d₂, ... d_m (1 <= d_j<=a₁+ a₂+...+ a_n), where d_j equals the total number of pages read by Tommy by jth day. All d_j are in in ascending order.

Output

Output m lines. In each line print two numbers - нbook number k (1 <= k <= n) and page number in this book s (1 <= s <= a_k) that Tommy settled on for the current day.

Examples

#	Input	Output
1	3 6 10 15 12 1 9 12 13 15 17	1 1 19 2 2 23 25 27
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 29999999994