{"code":"masoi","name":"Chơi bài ma sói (E div 1)","description":"Hôm nay  [bin9638](https://lqdoj.edu.vn/user/bin9638)  đang đánh bài ma sói với  [algorit](https://lqdoj.edu.vn/user/algorit)  và  [WuTan](https://lqdoj.edu.vn/user/WuTan), vì đã quá chán luật ma sói cũ nên cậu đã tự nghĩ ra luật mới.\r\n\r\nBộ bài ma sói gồm một số lá, gồm những lá như sau:\r\n\r\n-   Lá  **dân làng**  : được kí hiệu là \"**D**\", trong bộ bài có thể chứa nhiều lá  **dân làng**.\r\n    \r\n-   Lá  **ma sói**: được kí hiệu là \"**M**\", trong bộ bài có thể chứa nhiều lá  **ma sói**.\r\n    \r\n-   Lá  **thợ săn**: được kí hiệu là \"**T**\", trong bộ bài có thể chứa nhiều lá  **thợ săn**.\r\n    \r\n-   Lá  **phù thủy**: được kí hiệu là \"**P**\", trong bộ bài có thể chứa nhiều lá  **phù thùy**.\r\n    \r\n-   Lá  **chiến thắng**: được kí hiệu là \"**#**\", trong bộ bài chỉ chứa  **duy nhất MỘT**  lá  **chiến thắng**.\r\n    \r\n\r\nTrong mỗi lượt chơi:\r\n\r\n-   Chỉ được rút  **MỘT lá ở đầu hoặc cuối**  bộ bài.\r\n    \r\n-   Có thể sử dụng các lá bài  **thợ săn**  đang có trên tay, sau khi dùng  **một lá thợ săn**, người chơi sẽ bỏ đồng thơi  **một lá thợ săn**  và  **một lá ma sói**  xuống (không dược bỏ lại vào bộ bài).\r\n    \r\n-   Có thể sử dụng các lá bài  **phù thùy**  đang có trên tay, sau khi dùng  **một lá phù thùy**  người chơi sẽ bỏ đồng thời  **một lá phù thùy**  và  **một lá dân làng**  xuống (không được bỏ lại vào bộ bài).\r\n    \r\n-   Người chơi có thể sử dụng tùy ý số lượng lá bài mình đang có, tuy nhiên chỉ được rút  **một lá bài duy nhất**. Không nhất thiết phải làm theo thứ tự, người chơi có thể rút bài trước rồi sử dụng các lá bài, hoặc sử dụng các lá bài trước, rồi sau đó mới rút bài.\r\n    \r\n-   Khi kết thúc một lượt chơi, nếu số lá  **ma sói**  người chơi đang có trên tay  **lớn hơn hẳn**  số lá  **dân làng**  người chơi đang có thì sói sẽ ăn hết dân, lúc này trò chơi kết thúc và người chơi sẽ thua cuộc.\r\n    \r\n-   Người chơi sẽ chiến thắng nếu rút được lá  **chiến thắng**.\r\n    \r\n\r\nTuy là người đặt ra luật của trò chơi này, nhưng  [bin9638](https://lqdoj.edu.vn/user/bin9638)  không biết cách chơi như thế nào để chiến thắng, đồng thời sau khi chiến thắng, anh ấy muốn  **chênh lệch**  giữa số lá  **dân làng**  còn lại trên tay và số lá  **ma sói**  còn lại trên tay là  **nhỏ nhất**.\r\n\r\nHãy giúp  [bin9638](https://lqdoj.edu.vn/user/bin9638)  chơi một cách tối ưu nhất nhé!\r\n\r\n<h4>Input</h4>\r\n\r\n-   Dòng đầu tiên là số ván bài $Q$.\r\n-  $Q$  dòng tiếp theo mỗi dòng là một xâu $S$ miêu tả bộ bài.\r\n\r\n#### Input\r\n - Gồm  $Q$ dòng với mỗi dòng là kết quả của ván đấu tương ứng, nếu  [bin9638](https://lqdoj.edu.vn/user/bin9638)  thua thì ghi \"**LOSE**\", ngược lại ghi số lá bài chênh lệch bé nhất sau khi thắng.\r\n\r\n#### Constrains\r\n\r\n - $Q \\leq 50$\r\n - $|S| \\leq 2000$.\r\n \r\n#### Scoring\r\n\r\n - Subtask $1$ ($30\\%$ số điểm): $|S| \\leq 10$.\r\n - Subtask $2$ ($30\\%$ số điểm): $|S| \\leq 100$.\r\n - Subtask $3$ ($30\\%$ số điểm): $|S| \\leq 1000$.\r\n - Subtask $4$ ($20\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n\t\t5\r\n\t\tM#DMMT\r\n\t\tMD#DM\r\n\t\tMM#DDDPPT\r\n\t\tDDDP#DDDD\r\n\t\tTPMD#MM\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0\r\n\t\tLOSE\r\n\t\t0\r\n\t\t2\r\n\t\t0\r\n\r\n        ```\r\n   \r\n    ??? warning \"Note\"\r\n        -   Ở ván bài đầu tiên, bóc các lá lần lượt ở vị trí $6,1,2$ (sử dụng lá  **T**  để loại một lá  **M**  để chiến thắng).\r\n        -   Ván bài thứ hai, người chơi không thể bóc bài vì bị chặn hai lá  **M**  ở hai đầu.\r\n        -   Ván bài thứ ba người chơi bóc các lá ở vị trí  $9,8,7,6,5,1,2,3$ ( không cần sử dụng các lá  **P**  và  **T**).\r\n        -   Ván thứ 4, người chơi bốc ở vị trí $1,2,3,4,5$ ( sử dụng lá  **P**).\r\n        -   Ván cuối, người chơi bốc ở vị trí $1,2,3,4,5$ ( sử dụng cả lá  **T**  và  **P**  )","points":2000.0,"partial":false,"time_limit":2.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}