Zadanie trójkąt 2 etap XI OIG

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/B_g59y5Mjtj4o5HUUC0pzShh/site/?key=statement

Napisałem bruta w O(N^2), na 20pkt, sprawdzam każde możliwe 2 przedzielenia. Nie wiem jak podejść do tego lepiej. Myślałem o jakiś binary searchach i rozważaniu wszystkich przypadków bo długościach boków, w sesnie; najmniejszy - średni - największy, najmniejszy - największy - średni, średni - najmniejszy - największy........ Ale nie wiem, czy to ma jakiś sens i czy da się to tak ugryźć.

Z góry dziękuję za pomoc i poświęcony czas!

Comments

Nie widzę jak to jakoś sprytnie zrobić. Możesz sprawdzić brutem dla każdego prefiksu (zakładamy że cały prefiks będzie pierwszym bokiem) gdzie jest podział na drugi i trzeci blok. Może się okaże że to 2 rozłączne przedziały albo coś takiego

---

Sprawdziłem i we wszystkich przypadkach które sprawdzałem przedzialy miały ładną strukturę, ale nie mam dowodu na to, że zawsze tak będzie

---

ładną strukture, w sensie były podzielone na dwie ładne części?

---

w moim przypadku był to jeden przedział, który stopniowo zwiększał się w prawo. Ale nie mam pewnosci że to zawsze zajdzie

---

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

const l INF = 1000000000 + 9;
const ll MOD = 123456789;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

long long suma = 0;
int constexpr n = 100;
int arr[n];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    srand(time(0));

    REP(n, i)
    {
        arr[i] = rand() % 100;
        // arr[i] = i + 1;
        suma += arr[i];
        cout << arr[i] << " ";
    }
    cout << "\n";

    ll a = 0, b = 0, c = 0;

    REP(n - 2, i)
    {
        a += arr[i];
        cout << i << ": ";

        b = 0;
        c = suma - a;

        FOR(i + 1, n - 1, j)
        {
            b += arr[j];
            c -= arr[j];

            auto maks = max({a, b, c});

            if (maks < suma - maks)
                cout << j << " "; //" (" << a << " " << b << " " << c << ") ";
        }
        cout << "\n";
    }
}

tu jest kod który to testował

---

Ja mam trochę pomysł żeby wypiłować to zadanie z binary searchem, ale nie wiem, czy da się wszystkie przypadki tak rozpatrzeć. Kod pewnie będzie miał z 300 linii, ale trudno, jak się da to nie ma problemu. Rozpatrujemy po kolei wszystkie możliwe przypadki.

1* trójkąt równoboczny, ten przypadek jest stosunkowo prosty, przesuwamy pierwszy bok, w sensie pierwsze cięcie, i z binary searchem i sumami prefiksowymi szukamy takich, żeby były równe.

2 * w kolejności od lewej do prawej. najmniejszy,średni,największy. Znowu przesuwamy lewy wskaźnik i zakładamy, że jest to pierwszy bok. I szukamy binary searchem, żeby nie było boku większego od niego, i żeby suma się zgadzała, i tak wszystkie możliwe przypadku, najmiejszy,największy,średni, średni,najmniejszy,największy.....

Myślisz, że ma to sens?

---

pewnie się da, ale to za brzydkie jak na wzorcówke. Musi być tu jakaś zależnosć

---

też N jest ciekawe, że <= 200000, pewnie jakiś log wchodzi. Ale to nie wiadomo do końca.

---

zawsze to może być zmyłka. W tym praniu limity mogły być nawet do 1e6

---

A no faktycznie.