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

Commit 8964aaa

Browse files
Tamada4aTamada4a
committed
Added solution of Yandex Contest/Training on algorithms 5.0/Lesson 4/B. One-dimensional naval battle
1 parent 5734b7a commit 8964aaa

File tree

3 files changed

+144
-0
lines changed

3 files changed

+144
-0
lines changed

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/B. One-dimensional naval battle/Main.java

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
import java.io.BufferedReader;
2+
import java.io.FileReader;
3+
import java.io.IOException;
4+
5+
public class Main {
6+
public static void main(String[] args) {
7+
// The corresponding value will be stored in this variable
8+
long n = Long.MAX_VALUE;
9+
10+
// Reading the data
11+
try (BufferedReader reader = new BufferedReader(new FileReader("input.txt"))) {
12+
String line;
13+
while ((line = reader.readLine()) != null) {
14+
if (n == Long.MAX_VALUE)
15+
n = Long.parseLong(line);
16+
}
17+
} catch (IOException e) {
18+
e.printStackTrace();
19+
}
20+
System.out.print(rBinSearch(n));
21+
}
22+
23+
// We implement a right-hand binary search
24+
private static long rBinSearch(long n) {
25+
long l = 0, r = n;
26+
while (l < r) {
27+
long middle = (r + l + 1) / 2;
28+
if (checkK(middle, n))
29+
l = middle;
30+
else
31+
r = middle - 1;
32+
}
33+
return l;
34+
}
35+
36+
// A function for checking k for correctness
37+
private static boolean checkK(long k, long n) {
38+
// We create a variable from which we will subtract the occupied cells
39+
long dif = n;
40+
41+
// We keep the starting value of k
42+
long startK = k;
43+
44+
// The counter of the placed ships
45+
long counter = 0;
46+
while (k > 0) {
47+
// Counting the number of ships placed in the current iteration
48+
counter += (startK - k + 1);
49+
50+
// Counting the number of occupied cells
51+
dif -= (startK - k + 1) * k;
52+
53+
// Early exit from the function. If there is no room left for ships now, we go out
54+
if (dif < 0)
55+
return false;
56+
57+
k -= 1;
58+
}
59+
// Subtract the number of spaces between the ships
60+
dif -= counter - 1;
61+
62+
// If there are still places left or we have placed them side by side - true. Otherwise, false
63+
return dif >= 0;
64+
}
65+
}

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/B. One-dimensional naval battle/README.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
# B. One-dimensional naval battle
2+
3+
<table>
4+
<tr>
5+
<td>Time limit</td>
6+
<td>2 seconds</td>
7+
</tr>
8+
<tr>
9+
<td>Memory limit</td>
10+
<td>256Mb</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+
The field in the game of one-dimensional naval combat has dimensions of 1 × <i>n</i>. Your task is to find such a maximum <i>k</i> that one ship of size
23+
1 × <i>k</i>, two ships of size 1 × (<i>k</i>-1), ..., <i>k</i> ships of the size of 1 × 1, and the ships, as in a normal naval battle, should not touch
24+
each other and intersect.
25+
26+
## Input format
27+
In a single line of input data, the number <i>n</i> is given — the number of cells of the field (0 ≤ <i>n</i> ≤ 10<sup>18</sup>).
28+
29+
## Output format
30+
Print a single number — such a maximum <i>k</i> that you can arrange the ships as described in the condition.
31+
32+
## Example
33+
| Input | Output |
34+
|:------|:-------|
35+
| 7 | 2 |
36+
37+
## Notes
38+
Explanation for example: for a 1 × 7 field, the answer is 2. You can arrange one ship of size 1 × 2 and two ships of size 1 × 1 as follows:
39+
<div align="center"><img src="./assets/sea-battle.png?raw=true" alt="Ships location" height="88"/></div>

‎Yandex Contest/Training on algorithms 5.0/Lesson 4/B. One-dimensional naval battle/README_RU.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
# B. Одномерный морской бой
2+
3+
<table>
4+
<tr>
5+
<td>Ограничение времени</td>
6+
<td>2 секунды</td>
7+
</tr>
8+
<tr>
9+
<td>Ограничение памяти</td>
10+
<td>256Mb</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+
Поле в игре в одномерный морской бой имеет размеры 1 × <i>n</i>. Ваша задача — найти такое максимальное <i>k</i>, что на поле
23+
можно расставить один корабль размера 1 × <i>k</i>, два корабля размера 1 × (<i>k</i>−1), ..., <i>k</i> кораблей размера 1 × 1,
24+
причем корабли, как и в обычном морском бое, не должны касаться друг друга и пересекаться.
25+
26+
## Формат ввода
27+
В единственной строке входных данных дано число <i>n</i> — количество клеток поля (0 ≤ <i>n</i> ≤ 10<sup>18</sup>).
28+
29+
## Формат вывода
30+
Выведите единственное число — такое максимальное <i>k</i>, что можно расставить корабли, как описано в условии.
31+
32+
## Пример
33+
| Ввод | Вывод |
34+
|:-----|:------|
35+
| 7 | 2 |
36+
37+
## Примечания
38+
Пояснение к примеру: для поля 1 × 7 ответ равен 2. Расставить один корабль размера 1 × 2 и два корабля размера 1 × 1 можно
39+
следующим образом:
40+
<div align="center"><img src="./assets/sea-battle.png?raw=true" alt="Ships location" height="88"/></div>

0 commit comments

Comments
 (0)
0