25 / 14 / 2
Регистрация: 28.06.2020
Сообщений: 50
1

Коровы в стойла

23.07.2020, 10:58. Показов 48657. Ответов 19

Author24 — интернет-сервис помощи студентам
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.

Входные данные

В первой строке вводятся числа N (2<N<10001) — количество стойл и K (1<K<N ) — количество коров. Во второй строке задаются N натуральных чисел в порядке возрастания — координаты стойл (координаты не превосходят 109)

Выходные данные

Выведите одно число — наибольшее возможное допустимое расстояние.

Примеры
Ввод
Вывод
6 3
2 5 7 11 15 20
9
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n, k = map(int, input().split())
coords = list(map(int, input().split()))
def check(x):
    cows = 1
    lastcow = coords[0]
    for i in coords:
        if i - lastcow >= x:
            cows += 1
            lastcow = i
    return cows >= k
def solve():
    left = 0
    right = coords[-1] - coords[0] + 1
    m = (left + right) // 2
    if check(m):
        left = m
    else:
        right = m
    return left
print(solve())
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.07.2020, 10:58
Ответы с готовыми решениями:

Коровы в стойла
Коровы в стойла На прямой расположены стойла, в которые необходимо расставить коров так, чтобы...

Коровы в стойла
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное...

Коровы — в стойла
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное...

Коровы
По данному числу n закончите фразу «На лугу пасется...» одним из возможных продолжений: «n коров»,...

Быки и коровы
Доброго времени суток. Не могу реализовать человеческий поиск коров в Delphi. Имеется массив цифр...

19
34 / 25 / 8
Регистрация: 16.11.2019
Сообщений: 179
23.07.2020, 11:17 2
Если ты списываешь решение, то списывай его правильно...
C++
1
sort(coords.begin(), coords.end());
- эту строчку ты не учел
0
4236 / 2933 / 687
Регистрация: 08.06.2007
Сообщений: 9,814
Записей в блоге: 4
23.07.2020, 11:22 3
Я так понял, что вы хотели строки 14-18 выполнять до тех пор пока left и right не совпадут.
0
25 / 14 / 2
Регистрация: 28.06.2020
Сообщений: 50
23.07.2020, 11:24  [ТС] 4
А не знаете как переписать эту строчку на питон?
0
Status 418
Эксперт Python
4577 / 2344 / 602
Регистрация: 26.11.2017
Сообщений: 5,265
Записей в блоге: 3
23.07.2020, 12:40 5
Лучший ответ Сообщение было отмечено Rorik как решение

Решение

бинпоиск по ответу
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n, k = map(int, input().split())
*a, = map(int, input().split())
a.sort()
left = 0
right = a[-1] - a[0] + 1
while left < right:
    mid = (left + right)//2
    cows = 1
    last = a[0]
    for cur in a[1:]:
        if cur - last > mid:
            cows += 1
            last = cur
    if cows >= k:
        left = mid+1
    else:
        right = mid
print(left)
5
1 / 1 / 0
Регистрация: 12.07.2020
Сообщений: 42
23.07.2020, 13:59 6
eaa, ваш код работает!!! Спасибо!!!
0
18 / 15 / 2
Регистрация: 15.05.2021
Сообщений: 57
30.07.2021, 18:02 7
а есть на С++?

Добавлено через 46 секунд
даже темы такой нет для с++!
0
Am I evil? Yes, I am!
Эксперт PythonЭксперт Java
17537 / 10296 / 2816
Регистрация: 21.10.2017
Сообщений: 22,347
30.07.2021, 18:34 8
Цитата Сообщение от irthgr Посмотреть сообщение
даже темы такой нет для с++!
Кликните здесь для просмотра всего текста
БЕДА!!!
0
18 / 15 / 2
Регистрация: 15.05.2021
Сообщений: 57
30.07.2021, 18:46 9
Цитата Сообщение от iSmokeJC Посмотреть сообщение
БЕДА!!!
Цитата Сообщение от iSmokeJC Посмотреть сообщение
согласен!!! сегодня последний день!!
0
Arsegg
30.07.2021, 18:47
  #10

Не по теме:

Цитата Сообщение от irthgr Посмотреть сообщение
согласен!!! сегодня последний день!!
Кликните здесь для просмотра всего текста
ААА!!!11!одинодин!!

