Trò chơi xoá đoạn
Đề bài
Mô tả
Cho một mảng gồm số nguyên. Hai người chơi lần lượt thực hiện nước đi trên mảng này, người thứ nhất đi trước.
- Người thứ nhất chọn một đoạn con liên tiếp khác rỗng có tổng lẻ rồi xoá nó khỏi mảng.
- Người thứ hai chọn một đoạn con liên tiếp khác rỗng có tổng chẵn rồi xoá nó khỏi mảng.
Sau mỗi lần xoá, hai phần còn lại của mảng được nối liền với nhau thành một mảng mới và trò chơi tiếp tục. Ai không thực hiện được nước đi nào thì thua.
Hãy xác định người thắng cuộc nếu cả hai cùng chơi tối ưu.
Dữ liệu vào
- Dòng đầu chứa số nguyên : độ dài của mảng.
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
In ra một dòng duy nhất: First nếu người thứ nhất thắng, ngược lại in ra Second.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 3 2 3 |
First | Tổng cả mảng bằng là số lẻ nên người thứ nhất xoá toàn bộ mảng ngay ở nước đi đầu tiên, người thứ hai không còn gì để xoá. |
| 2 2 2 |
Second | Mọi đoạn con đều có tổng chẵn nên người thứ nhất không đi được nước nào và thua ngay lập tức. |
| 4 1 1 2 2 |
First | Tổng cả mảng bằng là số chẵn, nhưng người thứ nhất vẫn thắng: xoá đoạn gồm phần tử đầu tiên, phần còn lại 1 2 2 có tổng lẻ nên dù người thứ hai xoá đoạn nào thì tổng phần còn lại vẫn lẻ và người thứ nhất xoá nốt. |
Bình luận