Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Сонирхолтой тоглоом
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Хоёр сайн найз Серёжа, Гена нар тоглоом тоглож байв.
Эхлээд ширээн дээр $n$ ширхэг чулуу байв. Ѳѳрийн ээлжинд нэг хэсгийг сонгоод дурын байдлаар $a_1>a_2>...>a_k>0$ ширхэг чулуутай хэсгүүдэд хуваана. Уг хэсгүүд нь $a_1-a_2=a_2-a_3=...=a_{k-1}-a_k=1$ нѳхцлийг хангах ёстой. Мэдээж уг хуваах хэсгүүдийн тоо $k$ нь хоёроос багагүй байна.
Найзууд ээлжлэн нүүнэ. Үйлдэл хийж чадахгүй болсон тоглогч хожигдно. Серёжа хамгийн эхний үйлдлийг хийнэ. Хоёр тоглогч хамгийн зѳв тактикаар тоглоход хэн нь хожих вэ?
Оролт
Нэг мѳрѳнд бүхэл тоо $n$ ($1≤n≤10^5$) ѳгѳгднѳ.
Гаралт
Хэрвээ Серёжа хожих бол түүний хожихдоо хийх эхний үйлдэлдээ байж болох хамгийн бага хуваалтын тоо болох $k$ бүхэл тоог хэвлэ.
Хэрвээ Гена хожих бол $-1$ гэж хэвлэ.
Орчуулсан: Sugardorj
Жишээ тэстүүд
Оролт
3
Гаралт
2
Оролт
6
Гаралт
-1
Оролт
100
Гаралт
8