시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 106 | 44 | 40 | 42.105% |
W Bajtockim Turnieju Programistycznym bierze udział n zawodników. Każdy zawodnik ma pewną siłę i wiadomo, że dwóch różnych zawodników nie posiada takiej samej siły.
Codziennie odbywane są zawody z udziałem zawodników, którzy zakwalifikowali się z dnia poprzedniego. W jednym dniu zawodnicy dzieleni są losowo na pewną liczbę grup po k osób, spośród których odpada zawsze osoba z najmniejszą siłą (pozostałych k - 1 osób zostaje zwycięzcami w danej grupie). Może się zdarzyć, że jedna grupa nie będzie posiadała k osób. W tym wypadku wszystkie osoby z danej grupy przechodzą automatycznie do zawodów następnego dnia. Turniej się kończy, jeśli nie można już podzielić osób na co najmniej jedną grupę o liczbie osób k. W całym turnieju szukamy więc k - 1 zwycięzców.
Zastanawiamy się, ile różnych osób może zwyciężyć w tym turnieju.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą z (1 ≤ z ≤ 106), oznaczającą liczbę zestawów danych. Każdy zestaw danych zawiera po dwie liczby całkowite ni i ki (2 ≤ ki, ni ≤ 109), oznaczające odpowiednio liczbę osób biorących udział w turnieju oraz liczbę osób, na które dzielone są grupy.
Dla każdego zapytania w osobnym wierszu powinna znaleźć się jedna liczba całkowita oznaczająca liczbę różnych osób, które mogą być zwycięzcami w całym turnieju.
3 4 2 3 3 5 3
1 2 2