1 2 3 4 5 6 7 8 91011121314151617181920212223242526

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    int inp[n + 1];
    inp[0] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &inp[i]);
    for (int i = 2; i <= n; i++)
        inp[i] += inp[i - 1];

    int q, k = 0;
    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%d", &k);
        printf("%d\n", (int)(lower_bound(inp, inp + n + 1, k) - inp));
    }

    return 0;
}

 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);
    sort(inp, inp + n);

    int m;
    scanf("%d", &m);
    // 3 6 8 10 11
    for (int i = 0; i < m; i++) {
        int num;
        scanf("%d", &num);

        auto it = upper_bound(inp, inp + n, num);
        printf("%d\n", (int)(it - inp));
    }

    return 0;
}

 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343536

#include <cmath>
#include <cstdio>

int n, k;
bool check(double mid, double inp[])
{
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += (int)(inp[i] / mid);
    }

    return cnt >= k;
}

int main()
{
    scanf("%d %d", &n, &k);

    double inp[n];
    for (int i = 0; i < n; i++)
        scanf("%lf", &inp[i]);

    double l = 0, r = 100000001;
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;

        if (check(mid, inp))
            l = mid;
        else
            r = mid;
    }

    printf("%.2f\n", (floor)(l * 100) / 100);

    return 0;
}

 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

#include <bits/stdc++.h>

using namespace std;

#define EPS 1e-10

int n, len;
bool check(vector<int> &inp, double mid)
{
    if (inp[0] - mid > -EPS)
        return false;
    double farthest = inp[0] + mid;
    for (int i = 1; i < (int)inp.size(); i++) {
        if (farthest - (inp[i] - mid) >= -EPS)
            farthest = inp[i] + mid;
        else
            return false;
    }

    if (farthest - len >= -EPS)
        return true;
    return false;
}

int main()
{
    scanf("%d %d", &n, &len);

    vector<int> inp;
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);

        inp.push_back(num);
    }

    sort(inp.begin(), inp.end());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));

    double l = 0, r = len;
    for (int i = 0; i < 200; i++) {
        double mid = (l + r) / 2;

        if (check(inp, mid))
            r = mid;
        else
            l = mid;
    }

    printf("%.15f\n", l);

    return 0;
}

 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566

#include <bits/stdc++.h>

// For every query, binary search for the upper-left corner of the square
// And then binary search for the lower-left corner "on the diagnal"

using namespace std;

int n, m;
int inp[555][555];
int low, high;

int search(int row, int col)
{
    // printf("row %d col %d\n", row, col);
    int l = -1, r = min(n - row, m - col);
    while(r - l > 1) {
        int mid = l + (r - l) / 2;
        // printf("l = %d, mid = %d, r = %d\n", l, mid, r);
        
        if(inp[row + mid][col + mid] <= high)
            l = mid;
        else
            r = mid;
    }
    // printf("l = %d\n", l);
    
    return l;
}

void solve()
{
    int ret = 0;
    for(int i = 0; i < n; i++) {
        int l = lower_bound(inp[i], inp[i] + m, low) - inp[i];
        if(l == m)
            continue;
        int r = search(i, l);
        if(r == -1)
            continue;
        // printf("i = %d l = %d r = %d\n", i, l, r);
        
        ret = max(ret, r + 1);
    }
    
    printf("%d\n", ret);
}

int main()
{
    while(scanf("%d %d", &n, &m) == 2 && (n || m)) {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) 
                scanf("%d", &inp[i][j]);
        
        int q;
        scanf("%d", &q);
        for(int i = 0; i < q; i++) {
            scanf("%d %d", &low, &high);
            
            solve();
        }
        printf("-\n");
    }
    
    return 0;
}

  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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101102103104105106107108109110111112

import java.io.*;
import java.util.*;

public class C {
	public static boolean check(int[] inp, long mid, int k) {
		int[] cur = Arrays.copyOf(inp, inp.length);

		int last = inp.length - 1;
		while (last >= 0 && cur[last] == 0)
			last--;

		for (int i = 0; i < k; i++) {
			long t = mid - last - 1;
			while (t > 0 && last >= 0) {
				if (t - cur[last] >= 0) { // move box
					t -= cur[last];
					cur[last] = 0;

					while (last >= 0 && cur[last] == 0)
						last--;
				} else {
					cur[last] -= t;
					t = 0;
				}
				if (!(t > 0 && last >= 0))
					break;
			}
		}

		for (int i = last; i >= 0; i--)
			if (cur[i] != 0)
				return false;
		return true;
	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));

		int n = sc.nextInt(), k = sc.nextInt();

		int[] inp = new int[n];
		for (int i = 0; i < n; i++)
			inp[i] = sc.nextInt();

		long l = 0, r = (long) 1e18;
		while (r - l > 1) {
			long mid = (l + r) / 2;

			if (check(inp, mid, k) == true)
				r = mid;
			else
				l = mid;
		}

		out.println(r);

		out.close();
	}

	// PrintWriter for faster output
	public static PrintWriter out;

	// MyScanner class for faster input
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		boolean hasNext() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					return false;
				}
			}
			return true;
		}

		String next() {
			if (hasNext())
				return st.nextToken();
			return null;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}