W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Jak zapewne wszyscy pamiętają, Bajtuś i Bituś to dwaj chłopcy, którzy lubią grać w rozmaite gry. Ostatnio Bituś poniósł porażkę, zjadając oznaczony kawałek czekolady i chce się zrewanżować Bajtusiowi. Zaproponował mu nową grę, jej zasady są następujące.
Początkowo na tablicy napisana jest pewna liczba całkowita większa od . Gracze na przemian zastępują liczbę aktualnie napisaną na tablicy jej wybranym dzielnikiem (różnym od niej samej). Gdy któryś z graczy napisze liczbę , gra się kończy. Dla każdego dzielnika liczby , z wyjątkiem , określone są dwie liczby i . Gdy Bajtuś w trakcie gry napisze na tablicy liczbę , dostaje punktów. Z kolei Bituś, za napisanie otrzymuje punktów. Celem gry jest zmaksymalizowanie przewagi nad przeciwnikiem, czyli różnicy między zdobytymi punktami a punktami przeciwnika.
Bituś wybrał już liczbę oraz punktację dla jej dzielników. Za to Bajtuś może wybrać, który z chłopców wykona pierwszy ruch. Chciałby on wobec tego wiedzieć, ile w obydwu przypadkach wyniesie przewaga rozpoczynającego grę, przy założeniu, że obaj chłopcy grają optymalnie.
Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą oznaczającą liczbę przypadków testowych, które są kolejno opisane w dalszej części wejścia. Opis jednego przypadku testowego rozpoczyna się wierszem z czterema liczbami całkowitymi i (, ). Iloczyn jest równy liczbie , która początkowo znajduje się na tablicy, zaś oznacza liczbę dodatnich dzielników liczby .
W dalszych wierszach znajduje się punktacja dla kolejnych (różnych od ) dzielników , w kolejności rosnącej. W -tym z tych wierszy znajdują się dwie liczby całkowite oraz (), które oznaczają liczbę punktów przyznawanych odpowiednio Bajtusiowi i Bitusiowi za napisanie na tablicy liczby , czyli -tego dzielnika .
Suma liczb po wszystkich przypadkach testowych w jednym pliku nie przekracza .
Wypisz wierszy z odpowiedziami dla poszczególnych przypadków testowych. Odpowiedź dla jednego przypadku składa się z dwóch liczb całkowitych i , które oznaczają przewagę rozpoczynającego grę, jeśli jest nim, odpowiednio, Bajtuś i Bituś.
Dla danych wejściowych:
2 7 1 1 2 3 1 2 2 1 3 1 1 3 3
poprawną odpowiedzią jest:
3 1 2 2
Wyjaśnienie: W pierwszym przypadku testowym rozpoczynający grę może napisać jedynie , co od razu kończy grę. W drugim zaś opłaca się napisać i pozwolić przeciwnikowi napisać .
Autor zadania: Tomasz Kociumaka.