eolymp
bolt
Try our new interface for solving problems
Məsələlər

Жестокая задача

Жестокая задача

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Штирлиц и Мюллер стреляют по очереди. В очереди n человек, стоящих друг за другом. Каждым выстрелом убивается один из стоящих. Кроме того, если у кого-то из стоящих в очереди убиты все его соседи, то этот человек в ужасе убегает. Проигрывает тот, кто не может ходить. Первым стреляет Штирлиц. Требуется определить, кто выиграет при оптимальной игре обеих сторон, и если победителем будет Штирлиц, то найти все возможные первые ходы, ведущие к его победе.

Giriş verilənləri

Одно число n (2n5000) - количество человек в очереди.

Çıxış verilənləri

Если выигрывает Мюллер, вывести единственное слово Mueller. Иначе в первой строке вывести слово Schtirlitz, а в последующих строках - номера людей в очереди, которых мог бы первым ходом убить Штирлиц для достижения своей победы. Номера следует выводить в порядке возрастания.

Nümunə

Giriş verilənləri #1
3
Çıxış verilənləri #1
Schtirlitz
2
Mənbə ЛКШ-2011 Севастополь 08.08.2011 д.2 1-я лига