8000 Added solution of Yandex Contest/Training on algorithms 5.0/Lesson 4/… · Tamada4a/Algorithms@5734b7a · GitHub
[go: up one dir, main page]
Skip to content

Commit 5734b7a

Browse files
Tamada4aTamada4a
committed
Added solution of Yandex Contest/Training on algorithms 5.0/Lesson 4/A. Quick array search
1 parent f6b8302 commit 5734b7a

File tree

3 files changed

+184
-0
lines changed

3 files changed

+184
-0
lines changed

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/A. Quick array search/Main.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
import java.io.BufferedReader;
2+
import java.io.FileReader;
3+
import java.io.IOException;
4+
import java.util.ArrayList;
5+
import java.util.Comparator;
6+
7+
public class Main {
8+
public static void main(String[] args) {
9+
// The corresponding values will be stored in these variables
10+
int n = Integer.MAX_VALUE, k = Integer.MAX_VALUE;
11+
12+
// Array for numbers
13+
ArrayList<Integer> numbers = new ArrayList<>();
14+
15+
// The row for the final result
16+
StringBuilder result = new StringBuilder();
17+
18+
// Reading the data
19+
try (BufferedReader reader = new BufferedReader(new FileReader("input.txt"))) {
20+
String line;
21+
while ((line = reader.readLine()) != null) {
22+
if (n == Integer.MAX_VALUE)
23+
n = Integer.parseInt(line);
24+
else if (numbers.size() != n) {
25+
String[] numbersSplit = line.split(" ");
26+
for (String num : numbersSplit) {
27+
numbers.add(Integer.parseInt(num));
28+
}
29+
numbers.sort(Comparator.comparing(o -> o));
30+
} else if (k == Integer.MAX_VALUE)
31+
k = Integer.parseInt(line);
32+
else if (!line.isEmpty()) {
33+
String[] rangeSplit = line.split(" ");
34+
int l = Integer.parseInt(rangeSplit[0]);
35+
int r = Integer.parseInt(rangeSplit[1]);
36+
37+
// We calculate the difference between two function calls, because first we will find numbers less
38+
// than or equal to r, and then less than or equal to l - 1. The answer will be their difference
39+
result.append(String.format("%s ", findPosition(numbers, r) - findPosition(numbers, l - 1)));
40+
}
41+
}
42+
} catch (IOException e) {
43+
e.printStackTrace();
44+
}
45+
46+
System.out.print(result.toString().strip());
47+
}
48+
49+
50+
// A function for searching for a shifted left border
51+
private static int findPosition(ArrayList<Integer> numbers, int key) {
52+
// Setting the boundaries of the search. l will be the answer, because all numbers with indexes from 0 to l
53+
// inclusive will be in the specified range (first the numbers up to r, then up to l - 1)
54+
int l = -1, r = numbers.size();
55+
while (l + 1 < r) {
56+
int middle = (r + l) / 2;
57+
if (numbers.get(middle) <= key)
58+
l = middle;
59+
else
60+
r = middle;
61+
}
62+
return l;
63+
}
64+
}

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/A. Quick array search/README.md

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# A. Quick array search
2+
3+
<table>
4+
<tr>
5+
<td>Time limit</td>
6+
<td>3 seconds</td>
7+
</tr>
8+
<tr>
9+
<td>Memory limit</td>
10+
<td>64Mb</td>
11+
</tr>
12+
<tr>
13+
<td>Input</td>
14+
<td>standart input or input.txt</td>
15+
</tr>
16+
<tr>
17+
<td>Output</td>
18+
<td>standart output or output.txt</td>
19+
</tr>
20+
</table>
21+
22+
An array of <i>N</i> integers is given. All numbers from -10<sup>9</sup> to 10<sup>9</sup>.
23+
24+
You need to be able to answer queries like “How many numbers have values from <i>L</i> to <i>R</i>?”.
25+
26+
## Input format
27+
The number <i>N</i> (1 ≤ <i>N</i> ≤ 10<sup>5</sup>). Next <i>N</i> integers.
28+
29+
Then the number of requests <i>K</i> (1 ≤ <i>K</i> ≤ 10<sup>5</sup>).
30+
31+
Next <i>K</i> pairs of numbers <i>L</i>, <i>R</i> (-10<sup>9</sup> ≤ <i>L</i> ≤ <i>R</i> ≤ 10<sup>9</sup>) — the actual queries.
32+
33+
## Output format
34+
Print <i>K</i> numbers — answers to queries.
35+
36+
## Example
37+
<table>
38+
<thead>
39+
<tr>
40+
<th align= "left">Input</th>
41+
<th align= "left">Output</th>
42+
</tr>
43+
</thead>
44+
<tbody>
45+
<tr>
46+
<td>
47+
5</br>
48+
10 1 10 3 4</br>
49+
4</br>
50+
1 10</br>
51+
2 9</br>
52+
3 4</br>
53+
2 2
54+
</td>
55+
<td>
56+
5 2 2 0
57+
</td>
58+
</tr>
59+
</tbody>
60+
</table>

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/A. Quick array search/README_RU.md

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# A. Быстрый поиск в массиве
2+
3+
<table>
4+
<tr>
5+
<td>Ограничение времени</td>
6+
<td>3 секунды</td>
7+
</tr>
8+
<tr>
9+
<td>Ограничение памяти</td>
10+
<td>64Mb</td>
11+
</tr>
12+
<tr>
13+
<td>Ввод</td>
14+
<td>стандартный ввод или input.txt</td>
15+
</tr>
16+
<tr>
17+
<td>Вывод</td>
18+
<td>стандартный вывод или output.txt</td>
19+
</tr>
20+
</table>
21+
22+
Дан массив из <i>N</i> целых чисел. Все числа от −10<sup>9</sup> до 10<sup>9</sup>.
23+
24+
Нужно уметь отвечать на запросы вида “Cколько чисел имеют значения от <i>L</i> до <i>R</i>?”.
25+
26+
## Формат ввода
27+
Число <i>N</i> (1 ≤ <i>N</i> ≤ 10<sup>5</sup>). Далее <i>N</i> целых чисел.
28+
29+
Затем число запросов <i>K</i> (1 ≤ <i>K</i> ≤ 10<sup>5</sup>).
30+
31+
Далее <i>K</i> пар чисел <i>L</i>, <i>R</i> (−10<sup>9</sup> ≤ <i>L</i> ≤ <i>R</i> ≤ 10<sup>9</sup>) — собственно запросы.
32+
33+
## Формат вывода
34+
Выведите <i>K</i> чисел — ответы на запросы.
35+
36+
## Пример
37+
<table>
38+
<thead>
39+
<tr>
40+
<th align= "left">Ввод</th>
41+
<th align= "left">Вывод</th>
42+
</tr>
43+
</thead>
44+
<tbody>
45+
<tr>
46+
<td>
47+
5</br>
48+
10 1 10 3 4</br>
49+
4</br>
50+
1 10</br>
51+
2 9</br>
52+
3 4</br>
53+
2 2
54+
</td>
55+
<td>
56+
5 2 2 0
57+
</td>
58+
</tr>
59+
</tbody>
60+
</table>

0 commit comments

Comments
 (0)
0