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

Commit a0e0720

Browse files
Tamada4aTamada4a
committed
Added solution of Yandex Contest/Training on algorithms 5.0/Lesson 3/C. Deleting numbers
1 parent de74c4b commit a0e0720

File tree

3 files changed

+152
-0
lines changed

3 files changed

+152
-0
lines changed

‎Yandex Contest/Training on algorithms 5.0/Lesson 3/C. Deleting numbers/Main.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
import java.io.BufferedReader;
2+
import java.io.FileReader;
3+
import java.io.IOException;
4+
import java.util.ArrayList;
5+
import java.util.TreeMap;
6+
7+
public class Main {
8+
public static void main(String[] args) {
9+
// The corresponding value is stored in this variable
10+
int n = Integer.MAX_VALUE;
11+
12+
// This TreeMap will store pairs <number : number of repetitions>.
13+
// We use TreeMap, because an ordered sequence of keys will be required when calculating the
14+
// answer
15+
TreeMap<Integer, Integer> integersMap = new TreeMap<>();
16+
17+
// Reading data
18+
try (BufferedReader reader = new BufferedReader(new FileReader("input.txt"))) {
19+
String line;
20+
while ((line = reader.readLine()) != null) {
21+
if (n == Integer.MAX_VALUE)
22+
n = Integer.parseInt(line);
23+
else {
24+
String[] arrayOfInts = line.split(" ");
25+
// Filling in the TreeMap. If there is no element, add a new one with a value of 0
26+
for (String num : arrayOfInts) {
27+
int numInt = Integer.parseInt(num);
28+
if (!integersMap.containsKey(numInt))
29+
integersMap.put(numInt, 0);
30+
integersMap.put(numInt, integersMap.get(numInt) + 1);
31+
}
32+
}
33+
}
34+
} catch (IOException e) {
35+
e.printStackTrace();
36+
}
37+
38+
39+
// If we have one unique number, we do not delete anything, because the difference between them
40+
// is 0
41+
if (integersMap.size() == 1)
42+
System.out.print(0);
43+
else {
44+
// We make a list of the set of keys in order to iterate and compare them
45+
ArrayList<Integer> listOfNums = new ArrayList<>(integersMap.keySet());
46+
47+
// Creating a variable that will store the maximum
48+
int max = Integer.MIN_VALUE;
49+
for (int i = 0; i < listOfNums.size() - 1; ++i) {
50+
// We only work with a pair of numbers that differ by a maximum of 1
51+
if (Math.abs(listOfNums.get(i + 1) - listOfNums.get(i)) > 1)
52+
continue;
53+
54+
// We count their total number of repetitions. We need to remove the minimum number of
55+
// numbers, so we need to find the maximum number of numbers that differ by 1 from each other
56+
int sum = integersMap.get(listOfNums.get(i + 1)) + integersMap.get(listOfNums.get(i));
57+
if (sum > max)
58+
max = sum;
59+
}
60+
61+
// If we do not have numbers that differ by 1, then we set max = 1, that is, it will be
62+
// necessary to remove n - 1 numbers so that one number remains in the sequence, which
63+
// differs by 0 by itself
64+
if (max == Integer.MIN_VALUE)
65+
max = 1;
66+
67+
System.out.print(n - max);
68+
}
69+
}
70+
}

‎Yandex Contest/Training on algorithms 5.0/Lesson 3/C. Deleting numbers/README.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
# C. Deleting numbers
2+
<table>
3+
<tr>
4+
<td>Time limit</td>
5+
<td>1 second</td>
6+
</tr>
7+
<tr>
8+
<td>Memory limit</td>
9+
<td>256Mb</td>
10+
</tr>
11+
<tr>
12+
<td>Input</td>
13+
<td>standart input or input.txt</td>
14+
</tr>
15+
<tr>
16+
<td>Output</td>
17+
<td>standart output or output.txt</td>
18+
</tr>
19+
</table>
20+
21+
Given an array <i>a</i> of <i>n</i> numbers. Find the minimum number of numbers after deleting which the pairwise difference of the remaining
22+
numbers modulo will not exceed 1, that is, after deleting, no number should differ from any other by more than 1.
23+
24+
## Input format
25+
The first line contains a single integer <i>n</i> (1 ≤ <i>n</i> ≤ 2·10<sup>5</sup>) — the number of elements of the array < 10000 i>a</i>.
26+
27+
The second line contains <i>n</i> integers <i>a<sub>1</sub></i>, <i>a<sub>2</sub></i>, …, <i>a<sub>n</sub></i> (0 ≤ <i>a<sub>i</sub></i>≤ 10<sup>5</sup>) — elements of the array <i>a</i>.
28+
29+
## Output format
30+
Print one number — the answer to the problem.
31+
32+
## Example 1
33+
| Input | Output |
34+
|:----------------|:-------|
35+
| 5</br>1 2 3 4 5 | 3 |
36+
37+
## Example 2
38+
| Input | Output |
39+
|:---------------------------|:-------|
40+
| 10</br>1 1 2 3 5 5 2 2 1 5 | 4 |

‎Yandex Contest/Training on algorithms 5.0/Lesson 3/C. Deleting numbers/README_RU.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# C. Удаление чисел
2+
<table>
3+
<tr>
4+
<td>Ограничение времени</td>
5+
<td>1 секунда</td>
6+
</tr>
7+
<tr>
8+
<td>Ограничение памяти</td>
9+
<td>256Mb</td>
10+
</tr>
11+
<tr>
12+
<td>Ввод</td>
13+
<td>стандартный ввод или input.txt</td>
14+
</tr>
15+
<tr>
16+
<td>Вывод</td>
17+
<td>стандартный вывод или output.txt</td>
18+
</tr>
19+
</table>
20+
21+
Дан массив <i>a</i> из <i>n</i> чисел. Найдите минимальное количество чисел, после удаления которых попарная разность
22+
оставшихся чисел по модулю не будет превышать 1, то есть после удаления ни одно число не должно отличаться от какого-либо
23+
другого более чем на 1.
24+
25+
## Формат ввода
26+
Первая строка содержит одно целое число <i>n</i> (1 ≤ <i>n</i> ≤ 2⋅10<sup>5</sup>) — количество элементов массива <i>a</i>.
27+
28+
Вторая строка содержит <i>n</i> целых чисел <i>a<sub>1</sub></i>, <i>a<sub>2</sub></i>, …, <i>a<sub>n</sub></i>
29+
(0 ≤ <i>a<sub>i</sub></i> ≤ 10<sup>5</sup>) — элементы массива <i>a</i>.
30+
31+
## Формат вывода
32+
Выведите одно число — ответ на задачу.
33+
34+
## Пример 1
35+
| Ввод | Вывод |
36+
|:----------------|:------|
37+
| 5</br>1 2 3 4 5 | 3 |
38+
39+
## Пример 2
40+
| Ввод | Вывод |
41+
|:---------------------------|:------|
42+
| 10</br>1 1 2 3 5 5 2 2 1 5 | 4 |

0 commit comments

Comments
 (0)
0