Zadanie Ciąg [OIG]

Question

Mam takie zadanie Ciąg
Jedyne co udało mi się zrobić to program do generowania tego ciągu w formacie (ilosc_wystapien, liczba)

def f():
    tab = [[] for i in range(100)]
    tab[1].append((1, 1))
    tab[2] = [(2, 2), (2, 3)]
    tab[3] = [(3, 4), (3, 5)]
    wiersz, i = 3, 6
    while wiersz < 10:
        for tup in tab[wiersz]:
            for j in range(tup[0]):
                tab[tup[1]].append((tup[1], i))
                i += 1
        wiersz += 1
    for i in tab:
        print(i)
f()

Nie mam pojęcia jak to rozwiązać

Answer 1

Bardzo przydatnym narzędziem w tego typu zadaniach jest strona OEIS, na której znajdziesz większość odkrytych ciągów liczbowych. Po wpisaniu kilku pierwszych elementów ciągu, który powstaje w tym zadaniu, wychodzi, że jest to ten ciąg: https://oeis.org/A001462. 

Na tej stronie znajdziesz też wzór na n-ty wyraz ciagu: a(n+1) = 1 + a(n+1-a(a(n))), gdzie a(n) to n-ty wyraz ciągu Golomba. 

Najważniejszą obserwacja w tym zadaniu jest to, że ilość wszystkich wyrazów w "grupach" rozmiaru i jest równa i*a(i) np. jest 3*a(3), czyli 6 wyrazów w grupach rozmiaru 3 i są to wyrazy 4, 4, 4, 5, 5, 5. Jeżeli policzysz sobie sumę wszystkich i*a(i) dla i w przedziale [1, x] to wyjdzie że dla x równego około 2*10^7 ta suma jest większa od 1e18. Dodatkowo a(2*10^7) to około 40000.

Z tymi podpowiedziami powinieneś już być w stanie rozwiązać to zadanie

Comments

Niestety dalej nie wiem jak to zrobić :/, mogę iść po kolejnych liczbach tego ciągu i sprawdzać ile będzie następnych "grupy wyrazów"  ale nie będę wiedział co to za liczby w tych grupach np 4 * a(4) to grupa 6 6 6 6 7 7 7 7 8 8 8 8 skąd wiedzieć jakie cyfry są w tych grupach?

---

Możesz sumować wartości a(i) i będziesz wiedział ile różnych liczb jest w ciągu do momentu i. Np dla i = 4, a(1)+a(2)+a(3)+a(4) = 1+2+2+3=8, co się zgadza.

---

Zrobiłem taki program

#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long

int main(){
    ull number, sum_of_val, sum_of_indexes, n;
    vector<int> a(1000000);
    a[1] = 1;

    cin >> number;

    sum_of_indexes = sum_of_val = 0;

    for (n = 1; !(sum_of_indexes <= number && number <= sum_of_indexes + a[n] * n); n++){
        //a(n+1) = 1 + a(n+1-a(a(n)))
        a[n + 1] = 1 + a[n + 1 - a[a[n]]];
        sum_of_indexes += a[n] * n;
        sum_of_val += a[n];
    }
    sum_of_val += a[n]; //suma wartosci od 1 do n, suma indeksow jest od 1 do n-1

    ull position_in_group = 1;

    while (!(sum_of_indexes <= number && number <= sum_of_indexes + n)){
        position_in_group++;
        sum_of_indexes += n;
    }

    cout << sum_of_val - (a[n] - position_in_group) << endl;
    return 0;
}

