#C11228. Bacteria Colony Sustainability

    ID: 40521 Type: Default 1000ms 256MiB

Bacteria Colony Sustainability

Bacteria Colony Sustainability

You are given an initial population \(S\) of bacteria and a survival factor \(k\). In each generation, the bacteria reproduce in such a way that for every \(k\) bacteria, only \(k-1\) survive long enough to contribute to the next generation. Your task is to determine if the colony can sustain itself indefinitely.

Formally, define a function \(f(S, k)\) that returns "Yes" if the colony can survive forever and "No" otherwise. A critical observation is that if \(S \bmod (k-1) = 0\), then the colony will eventually dwindle to zero. Additionally, for some small populations or when \(k \leq 1\), the behavior is defined as follows:

  • If \(k \leq 1\) then the colony survives if and only if \(S > 1\).
  • If \(S 1\), the colony is considered sustainable.

Implement the following two functions:

  1. can_sustain_forever(S, k): Determines the sustainability for a single query.
  2. process_bacteria_queries(queries): Processes multiple queries. Each query is a pair \((S, k)\). Return the corresponding list of "Yes" or "No" answers.

All formulas are provided in \(\LaTeX\) format.

inputFormat

The input is read from standard input. The first line contains an integer \(N\), the number of queries. Each of the next \(N\) lines contains two space-separated integers \(S\) and \(k\): the initial population and the survival factor, respectively.

outputFormat

For each query, output "Yes" if the colony can sustain itself indefinitely, or "No" otherwise. Each answer should be printed on a new line.

## sample
1
5 3
Yes

</p>