{"code":"lqdojcontest10bai9","name":"LQDOJ Contest #10 - Bài 9 - Trò Chơi Trốn Tìm","description":"[user:shiba] và chú chó [user:_minhduc] của mình chơi trò trốn tìm với nhau, trong đó [user:shiba] là người đi tìm và [user:_minhduc] sẽ đi trốn. Trong ngôi nhà của [user:shiba] có $N$ hộp khác nhau đứng liền kề nhau và được đánh số từ $1$ đến $N$. [user:_minhduc] sẽ trốn vào một hộp bất kì trong $N$ hộp đó. Sau khi trốn xong [user:shiba] bắt đầu đi tìm, mỗi giây [user:shiba] sẽ thực hiện thao tác tìm chú chó của mình như sau:\r\n\r\n - Đầu tiên [user:shiba] chọn một hộp bất kì và kiểm tra nó (ta sẽ gọi hộp đó là hộp đã kiểm tra). Nếu [user:shiba] thấy chú chó [user:_minhduc] của mình ở đó thì trò chơi kết thúc, nếu chưa tìm ra thì [user:shiba] sẽ đặt lại hộp vào chỗ cũ.\r\n\r\n - Sau đó, [user:_minhduc] sẽ chọn một trong hai lựa chọn như sau: nằm im ở trong hộp mình đang đứng, hoặc nhảy sang hộp bên cạnh (hộp cạnh bên trái hoặc hộp cạnh bên phải đều được). Lưu ý rằng [user:_minhduc] có thể nhảy vào hộp đã kiểm tra nếu đó là hộp bên cạnh chú chó ấy đang đứng (giả sử rằng thời gian nhảy từ hộp này sang hộp khác là không đáng kể, có thể nói là $0$ giây).\r\n\r\n\r\nCác lựa chọn của [user:_minhduc] tùy thuộc vào tình trạng của nó lúc đó. Cụ thể [user:_minhduc] có hai tâm trạng như sau:\r\n\r\n - Nếu [user:_minhduc] đang ở tình trạng sợ hãi thì nó sẽ nhảy ra xa hộp đã kiểm tra. Nếu nó đang ở hộp số $1$ hoặc ô số $N$ thì nó sẽ đứng im trong hộp đấy.\r\n\r\n - Nếu [user:_minhduc] đang ở tình trạng tò mò thì nó sẽ nhảy đến gần hộp đã kiểm tra (lưu ý rằng [user:_minhduc] luôn có thể tiến lại gần hơn).\r\n\r\n**Lưu ý rằng chú chó [user:_minhduc] chỉ hành động dựa trên hộp đã kiểm tra gần nhất, không quan tâm đến hộp đã kiểm tra trước đó.**\r\n\r\nVì [user:_minhduc] là một con chó cưng của [user:shiba] nên anh ấy hiểu rất rõ các tâm trạng của [user:_minhduc]. [user:shiba] biết rằng tình trạng của [user:_minhduc] luôn xen kẽ giữa đúng $X$ giây sợ hãi và $Y$ giây tò mò. Ví dụ với $X = 1$ và $Y = 2$ thì tâm trạng của [user:_minhduc] lần lượt sẽ là (sợ hãi, tò mò, tò mò, sợ hãi, tò mò, tò mò, sợ hãi,...).\r\n\r\n[user:shiba] cảm thấy việc tìm chú chó của mình quá khó khăn nên anh ấy quyết định nhờ các bạn tài năng của **LQDOJ** tính toán một chuỗi các hộp cần kiểm tra sao cho chú chó [user:_minhduc] dù cho lúc đầu có trốn ở đâu thì [user:shiba] sẽ luôn tìm ra chú chó ấy.\r\n\r\n**Yêu cầu:** Bạn hãy giúp [user:shiba] giải quyết vấn đề trên.\r\n\r\n#### Input\r\n\r\n - Chứa ba số nguyên lần lượt là $N,X,Y$ $(2 \\le N \\le 10^4; 0 \\le X,Y \\le 50)$. \r\n\r\n#### Output \r\n\r\n - Dòng đầu tiên in ra số giây $M$ [user:shiba] cần để tìm ra chú chó [user:_minhduc].\r\n\r\n - Dòng tiếp theo in ra $M$ số nguyên nằm trong đoạn $[1;N]$ là liệt kê các hộp được kiểm tra vào mỗi giây (trình tự này được phép lặp lại). Mỗi số được liệt kê cách nhau một khoảng trắng.\r\n\r\n#### Scoring\r\n\r\nGọi $M$ là số giây trong trình tự tìm hộp của bạn. Nếu bạn cố kiểm tra một hộp không hợp lệ (tức là hộp bạn kiểm tra nằm ngoài đoạn $[1;N]$) hoặc trình tự tìm hộp của bạn không phải lúc nào cũng có thể tìm ra chú chó [user:_minhduc] thì bạn sẽ nhận được $0$ điểm với chú thích ```Wrong Answer```. Với mỗi test có $P$ điểm thì bạn sẽ nhận được $k \\times P$ điểm với $k$ là:\r\n\r\n - $k = 0$ nếu $M > 2 \\times N$.\r\n\r\n - $k = 1$ nếu $M \\le T$.\r\n\r\n - Các trường hợp còn lại $k = \\frac{1}{2} \\times (\\frac{T}{M})^2$.\r\n\r\n - Ta có $T = \\frac{N\\ \\times(X+Y)}{X+2max(X,Y)} + 3max(X,Y)$.\r\n\r\n\r\n#### Subtask\r\n - Subtask $1$ ($8\\%$ số điểm): Có $X = 0$ và $Y = 1$.\r\n - Subtask $2$ ($12\\%$ số điểm): Có $X = 1$ và $Y = 0$.\r\n - Subtask $3$ ($8\\%$ số điểm): Có $X = 1$ và $Y = 1$.\r\n - Subtask $4$ ($72\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        10 2 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        6\r\n        1 3 10 6 8 10\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Đây là một ví dụ về trò chơi: Giả sử chú chó ban đầu trốn ở ô số $5$.\r\n         \r\n         | Giây | Ô đã kiểm tra |     Tình trạng của chú chó trước khi nhảy |             Ô của chú chó sau khi nhảy          |\r\n         |:----:|:-------------:|:-----------------------------------------:|:-----------------------------------------------:|\r\n         |  $1$ |      $1$      |                   Sợ hãi                  |                $5 \\rightarrow 6$                |\r\n         |  $2$ |      $3$      |                   Sợ hãi                  |                $6 \\rightarrow 7$                |\r\n         |  $3$ |      $10$     |                   Tò mò                   |                $7 \\rightarrow 8$                |\r\n         |  $4$ |      $6$      |                   Sợ hãi                  |                $8 \\rightarrow 9$                |\r\n         |  $5$ |      $8$      |                   Sợ hãi                  |                $9 \\rightarrow 10$               |\r\n         |  $6$ |      $10$     |                   Tò mò                   | Đã bị tìm thấy nên không thể di chuyển được nữa |\r\n         \r\n         Giả sử vẫn chưa tìm thấy thì [user:shiba] có thể tiếp tục lặp lại trình tự của mình đến khi tìm ra chú chó của mình.\r\n         Test ví dụ này thỏa mãn yêu cầu đề bài và $M \\le T$ $(6 < 11)$ nên sẽ được điểm tuyệt đối.","points":2500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}