| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 47 | 30 | 26 | 78.788% |
Hektor lubi opiekować się swoją młodszą siostrą Kornelią - nigdy nie brakuje im pomysłów na zabawy. Dzisiaj grają w zgadywankę.
Do zabawy potrzebne jest N kwadratowych pól, ułożonych jedno za drugim. Na początku Kornelia zamalowuje kilka początkowych pól (na przykład pierwsze 5, pierwsze 2 - oczywiście może zamalować wszystkie pola, albo żadne z nich). Kiedy Kornelia skończy zamalowywać pola, przykrywa każde z nich kawałkiem papieru, tak, że nie widać czy zostało zamalowane.
Wtedy przychodzi kolej na Hektora - jego zadaniem jest dowiedzieć się, ile pól zamalowała Kornelia. Hektor może odkrywać wybrane przez siebie pola w kolejnych rundach zgadywanki. W każdej z nich może odkryć (jednocześnie!) co najwyżej K do tej pory zakrytych pól.
Oblicz minimalną liczbę rund, dla której istnieje sposób wybierania odkrywanych pól dający gwarancję ustalenia liczby zamalowanych kwadratów.
W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). W kolejnych Z liniach znajdują się po dwie, opisane w treści liczby naturalne N i K ( 1 <= N, K <= 1000000 ).
Dla każdego zestawu testowego należy w osobnej lini wypisać opisaną w treści minimalną liczbę rund dającą gwarancję sukcesu.
1 5 2
2
2 rundy wystarczają do ustalenia liczby zamalowanych pól przy następującej strategii odkrywania pól. Hektor w pierwszej rundzie odkrywa pola 2 i 4.
Jednocześnie 1 runda to za mało - niezależnie od tego jakie pola Hektor odkryje w pierwszej rundzie, może się okazać, że w dalszym ciągu nie wie ile pól zamalowała Kornelia. Wybrane przykłady:
Contest > Spot > CoolSpot 2010 2-3번