Aug 2016
1 / 6
Aug 2016
Sep 2020
tarpauwatratar
Aug '16

http://pl.spoj.com/problems/FR_02_18/10

Brutalna symulacja z fast IO dostaje TLE (choć to chyba oczywiste).

Myśląc intensywnie nad własnościami ciągu arytmetycznego i okręgu rozumianego jak w powyższym zadaniu (oraz ucząc się i dowodząc parę rzeczy po drodze bo tak teoretycznie dzielenie z resztą miałem tylko w II podstawówki) stworzyłem "cudowne" rozwiązanie. Jedno ale - rozwiązanie matematyczne a nie program...

Mój pomysł opiera się na rozwiązywaniu kongruencji. Rozwiązując równania kwadratowe w ciele reszt modulo n, gdzie n oznacza liczbę punktów na okręgu, otrzymuję numery porządkowe kapitanów. Problem polega na tym, że zakodowanie tego + uwzględnienie n złożonych (chińskie twierdzenie o resztach) wydaje mi się co najmniej wyzwaniem. Z tego wnioskuję, że moje rozwiązanie jest delikatnie mówiąc przekombinowane jak na zadanie średnie. Chciałbym się dowiedzieć, czy słusznie wydaje mi się, że nie tędy droga?

  • created

    Aug '16

  • last reply

    Sep '20
  • 5

    replies

  • 702

    views

  • 3

    users

  • 1

    link

mariusz193
Aug '16

nie rozwiązywałem jeszcze tego zadania, ale mam wrażenie do jego rozwiązania (przy podanych zakresach danych wejściowych) całkowicie wystarczą:
1) właściwości ciągu arytmetycznego
2) właściwości reszty z dzielenia

tylko w przypadku bardzo małej liczby zapytań rozwiązywanie kongruencji miałoby sens (czyli krótszy czas)
biorąc pod uwagę zysk czasowy oraz różnicę w złożoności algorytmu to raczej bezsens :slight_smile:

oczywiście zupełnie inaczej byłoby, gdyby n, q były o kilka rzędów większe

tarpauwatratar
Aug '16

Ok. Czyli przekombinowałem. Cóż... pomyślę nad czymś innym. Chociaż jeszcze nie wiem czym :wink:

4 years later
manjaro
Sep '20

Tych zadań nikt nie weryfikuje?
Pół dnia tracę na poszukiwanie błędu a okazuje się że autor wymyślił sobie że wyniki wypisujemy w OSOBNYCH LINIACH a w przykładzie podał że w tej samej linii po spacji…
No litości, tyle osób rozwiązało zadanie i nikt nie przekazało uwag dalej?

tarpauwatratar
Sep '20

Tak w sumie to nawet tego nie zauważyłem. Serio. Rozwiązałem przypadkowo robiąc jak zwykle EOL.

Mamy kapitalizm. Nikt tych zadań bardzo dokładnie nie weryfikuje bo trzeba na obiad dla dziecka zapracować.

Niemniej tym razem postanowiłem zweryfikować bo się jeszcze nie okociłem gdyż jedna z 2^8 płci, za której przedstawiciela się uważam, nie może się okocić. i zrobiłem output jak w przykładzie tj po spacji. Zrobiłem jak zawsze niechlujnie czyli spacja nawet po ostatniej liczbie. AC.

manjaro
Sep '20
1

Rzeczywiście przechodzi w obu przypadkach.
U mnie nie przechodziło bo robiłem w Pythonie i miałem dość nietypowe formatowanie wyniku.

Co nie zmienia faktu, że jednak chyba jest ważne, czy na końcu wyniku jest spacja czy enter.