Ale jak już znajdę najlepsze drzewo, to niedźwiedź mnie nie zje?

+1

+1

Potwierdzam.

+1

Wrzucam paczkę od siebie:

https://tinyurl.com/2fcpre6

ktoś potwierdzi?

Potwierdzam

Potwierdzam

Potwierdzam

Taki tam losowy maxtest:
www.mimuw.edu.pl/~ms337666/PA/polmax.in
www.mimuw.edu.pl/~ms337666/PA/polmax.out

W treści znajduje się informacja "Ze względu na specyfikę zadania, jurorzy podjęli decyzję, że w przypadku tego zadania na forum nie można dzielić się testami. W dziale Pliki można znaleźć za to paczkę z kilkoma testami przygotowanymi przez jurorów.".

Jeśli ktoś lubi pisać "potwierdzam testy" (jak zawsze na forum w poprzednich latach), to można to tu zrobić. Nie można jednak wrzucać swoich testów.

to ja piąty :) dzień dobry wszystkim

Rok temu podczas właściwej rundy wyszedł na jaw problem techniczny: w pewnych przypadkach wysyłanie wiadomości o rozmiarze powyżej 64 KB wprowadzało gigantyczne opóźnienia na sieci. Nie mamy za bardzo wpływu na ten problem i możliwe, że wciąż nie został naprawiony... W każdym razie w przyszłości polecam spróbować paczkowania wiadomości na nieco mniejsze.

Zgaduję, że wzorem poprzednich lat będzie dostępna możliwość wysyłania rozproszonych uruchomień próbnych. Będzie to doskonała okazja do sprawdzenia tej hipotezy. :)

Cześć!

Czy ktoś dobry mógłby zajrzeć i powiedzieć mi, dlaczego ten kod do Działki 2 działa wolno (tzn. puszczając na teście wielkości 7500*7500 na swoim komputerze na 1 węźle, dostaję czas rzędu 1,5 s, a na 100 rzędu 400 ms, co trochę nie odpowiada oczekiwaniu, że to będzie odwrotnie proporcjonalne do liczby węzłów + mam TLE na większości testów w systemie)?

(Wklejam z pastebina, bo nie umiem za bardzo into github, a nie chcę też przeklejać bezpośrednio tu, nie bijcie).

https://pastebin.com/JQphpPZc

EDIT: Za późno zauważyłem, że nazwa tematu jest słaba, to za to też sorki.

EDIT2: Z góry dzięki!

Minimalnie jeszcze upraszcza kod obserwacja, że skoro coś liczymy dla każdego n/d, to równie dobrze możemy liczyć dla każdego dzielnika d, bo jest odpowiedniość: {wszystkie liczby postaci n/d dla d będącego dzielnikiem n} = {wszystkie dzielniki liczby n}. Moje rozwiązanie poniżej:

#include <cstdio>
#include <vector>

std::vector<int> divisors(int n)
// O(sqrt(n)))
{
..std::vector<int> returned_divisors;

..int i = 1;
..while (i * i < n)
..{
....if (n % i == 0)
....{
.... returned_divisors.push_back(i);
.... returned_divisors.push_back(n/i);
....}
....i++;
..}
..if (i * i == n)
....returned_divisors.push_back(i);
..return returned_divisors;
}

int n{};

int getNumberOfSolutions(int k)
// a * b == k: a >= 2, b >= 3
{
..if (k <= 2)
....return 0;
..if (k % 2 == 0)
....return divisors(k).size() - 3; // subtract: a == 1; b == 1; b == 2
..else
....return divisors(k).size() - 2; // subtract: a == 1; b == 1;
}

int main ()
{
..scanf("%d", &n);

..int sum{};
..for (int d: divisors(n))
..{
....sum += getNumberOfSolutions(d - 1);
..}
..printf("%d\n", sum);
}