Khởi Nghiệp Nơi Đáy Tầng

Xem PDF

Điểm: 1 Thời gian: 1.0s Bộ nhớ: 256M Input: daovang.INP Output: daovang.OUT
  • Thuở thiếu thời, Pitomon chỉ là một kẻ tay trắng mang trong mình tham vọng đổi đời. Anh quyết định dấn thân vào khu mỏ khoáng sản tinh thể nguy hiểm bậc nhất vũ trụ để tìm kiếm vận may. Tại đây, Pitomon đụng độ với tập đoàn Vingrap - một thế lực khai thác sừng sỏ. Khu mỏ gồm \(N\) khối quặng tinh thể, khối thứ \(i\) có khối lượng là \(A_i\).
  • Để sinh tồn và tranh giành tài nguyên, Pitomon và Vingrap phải tham gia vào một trò chơi sinh tử: Hai bên luân phiên nhau tiến hành khai thác (Pitomon luôn là người đi trước do nhanh chân hơn).
  • Trong mỗi lượt, người chơi được quyền chọn đúng một khối quặng chưa bị khai thác hết và lấy đi một lượng tinh thể bằng \(K\). Để bảo đảm thiết bị không bị quá tải bởi năng lượng tinh thể, lượng \(K\) bắt buộc phải là một số lũy thừa của 2 (\(K \in \{1, 2, 4, 8, 16, 32, \dots\}\)) và không được vượt quá khối lượng còn lại của khối quặng đó.
  • Đến lượt của ai mà không thể thực hiện việc khai thác (do tất cả các khối quặng đều đã cạn kiệt, tức là bằng 0), kẻ đó sẽ bị phá sản và thua cuộc. Giả sử cả Pitomon và Vingrap đều vô cùng thông minh và luôn có chiến lược tối ưu nhất trong mọi bước đi. Bạn hãy xác định xem ai sẽ là người giành chiến thắng và ôm trọn hũ vàng nhé!

Input

  • Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)) mô tả số lượng khối quặng.
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^{18}\)) biểu diễn khối lượng của từng khối quặng.

Output

  • Một dòng duy nhất in ra Pitomon nếu anh chàng giành chiến thắng, ngược lại in ra Vingrap.

Scoring

  • Subtask 1: Có 40% số điểm với \(N \le 10\)\(A_i \le 100\).
  • Subtask 2: Có 60% số điểm với \(N \le 10^5\)\(A_i \le 10^{18}\).

Sample Input 1

2
3 4

Sample Output 1

Pitomon

Sample Input 2

3
4 4 3

Sample Output 2

Vingrap

Giải thích

- Ở ví dụ thứ nhất, Pitomon đi trước và lấy đi 1 đơn vị tinh thể ở khối quặng thứ hai (lúc này các khối quặng còn lại là 3 và 3). Dù Vingrap có đi bước nào tiếp theo trên một khối quặng, Pitomon chỉ cần sao chép y hệt bước đi đó ở khối quặng còn lại. Cuối cùng, Vingrap sẽ là người không còn bước đi hợp lệ.
- Ở ví dụ thứ hai, cả hai đều chơi tối ưu nhưng thế trận ban đầu lại là một thế thua cho người đi trước. Dù Pitomon có cố gắng đi nước đi nào, Vingrap cũng luôn có cách đáp trả hoàn hảo để dồn Pitomon vào đường cùng.

Bình luận

Gần nhất
Tải bình luận...

Không có bình luận nào.