Bloki trojkowe c++

Question

Mam problem z zadaniem 

Niech n będzie dodatnią liczbą całkowitą i niech a1, a2, …, an będzie ciągiem nieujemnych liczb całkowitych. Dla pary liczb i, j takich, że 1 ≤ i ≤ j ≤ n, blokiem b(i,j) nazywamy podciąg kolejnych elementów ciągu a z pozycji od i do j, czyli ai, ai+1, …, aj. Długością bloku nazywamy liczbę jego elementów. O bloku, którego suma elementów jest podzielna przez 3 mówimy, że jest blokiem trójkowym.
Przykład:
W ciągu 0,0,2,3,2,1,2 najdłuższym blokiem trójkowym jest b(4,6) = 3,2,1.
W plikach tekstowych bloki1.txt, bloki2.txt i bloki3.txt zapisano ciągi odpowiednio 1000, 30000 i 1000000 nieujemnych liczb całkowitych mniejszych od 10 000. W każdym pliku liczby zapisano w kolejnych wierszach, po jednej liczbie w każdym wierszu.
Dla każdego pliku z danymi wyznacz długość najdłuższego bloku trójkowego w ciągu zapisanym w tym pliku.
Przykład:
Dla danych z pliku z 7 liczbami: 0
0
2
3
2
1
2
długość najdłuższego bloku trójkowego wynosi 3.
Do oceny oddajesz plik(i) o nazwie(ach) ………………………………………………
tu wpisz nazwę/nazwy pliku/plików
zawierający(e) komputerową realizację Twoich obliczeń oraz pliki tekstowe wyniki1.txt, wyniki2.txt, wyniki3.txt, gdzie każdy z nich zawiera liczbę równą długości najdłuższego bloku trójkowego w ciągach zapisanych odpowiednio w plikach bloki1.txt, bloki2.txt i bloki3.txt.

oto część mojego programu,zliczam sume cyfr ,a następnie sprawdzam,czy dana suma przy dzieleniu przez 3 daje resztę 0,niestety,ale to nie działa :( 

 

#include <iostream>
#include<fstream>
using namespace std;



int suma_cyfr(int n)
{

    int s=0;
    while(n>0)
    {
         s=s+n%10;
    n=n/10;
    }

    return s;
}
int main()
{
   int b;
   ifstream we("blok_A.txt");
 
   for(int i=0;i<1000;i++)
   {
       we>>b;

if(suma_cyfr(b)%3==0)cout<<b<<endl;

   }
    return 0;
}

 

Comments

vector mógłbyś wytłumaczyć jak to zrobić za pomocą dziel i zwyciężaj? ,bo do końca nie rozumiem...

---

funkcja solve liczy najdłuższy blok trójkowy na przedziale <lhs, rhs). funkcja helper liczy najdłuższy blok trójkowy na przedziale <lhs, rhs) przechodzący przez mid.
 

#include <bits/stdc++.h>

int32_t helper(std::vector<int32_t> &vec, int32_t lhs, int32_t mid, int32_t rhs) {
    static constexpr int32_t moves[3][2] = {{0, 0}, {1, 2}, {2, 1}};

    int32_t lhsModPref = vec[mid - 1] % 3;
    int32_t rhsModPref = vec[mid] % 3;
    int32_t max        = 0;

    std::vector<int32_t> lhsMod(3, -1), rhsMod(3, -1);

    lhsMod[lhsModPref] = mid - 1;
    for(int32_t i = mid - 2; i >= lhs; --i) {
        lhsModPref         = (lhsModPref + vec[i]) % 3;
        lhsMod[lhsModPref] = i;
    }

    rhsMod[rhsModPref] = mid;
    for(int32_t i = mid + 1; i < rhs; ++i) {
        rhsModPref         = (rhsModPref + vec[i]) % 3;
        rhsMod[rhsModPref] = i;
    }

    for(int32_t i = 0; i < 3; ++i) {
        if(lhsMod[moves[i][0]] != -1 && rhsMod[moves[i][1]] != -1) {
            max = std::max(max, rhsMod[moves[i][1]] - lhsMod[moves[i][0]] + 1);
        }
    }

    return max;
}

int32_t solve(std::vector<int32_t> &vec, int32_t lhs, int32_t rhs) {
    if(rhs - lhs == 1) {
        return vec[lhs] % 3 == 0 ? 1 : 0;
    }

    int32_t mid = (lhs + rhs) / 2;
    int32_t res = std::max(std::max(solve(vec, lhs, mid), solve(vec, mid, rhs)), helper(vec, lhs, mid, rhs));

    return res;
}

int main(void) {
    int32_t n;
    std::cin >> n;

    std::vector<int32_t> vec(n);
    for(auto &v : vec) {
        std::cin >> v;
    }

    std::cout << solve(vec, 0, vec.size()) << std::endl;
    return 0;
}

 

---

dzięki za Twój wysiłek i czas,zapewne to jest dobry program,ale ja nie znam funkcji solve mało z tego rozumiem,nie da się tego zrobić w jakiś prostszy sposób ?

---

Dużo prostrzy algorytm zaproponował Sinoviesta, który w dodatku działa w O(n), a mój w O(n lg n). Możesz spróbować zrozumieć jego algorytm.

 

Mogę Ci jedynie objaśnić jak działa mój algorytm, może pomoże Ci to zrozumieć wcześniej załączony kod przeze mnie.

Najpierw oznaczenia:

Niech A będzie ciągiem (a_lhs, a_(lhs+1), ..., a_(rhs-1)) (cały ciąg)

Niech B będzie ciągiem (a_(lhs), a_(lhs+1), ..., a_(mid-1)) (lewa połowa)

Niech C będzie ciągiem (a_mid, a_{mid+1), ..., a_(rhs-1)) (prawa połowa)

Niech X będzie ciągiem (a_i, a_(i+1), ..., a_(mid-1)) (sufiks ciągu B)

Niech Y będzie ciągiem (a_mid, a_(mid+1), ..., a_(j)) (prefiks ciągu C)

Niech S(K) będzie sumą wszystkich elementów ciągu K.

Funkcja solve(A, lhs, rhs) znajdzie maksymalny blok trójkowy dla ciągu A. Najpierw rekurencyjnie znajdzie maksymalne bloki trójkowe dla ciągów B i C. Ale może istnieć lepsze rozwiązanie dla ciągu A niż to znalezione w ciągach B i C. Mianowicie nie rozpatrzyliśmy ciągów których początek znajduje się w ciągu B i koniec w ciągu C, tym znajduje się funkcja helper(A, lhs, mid, rhs).

Wystarczy dla każdej najmniejszej liczby i takiej że S(X) = k (mod 3) rozważyć największą liczbę j taką że S(Y) = 3-k (mod 3). funkcja helper wyznacza te wartości i zwraca maksymalne j-i+1.

---

dzieki:),wszystko jasne :)