Analiz ve Çözüm Yolu

En fazla katılımcı sayısı \(L = (M - 1) \cdot 365 + 1\) ile bulunabilir.

Bu soruyu çözmek için tersten düşünmemiz gerekebilir. K (\(0 ≤ K ≤ L\)) katılımcı için herhangi M tanesinin doğum gününün aynı olmadığı durumları sayalım. Biri işlenen gün sayısı (d), diğeri katılımcı sayısı (c) olmak üzere iki boyutlu dinamik programlama kullanacağız. Değerimiz ise c kişinin d gün içinden kaç farklı doğum günü olacağı durumu \(A_{d, c}\) olacak.

Herhangi bir günü değerlendirirken doğum günü o gün olan kişi sayısı üzerinde ilerleriz (en fazla \(M - 1\) kişi):

\( A_{d, c} = \sum_{k = 0}^{k < \mathbf{M}}{A_{d - 1, c - k} \cdot \binom{c}{k}}\).

Minumum katılımcı sayısını ise şu şekilde bulabiliriz:

\(1 - \frac{A_{365, c}}{365^c} \ge \frac{P}{100}\).

Bu algoritmayı uygulama biçimimize göre zaman limitini aşabilir. Ancak sadece 1010 farklı girdi olduğu için tüm olası çıktıları önceden hesaplayabiliriz.

Analysis and Guide for Solution

Obviously the answer is at most \(L = (M - 1) \cdot 365 + 1\).

Let's compute the number of birthday assignments for K (\(0 ≤ K ≤ L\)) participants such that no \(M\) of them have the same birthday. We will use dynamic programming with two dimensions: the number of year days processed (d) and the number of participants (c). The value is the number of birthday assignments \(A_{d, c}\). While considering a current year day we iterate the number of participants with the current birthday (at most \(M - 1\)):

\(A_{d, c} = \sum_{k = 0}^{k < \mathbf{M}}{A_{d - 1, c - k} \cdot \binom{c}{k}}\).

Finally we are looking for the smallest c such that:

\(1 - \frac{A_{365, c}}{365^c} \ge \frac{P}{100}.\)

Depending on the implementation we may or may not fit into the time limit. However all possible answers could be precalculated since there are only 1010 different inputs.