| Problem description | | Progress |
|
Темы:
Binary search in an array
Требуется определить в заданном массиве количество элементов, равных искомому числу.
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.
Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше предыдущего.
В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.
В четвертой строке вводится M натуральных чисел, не превосходящих 109.
Выходные данные
Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.
Если в массиве нет такого числа, выведите 0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 2 4
4
1 4 3 2 |
1
1
0
2 |
| |
![]()
|
|
Темы:
Binary search in an array
Implement a binary search algorithm.
Input:
- the first line of the input contains natural numbers N and K (\(0<N,\ K < ;= 100000\));
- the second line contains N elements of the first array, sorted in ascending order;
- on the third line – K elements of the second array.
The elements of both arrays are integers, each of which does not exceed \(10^9\).
Output: required for each of the K numbers to print in a separate line "YES" ; if this number occurs in the first array, and "NO" otherwise.
Examples
| # |
Input |
Output |
| 1 |
105
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
|
NO
NO
YES
YES
NO
|
| |
![]()
|
|
Темы:
Binary search in an array
Given two lists of numbers, the numbers in the first list are in non-descending order. For each number in the second list, determine the number of the first and last occurrence of that number in the first list.
Input:
- the first line of the input contains two numbers N and M (\(1<=N,\ M <=20000\));
- the second line contains N non-decreasing integers — elements of the first list;
- the third line contains M of non-negative integers - elements of the second list.
All numbers in the lists are 32-bit signed integers.
Output: The program should output M lines. For each number from the second list, print the number of its first and last occurrence in the first list. The numbering starts from one. If the number is not included in the first list, you need to print a single number 0.
Examples
| # |
Input |
Output |
| 1 |
105
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
|
10 10
3 4
7 7
1 2
0
|
| |
![]()
|
|
Темы:
Dynamic Programming: One Parameter
Binary search in an array
The spacebar does not work on Vasya's keyboard. Therefore, he is now typing all the texts together. Write a program that will split the text typed by Vasya into words from the given dictionary.
Input
First, the input of the program receives the text entered by Vasya – one line of no more than 100 Latin lowercase letters. The next input line specifies the value N – the number of words in the dictionary (N – is a natural number not exceeding 2000). The next N lines contain words from the – one word per line, each word contains no more than 20 Latin lowercase letters. The words are written in alphabetical order.
Imprint
Print Vasya's text with spaces between words (a space after the last word is acceptable). If there are several options for splitting the string into words, print any of them. It is guaranteed that at least one way to split a string into dictionary words exists.
Examples
| # |
Input |
Output |
| 1 |
whatcanido
6
a
an
can
do
i
what |
what can i do |
| |
![]()
|
|
Темы:
Binary search in an array
Prefix sums(minimums, ...)
Volodya wants to beautifully congratulate his wife on their wedding anniversary and is going to give her a bouquet of n flowers.
Arriving at a flower shop, Volodya discovered that a bouquet can be made from flowers of m different types, and the number of flowers of each type is not limited. Volodya knows that the first flower of the i-th species in the bouquet makes his wife happier by ai, and each next flower
this way she becomes happier on bi. That is, if in the bouquet xi > 0 flowers of type i, then flowers of this type make Volodya's wife happier by ai + (xi − 1) · bi.
Like any loving husband, Volodya wants to please his wife as much as possible. Therefore he wants to know by what maximum amount her happiness can increase from a bouquet, picked from the flowers available in the store.
Input data format
The first line contains two integers n and m (1 ≤ n ≤ 109 , 1 ≤ m ≤ 100 000) — required
the number of flowers in the bouquet and the number of flowers available.
Each of the following m lines describes the i-th kind of flowers and contains two integers ai and bi (0 ≤ ai , bi ≤ 109 ) — an increase in happiness from the first flower of the i-th species and an increase in happiness from each subsequent flower of this species.
Output data format
In a single line print a single number — the maximum increase in happiness that Volodya's wife can get from a bouquet of n flowers.
Examples
| # |
Input |
Output |
| 1 |
4 3
50
14
2 2 |
14 |
| 2 |
5 3
5 2
4 2
3 1
| 16 |
| |
![]()
|
|
Темы:
Binary search in an array
Binary search by answer
Greedy Algorithm
In order to improve the landscape architecture and environmental situation, the municipal administration has developed a draft program for greening the central avenue. According to the project, on one side of the avenue, it is planned to plant trees of K different species in a row, for which tree seedlings were purchased, and ai seedlings were purchased.
To achieve the aesthetic perfection of the planted row of trees, it is required that among any P consecutive trees, all trees be of different species. If the number of trees in a row is less than P, then they must all be different.
It is required to write a program that finds the maximum number of trees in an aesthetically perfect row planted from purchased seedlings.
Input
The first line contains two integers: K — number of different tree species (1 ≤ K ≤ 100,000), and P — the required number of consecutive trees of different species (2 ≤ P ≤ K). The next K lines of input data contain integers ai, specifying the number of purchased tree seedlings of the i-th type (1 ≤ ai ≤ 109), by one number per line.
Imprint
Print a single number — the maximum number of trees that, planted in a row in some order, achieves aesthetic perfection.
Examples
| # |
Input |
Output |
| 1 |
3 3
1
200
1 |
4 |
| |
![]()
|
|
Темы:
Dynamic programming
Using sort
Binary search in an array
The restaurant received n orders for a banquet. Each order is characterized by two values: the start time of the banquet li and the end time ri (li ≤ r i).
The restaurant management can either accept the order or reject it. What is the maximum number of orders that can be accepted?
No two accepted orders can intersect, that is, there should not be a point in time that belongs to two accepted orders at once. If one of the orders starts at the same time as the other ends, then they cannot be accepted together.
Input:
The first line contains an integer n (1 ≤ n ≤ 200000) — the number of orders. Each of the next n lines contains a pair of integers li, ri (0 ≤ li &le ; ri ≤ 109).
Output:
Print the maximum number of orders that can be accepted.
Examples:
| Input |
Output |
2
7 11
4 7 |
1 |
5
1 2
23
34
4 5
5 6 |
3 |
6
48
15
47
25
1 3
68 |
2 |
| |
![]()
|
|
Темы:
Binary search in an array
Dynamic programming
Greedy Algorithm
At the Interregional Robot Programming Olympiad, competitions are held in one round and in an unusual format. The tasks are given to the participants sequentially, not all at the very beginning of the round, and each i-th task (1 ≤ i ≤ n) becomes available to the participants at its time si. Upon receipt of the next task, each participant must immediately determine whether he will solve it or not. If he chooses to solve this problem, then he has ti minutes to submit its solution for verification, and during this time he cannot switch to solving another problem. If the participant refuses to solve this problem, then in the future he cannot return to it. At the moment when the time allotted for the task that the participant is solving has ended, he can start solving another task that became available at the same moment, if there is such a task, or wait for another task to appear. At the same time, for the correct solution of the i-th problem, the participant receives ci points.
Artur, who represents one of the regional artificial intelligence centers at the interregional Olympiad, understands that not only the ability to solve problems, but also the correct strategic calculation of which problems need to be solved and which ones to skip, plays an important role at such an Olympiad. He, like all participants, before the start of the tour knows at what point in time each task will become available, how much time will be allotted for its solution and how many points you can get for solving it. Artur is a talented student and therefore will be able to successfully solve any problem he chooses to solve at the Olympiad in the allotted time and pass for verification.
It is required to write a program that determines the maximum number of points Arthur can get with the optimal choice of problems that he will solve, as well as the number and list of such problems.
Input
The first line contains one integer n (1 ≤ n ≤ 105) the number of problems in the Olympiad.
The next n lines contain descriptions of the problems, three numbers on each line: si the moment the i-th problem appears in minutes, ti the time allotted for its solution in minutes, and ci how many points the participant will receive for solving this problem (1 ≤ si, ti, ci ≤ 109).
Imprint
First line must contain a single number – the maximum number of points that Arthur can get at the Olympiad.
The second line should contain one integer m - the number of tasks to be solved with the optimal choice.
The third line should contain m space-separated integers - the numbers of these problems in the order in which they were solved. The tasks are numbered, starting from one, in the order they are described in the input file.
If there are several optimal answers, print any of them.
Examples
| # |
Input |
Output |
| 1 |
2
1 1 1
2 2 2
| 3
2
1 2
|
| 2 |
3
1 2 1
3 2 1
2 4 3
| 3
1
3 |
| |
![]()
|
|
Темы:
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 |
| |
![]()
|
|
Темы:
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.
| |
![]()
|
|
Темы:
Binary search in an array
It is required to determine the number of the leftmost and rightmost element in the given array equal to the desired number.
Input
The first line contains one natural number N not exceeding 105: the number of numbers in the array.
The second line contains N natural numbers not exceeding 109, each successive number is at least as great.
The third line contains the number of numbers to be searched for M - a natural number not exceeding 106.
The fourth line contains M of natural numbers not exceeding 109.
Imprint
For each query, print two numbers separated by a space on a separate line: the number of the element of the leftmost and rightmost elements of the array equal to the number-query. Array elements are numbered starting from one.
If there is no such number in the array, print two space-separated zeros in the corresponding line.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 2 3
4
4 3 2 1
|
0 0
4 4
2 3
1 1
|
| |
![]()
|
|
Темы:
Binary search in an array
Given an array of n numbers, sorted in non-decreasing order, and k queries. For each query print the maximum number of the array element not greater than the given one (numbering of array elements starts from 1).
Input
The first line of the input contains numbers n and k (0 < n, k <= 105 ) — array length and number of requests. The second line contains the n elements of an array sorted in non-descending order. The third line contains k requests. All array elements and — integers, each of which does not exceed 2⋅109 .
Output
For each of k queries, output the maximum number of the array element not greater than the given one. If there are none, print 0.
Examples
| # |
Input |
Output |
| 1 |
5 5
3 3 5 8 9
2 4 8 1 10
|
0
2
4
0
5
|
| |
![]()
|
|
Темы:
Binary search in an array
Given an array a of n integers a1, a2,..., an. Learn how to answer questions quickly "How many numbers have values from l to r"?
Input
The first line contains an integer n (1<=n<=105) — the length of the array. The second line contains n integers a1, a2,..., an (−109<=ai<=109). The third line contains an integer k (1<=k<=105) — number of requests. The following k lines contain pairs of numbers l r (−109<=l<=r<=10 9).
Output
Print k numbers (each on a separate line) responses.
Examples
| # |
Input |
Output |
| 1 |
5
10 1 10 3 4
4
1 10
29
3 4
2 2
|
5
2
2
0
|
| |
![]()
|
|
Темы:
Binary search in an array
Given an array of n numbers, sorted in non-increasing order, and k queries. For each query, print the maximum number of the array element greater than the given one (numbering of array elements starts from 1).
Input
The first line of the input contains numbers n and k (0 < n, k <= 105 ) — array length and number of requests. The second line contains the n elements of an array sorted in non-ascending order. The third line contains k requests. All array elements and — integers, each of which does not exceed 2⋅109 .
Output
For each of k queries, output the maximum number of the array element greater than the given one. If there are none, print 0.
Examples
| # |
Input |
Output |
| 1 |
5 5
9 8 5 3 3
2 4 8 1 10
|
5
3
1
5
0
|
| |
![]()
|
|
Темы:
Binary search in an array
Given an array of n numbers, sorted in non-decreasing order, and k queries. For each query, print the maximum number of the array element less than the given one (numbering of array elements starts from 1).
Input
The first line of the input contains numbers n and k (0 < n, k <= 105 ) — array length and number of requests. The second line contains the n elements of an array sorted in non-descending order. The third line contains k requests. All array elements and — integers, each of which does not exceed 2⋅109 .
Output
For each of k queries, print the maximum number of the array element less than the given one. If there are none, print 0.
Examples
| # |
Input |
Output |
| 1 |
5 5
3 3 5 8 9
2 4 8 1 10
|
0
2
3
0
5
|
| |
![]()
|
|
Темы:
Binary search in an array
Given an array of n numbers, sorted in non-increasing order, and k queries. For each query, print the minimum array element number less than the given one (numbering of array elements starts from 1).
Input
The first line of the input contains numbers n and k (0 < n, k <= 105 ) — array length and number of requests. The second line contains the n elements of an array sorted in non-ascending order. The third line contains k requests. All array elements and — integers, each of which does not exceed 2⋅109 .
Output
For each of k queries print the minimum nbsp;number of the array element less than the given one. If there are none, print 0.
Examples
| # |
Input |
Output |
| 1 |
5 5
9 8 5 3 3
2 4 8 1 10
|
0
4
3
0
1
|
| |
![]()
|
|
Темы:
"Two Pointers"
Binary search in an array
Uncle Fyodor, the cat Matroskin and Sharik decided to update the fence around their garden in Prostokvashino. Matroskin and Sharik, without thinking twice, dug N pillars along one of the sides of the site. This upset Uncle Fyodor very much, as his friends forgot about the most important — the gate had to be exactly on this side, and for it it was necessary to leave an opening with a width of at least W. Now they will have to dig out some posts.
To keep your work from going to waste, dig as few posts as possible. Help Uncle Fyodor determine which pillars to dig. After digging out the posts, there must be a gap (between the two remaining posts, or between the remaining post and the end of the side of the lot, or between the two ends of the side of the lot) of a width greater than or equal to W.
Input
The first line contains two integers N and W — the number of dug-in poles and the minimum required width of the opening for the gate, respectively. It is guaranteed that 0<=N<=30000 and that 0<=W<=60000.
We will assume that the coordinate axis is introduced along the side of the site that interests us. The second line of the input file contains two numbers L and R — coordinates of the left and right end of this side (LR). This is followed by N numbers — the coordinates of the dug-in pillars. All coordinates (including L and R) — different integers, modulo not exceeding 30000. It is guaranteed that all posts are dug between the left and right ends of the side.
Output
The first line of the output file should contain the minimum number of posts to be dug. The numbers of these pillars should follow. The columns are numbered in the order they are specified in the input file, starting from 1.
If there are multiple solutions, you can output any one. If there is no solution, then output one line containing the number -1 to the output file.
| Input |
Output |
|
3 2
2 6
3 4 5
|
1
2 |
|
3 2
16
4 3 5
|
0 |
|
3 5
1 7
5 3 4
|
3
2
1
3
|
| |
![]()
|