Skip to content
The Chat Archive
o1-mini-2024-09-12· OpenAI WildChat-4.8M (AI2)

Cows to the stalls Input file: stdin Output file: stdout Time limit: 1 sec Memory limit:…

  1. User

    Cows to the stalls Input file: stdin

    Output file: stdout

    Time limit: 1 sec

    Memory limit: 256 mb

    On the straight line there are stalls in which you have to arrange the cows so that the minimum distance between the cows is as large as possible.

    Input The first line contains N (2<N≤105) – the number of stalls and K (1<K<N) – the number of cows. The second line contains N natural numbers in ascending order – the coordinates of the stalls (the coordinates do not exceed 109 ).

    Output One number – the largest possible allowable distance.

    Examples Input 1:

    copy

    6 3 2 5 7 11 15 20

    Output 1:

    copy

    9

    Input 2:

    copy

    5 3 1 2 3 100 1000

    Output 2:

    copy

    99 solve in c++. do not use comments. use short naming. use bits/std...

  2. Assistant
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int N,K;
        cin>>N>>K;
        vector<int>A(N);
        for(auto &x:A) cin>>x;
        auto possible = [&](int d)->bool{
            int cnt=1, last=A[0];
            for(int i=1;i<N;i++) if(A[i]-last>=d){cnt++; last=A[i]; if(cnt>=K) return true;}
            return cnt>=K;
        };
        int l=0, r=A[N-1]-A[0], res=0;
        while(l<=r){
            int m = l + (r-l)/2;
            if(possible(m)){res=m; l=m+1;}
            else r=m-1;
        }
        cout<<res;
    }