0
Am I evil? Yes, I am!
Эксперт PythonЭксперт Java
17537 / 10296 / 2816
Регистрация: 21.10.2017
Сообщений: 22,347
30.07.2021, 18:49 11
Цитата Сообщение от irthgr Посмотреть сообщение
сегодня последний день!!
... а мысль, вместо безуспешных поисков и тупого ожидания ответа на форуме написать программу самому, так и не появилась...
0
18 / 15 / 2
Регистрация: 15.05.2021
Сообщений: 57
30.07.2021, 19:09 12
Цитата Сообщение от iSmokeJC Посмотреть сообщение
написать программу самому
я пишу и паралельно ищу
0
Am I evil? Yes, I am!
Эксперт PythonЭксперт Java
17537 / 10296 / 2816
Регистрация: 21.10.2017
Сообщений: 22,347
30.07.2021, 19:16 13
irthgr, а зачем искать, если сам пишешь?
0
Just Do It!
3837 / 2283 / 636
Регистрация: 23.09.2014
Сообщений: 7,051
Записей в блоге: 2
30.07.2021, 19:23 14
не переводится:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{   size_t n, k;
    std::cin >> n >> k; std::vector<size_t> a(n);
    for(auto& e : a) std::cin >> e;
 
    std::sort(a.begin(), a.end());
 
    size_t left  = 0;
    size_t right = a.back() - a[0] + 1;
 
    while(left < right)
    {
        size_t mid  = (left + right)/2;
        size_t cows = 1;
        size_t last = a[0];
 
        for(size_t cur = 1; cur < n; ++cur)
        {
            if(cur - last > mid)
            {   cows +=  1;
                last = cur;
            }
        }
 
        if(cows >= k) left  = mid+1;
        else          right = mid;
    }
 
    std::cout << left;
}
тест не проходит.

есть тёмные места:
mid = (left + right)//2
for cur in a[1:]:
0
18 / 15 / 2
Регистрация: 15.05.2021
Сообщений: 57
30.07.2021, 19:31 15
Цитата Сообщение от iSmokeJC Посмотреть сообщение
а зачем искать, если сам пишешь?
не успеваю

Добавлено через 2 минуты
Цитата Сообщение от XLAT Посмотреть сообщение
mid = (left + right)//2
это можнолегко исправить, просто убрав один слеш, а со вторым не знаю!
А так спасибо)
я подумаю как исправить второе

Добавлено через 5 минут
Цитата Сообщение от XLAT Посмотреть сообщение
for cur in a[1:]:
в питоне, это будет как все элементы массива от элемента с индексом 1 до конца самого массива
только мне не известно, как на с++ сделать
1
3 / 2 / 1
Регистрация: 30.03.2020
Сообщений: 10
30.07.2021, 19:44 16
XLAT,
Цитата Сообщение от XLAT Посмотреть сообщение
for cur in a[1:]:
используй тип auto вместо простого цикла
и вот эти ваши переводы мало к чему приведут при незнании языка, не надо таким заниматься)
1
Just Do It!
3837 / 2283 / 636
Регистрация: 23.09.2014
Сообщений: 7,051
Записей в блоге: 2
30.07.2021, 20:02 17
ShadowAT, да, я слишком заглупил.
пошёл курнул и понял где прокол...
вот, вроде, то:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{   size_t n, k;
    std::cin >> n >> k; std::vector<size_t> a(n);
    for(auto& e : a) std::cin >> e;
 
    std::sort(a.begin(), a.end());
 
    size_t left  = 0;
    size_t right = a.back() - a[0] + 1;
 
    while(left < right)
    {
        size_t mid  = (left + right)/2;
        size_t cows = 1;
        size_t last = a[0];
 
        for(size_t i = 1; i < n; ++i)
        {
            auto cur = a[i];
            if(cur - last > mid)
            {   cows +=  1;
                last = cur;
            }
        }
 
        if(cows >= k) left  = mid+1;
        else          right = mid;
    }
 
    std::cout << left;
}
тест из шапки проходит!
0
0 / 0 / 0
Регистрация: 14.10.2022
Сообщений: 3
14.10.2022, 22:34 18
СКИНЬТЕ КОД ПОЖАЛУЙСТА!!! на с++
0
Am I evil? Yes, I am!
Эксперт PythonЭксперт Java
17537 / 10296 / 2816
Регистрация: 21.10.2017
Сообщений: 22,347
14.10.2022, 23:21 19
100001, А ЭТАЖОМ ВЫШЕ ЧТО?
0
0 / 0 / 0
Регистрация: 22.10.2023
Сообщений: 1
22.10.2023, 19:12 20
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, k;
cin >> n >> k;
vector <long long> v(n);
for (auto & e : v) cin >> e;
sort(v.begin(), v.end());
long long l = 0;
long long r = v.back() - v[0] + 1;
while(l < r) {
long long m = (l + r) / 2, cows = 1, last = v[0];
for(size_t i = 1; i < n; i++) {
auto cur = v[i];
if (cur - last > m)
{ cows += 1;
last = cur;
}
}
if (cows >= k) {
l = m + 1;
} else {
r = m;
}
}
cout << l;
return 0;
}

Поправил код на оформление.
0
22.10.2023, 19:12
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.10.2023, 19:12
Помогаю со студенческими работами здесь

Быки и Коровы
1. «Быки и коровы». Программа формирует строку из четырех цифр (каждая цифра может иметь значение...

Быки и коровы
Перерыла весь интернет. есть алгоритмы на всех языках, кроме php/ я их не знаю. вот наваяла...не...

Быки и коровы
Помогите пожалуйста с алгоритмом к игре быки и коровы. В нете много что есть но не совсем то что...

Быки и коровы.
Доброе время суток! Можете помочь с реализацией игры &quot;Быки и коровы&quot;, много тем просмотрел, там...

Быки и Коровы
Здравствуйте! Ниже представлены мои попытки (может быть жалкие :D) написать программку Быки и...

Быки и коровы
Нужно реализовать классический вариант игры &quot;Быки и коровы&quot;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru