E. Дирихлэй юу хийчихэв ээ?

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ хайрцагт $n+1$-ээс цөөнгүй зүйл хийхэд дор хаяж хоёр ширхэг зүйл агуулах хайрцаг олдно гэсэн Дирихлэйн зарчмыг бүгд мэдэх билээ.

Энэ зарчмыг сонссон боловч логик сэтгэлгээний техникийг нь сайн эзэмшээгүй $8$ настай Стас, Маша нар нэгэн тоглоомыг нээжээ. Тэнд $a$ ялгаатай хайрцаг ба $b$ ялгаатай эдлэл байгаа бөгөөд тоглогчид өөрийн ээлжинд шинэ хайрцаг юмуу шинэ эдлэл нэмнэ. Хэрвээ тухайн тоглогч үйлдэл хийсний дараа $b$ эдлэлийг $a$ хайрцагт хийх боломжийн тоо өгсөн тоо $n$-ээс багагүй болвол тэр тоглогч хожигдно. Хайрцаг хоосон үлдэж болно.

Стас эхэлсэн бол зөв тогловол хэн нь хожих вэ?

Оролт

Оролт зөвхөн нэг мөрөнд анх байсан хайрцаг, эдлэл болон боломжийн тооны хязгаарлалтыг илэрхийлэх тоо болох $a$, $b$, $n$ ($1 ≤ a ≤ 10000$, $1 ≤ b ≤ 30$, $2 ≤ n ≤ 10^9$) гурван бүхэл тоо байрлана. Анхны байрлуулах боломжийн тоо заавал $n$-ээс эрс бага байх ёстой.

Гаралт

Маша хожих бол $Stas$ гэж гарга. Стас хожих бол $Masha$ гэж гарга. Тэнцэхээр бол $Missing$ гэж гарга.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
2 2 10
Гаралт
Masha
Оролт
5 5 16808
Гаралт
Masha
Оролт
3 1 4
Гаралт
Stas
Оролт
1 4 10
Гаралт
Missing

Тэмдэглэл

In the second example the initial number of ways is equal to $3125$.

  • If Stas increases the number of boxes, he will lose, as Masha may increase the number of boxes once more during her turn. After that any Stas's move will lead to defeat.
  • But if Stas increases the number of items, then any Masha's move will be losing.
Сэтгэгдлүүдийг ачааллаж байна...