SEG - Chia đoạn Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi: duytoannguyenledh Cho một băng số gồm n số nguyên dương a1, a2, ..., an, mỗi số được viết trên một ô. Hãy cắt băng số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau. Dữ liệu vào: + Dòng đầu ghi n (n 1000) + Trong n dòng tiếp theo, dòng thứ i ghi một số nguyên dương ai (1 ai 1000). Dữ liệu ra: + Là số lượng đoạn nhiều nhất chia được. Ví dụ input 8 10 2 6 2 5 2 1 2 output 3 Đoạn 1: 10 Đoạn 2: 2 + 6 + 2 =10 Đoạn 3: 5 + 2 + 1 + 2 = 10 c++

#include <bits/stdc++.h>
using namespace std;
int n, res = 0;
vector<int> a;
int binSearch(int l, int r, int v) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == v) return mid;
        else if (a[mid] > v) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}
bool check(int x, int q, int n) {
    int pos, id = 0;
    for (int i = 1; i <= q; i++) {
        pos = binSearch(id, n - 1, i*x);
        if (pos == -1) return false;
        id = pos;
    }
    return true;
}
int max(int a, int b) {
    if (a >= b) return a;
    return b;
}
int main() {
    int n;
    cin >> n;
    a.reserve(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) a[i] = a[i - 1] + a[i];
    int k = a[n - 1];
    for (int i = 1; i <= sqrt(k); i++) {
        if (k % i == 0)
            if (k / i == i) {
                if (check(k / i, i, n)) res = max(res, i);
            } else {
                if (check(k / i, i, n)) res = max(res, i);
                if (check(k / (k / i), k / i, n)) res = max(res, k / i);
            }
    }
    cout << res;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, a[1111], pre[1111];
int checkAnswer(int value)
{
    int cnt = 1, sum = 0;
    for(int i = 1; i <= n; i++)
    {
        sum += a[i];
        if(sum > value)
        {
            sum -= a[i];
            if(sum != value) return -1;
            sum = a[i];
            cnt++;
        }
    }
    if(sum != 0 && sum != value) return -1;
    return cnt;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++)
    {
        int res = checkAnswer(pre[i]);
        if(checkAnswer(pre[i]) != -1)
        {
            cout << res;
            return 0;
        }
    }
    return 0;
}