Mam problem z pamięcią :(, mogę zrobić maksymalnie tablicę o wielkości kilku milionów, jak sprawdzałem ile potrzeba miejsc aby przebic 1e18 to pokazywało około 11 milonów, ten kod przechodzi wszystkie testy oprócz trzech ostatnich bo brakuje mu tablicy :(

EDIT: Dziwna sprawa, jak zmieniłem na 7 milionów wielkość to w 3 ostatnich nie mieszczę się z limitem czasowym

---

Niestety nie wiem jak to można przyspieszyć. Złożoność O(10^7) powinna przejść w większości zadań, ale widzę, że limity są całkiem surowe, bo na 0.1 sekundy. Być może da sie to jakoś zoptymalizować np. wartości powyżej 10^6 mają jakieś specjalne właściwości, albo można je szybciej liczyć itp.

---

Ewentualnie w związku z tym, że a(10e7) to jakieś 30000, być może można po prostu ręcznie wpisać do kodu, dla jakiego najmniejszego x, a(x) = i, gdzie i należy do przedziału [0, 30000]. I potem jakoś szybciej odpowiadać na zapytanie. Nie wiem tylko jaki jest na szkopule limit na rozmiar kodu źródłowego. Jeżeli jakiś duży to być może ten pomysł zadziała

---

Napisałem do OKI (olimpijskie koło informatyczne) bo już mi kiedyś wysłali odpowiedź do jednego zadania, wysyłają mi taki kod:

#include <iostream>
#include <vector>
/*
Liczymy ciag dopoki znane, pamietajc cale przedzial
*/
using namespace std;
const int N = 1000*100;
int Ost[N];
int main(){
    long long int n,znane;
    long long int j,i,k,ktory,wsk;
    bool koniec_petli = false;
    cin >> n;
    if (n==1) {
       cout << "1\n";
       return 0;
    }
    if ( n<=3 ) {
       cout << "2\n";
       return 0;
    }
    if ( n<=5 ) {
       cout << "3\n";
       return 0;
    }
    if ( n<=8 ) {
       cout << "4\n";
       return 0;
    }
    if ( n<=11 ) {
       cout << "5\n";
       return 0;
    }
//ost - ostatni element który wystepuje index razy
    Ost[1] = 1;
    Ost[2] = 3; //3 jest ostatnia ktora wystepuje 2 razy
    //ost[3] = 5
    //ost[4] = 8
    //ost[5] == 11
    k = 2;      //index dla ost
    wsk = 3;    //index dla ost
    znane = 11;
    ktory = 5;
/*
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
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8  8  8  8  9  9  9  9  9  10 10
1 wyraz który występuje 1 raz
2 wyrazy które wyystępują 2 razy (2 2 oraz 3 3)
2 wyrazy które wyystępują 3 razy (4 4 4 oraz 5 5 5)
3 wyrazy które wyystępują 4 razy
*/
    while(znane < n) {
        Ost[wsk] = Ost[wsk-1]+k;
        for(i=Ost[wsk-1]+1; i<=Ost[wsk]; i++){
            if (znane + i*wsk > n) {
			   koniec_petli = true;
    	       break;
            }
            znane += i*wsk;
            ktory += wsk;
        }
        if (koniec_petli == true) {
  	       break;
        }
        wsk++;
        if(wsk > Ost[k]) k++;
    }
    while(znane < n){
        znane += i;
        ktory++;
    }
    cout << ktory << "\n";
    return 0;
}

wklejam do sprawdzarki, nie przechodzi wszystkich testów więc napisałem im to, oni przeczytali i nic nie odpisują nie wiem czy się na mnie obrazili czy co xD, a może ja coś robię źle ? nie wiem, robią takie trudne zadania i testy że później sami ich nie potrafią rozwiązać

---

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

#include <bits/stdc++.h>

using namespace std;

const int N = 30000;
long long Ost[N];

long long int n, znane;
long long int i, k, ktory, wsk;

long long beg, en, mid, pos;

bool koniec_petli;

long long suma(long long a, long long b)
{
    return b*(b+1)/2 - (a-1)*a/2;
}

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

    cin >> n;

    if (n==1) {
       cout << "1\n";
       return 0;
    }
    if ( n<=3 ) {
       cout << "2\n";
       return 0;
    }
    if ( n<=5 ) {
       cout << "3\n";
       return 0;
    }
    if ( n<=8 ) {
       cout << "4\n";
       return 0;
    }
    if ( n<=11 ) {
       cout << "5\n";
       return 0;
    }

    Ost[1] = 1;
    Ost[2] = 3;

    k = 2;
    wsk = 3;
    znane = 11;
    ktory = 5;

    while(znane < n)
    {
        Ost[wsk] = Ost[wsk-1]+k;

        if(znane + suma(Ost[wsk-1]+1, Ost[wsk])*wsk <= n)
        {
            znane += suma(Ost[wsk-1]+1, Ost[wsk])*wsk;
            ktory += (Ost[wsk]-Ost[wsk-1])*wsk;
        }

        else
        {
            beg = Ost[wsk-1]+1, en = Ost[wsk], pos=Ost[wsk-1];

            while(beg <= en)
            {
                mid = (beg+en)/2;

                if(znane + wsk*suma(Ost[wsk-1]+1, mid) <= n)
                {
                    pos = max(pos, mid);
                    beg = mid+1;
                }

                else en = mid-1;
            }

            koniec_petli = true;

            if(pos > Ost[wsk-1])
            {
                znane += suma(Ost[wsk-1]+1, pos)*wsk;
                ktory += (pos-Ost[wsk-1])*wsk;
            }
            
            pos++;
        }

        if (koniec_petli)
           break;

        wsk++;

        if(wsk > Ost[k])
           k++;
    }

    while(znane < n)
    {
        znane += pos;
        ktory++;
    }

    cout << ktory << "\n";
}

Udało mi się tak przerobić kod, aby weszło na 100. Z rozwiązaniem od OKI był taki problem, że w pętli w linii 54 (w oryginalnym kodzie od OKI) pętla mogła się powtórzyć nawet 10^7 razy, a to jest zdecydowanie za wolno. Wystarczyło jednak zamiast pętli dać bin searcha.

Kod nie jest za ładny, ale mam nadzieję, że się w nim połapiesz

---

Whistleroosh, jesteś kozakiem, bardzo bardzo Ci dziękuję !

---

Bez binary-searcha też przechodzi :D

#include <bits/stdc++.h>

using namespace std;

const int N = 30000;
long long Ost[N];

long long int n, znane;
long long int i, k, ktory, wsk;

long long beg, en, mid, pos;

bool koniec_petli;

long long suma(long long a, long long b)
{
    return b*(b+1)/2 - (a-1)*a/2;
}

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

    cin >> n;

    if (n==1) {
       cout << "1\n";
       return 0;
    }
    if ( n<=3 ) {
       cout << "2\n";
       return 0;
    }
    if ( n<=5 ) {
       cout << "3\n";
       return 0;
    }
    if ( n<=8 ) {
       cout << "4\n";
       return 0;
    }
    if ( n<=11 ) {
       cout << "5\n";
       return 0;
    }

    Ost[1] = 1;
    Ost[2] = 3;

    k = 2;
    wsk = 3;
    znane = 11;
    ktory = 5;

    while(znane < n)
    {
        Ost[wsk] = Ost[wsk-1]+k;

        if(znane + suma(Ost[wsk-1]+1, Ost[wsk])*wsk <= n)
        {
            znane += suma(Ost[wsk-1]+1, Ost[wsk])*wsk;
            ktory += (Ost[wsk]-Ost[wsk-1])*wsk;
        }

        else
        {
            for(i=Ost[wsk-1]+1; i<=Ost[wsk]; i++){
            if (znane + i*wsk > n) {
               koniec_petli = true;
               break;
            }
            znane += i*wsk;
            ktory += wsk;
        }
        }

        if (koniec_petli)
           break;

        wsk++;

        if(wsk > Ost[k])
           k++;
    }

    while(znane < n)
    {
        znane += i;
        ktory++;
    }

    cout << ktory << "\n";
}

trzeba było dać ten jeden warunek żeby nie iterowało po mniejszych wyrazach jeśli to nie jest potrzebne

---

Racja. Tak też się da i jest nawet prostsze w implementacji. To zadanie jest w ogóle ciekawe, bo powiedziałbym, że ono jest bardziej na poziomie OI niż OIG. Jeżeli chciałbyś zrobić jakieś fajne i całkiem proste zadania z OI to mogę polecić zadanie Kurierzy z XXI OI (ono ma różne 2 rozwiązania), albo to