• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie trójkąt 2 etap XI OIG

VPS Starter Arubacloud
0 głosów
650 wizyt
pytanie zadane 9 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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!
komentarz 10 marca 2023 przez Whistleroosh Maniak (56,980 p.)
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
komentarz 11 marca 2023 przez Whistleroosh Maniak (56,980 p.)
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
komentarz 11 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
ładną strukture, w sensie były podzielone na dwie ładne części?
komentarz 11 marca 2023 przez Whistleroosh Maniak (56,980 p.)
w moim przypadku był to jeden przedział, który stopniowo zwiększał się w prawo. Ale nie mam pewnosci że to zawsze zajdzie
komentarz 11 marca 2023 przez Whistleroosh Maniak (56,980 p.)
#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ł

komentarz 11 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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?
komentarz 11 marca 2023 przez Whistleroosh Maniak (56,980 p.)
pewnie się da, ale to za brzydkie jak na wzorcówke. Musi być tu jakaś zależnosć
komentarz 11 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
też N jest ciekawe, że <= 200000, pewnie jakiś log wchodzi. Ale to nie wiadomo do końca.
1
komentarz 11 marca 2023 przez Whistleroosh Maniak (56,980 p.)
zawsze to może być zmyłka. W tym praniu limity mogły być nawet do 1e6
komentarz 11 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A no faktycznie.

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
2 odpowiedzi 412 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
0 odpowiedzi 510 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 173 wizyt
pytanie zadane 24 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,833 zapytań

141,778 odpowiedzi

320,826 komentarzy

62,164 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...