{"code":"pretst2022goldsilver","name":"Thi thử vòng 2 2022 - Vàng Bạc","description":"Bạn có một lưới ô vuông gồm $R$ hàng và $C$ cột. Các hàng được đánh số từ $1$ đến $R$, các cột được đánh số từ $1$ đến $C$. Trên ô nằm ở hàng i và cột $j$ có $G[i][j]$ miếng vàng, $S[i][j]$ miếng bạc và $B[i][j]$ miếng đồng. \r\n \r\nBạn cần đi từ ô góc trái trên (thuộc hàng $1$ cột $1$) tới ô góc phải dưới (thuộc hàng $R$ cột $C$) của lưới. Đường đi của bạn cần thoả mãn các điều kiện sau:\r\n- Trong mỗi bước, bạn chỉ được đi từ vị trí hiện tại sang một trong bốn ô kề cạnh. \r\n- Tổng số miếng đồng trên các ô bạn đã đi qua không quá $K$.\r\n- Đường đi của bạn cần có số bước nhỏ nhất có thể.\r\n- Trong số các đường đi có số bước tối thiểu, bạn cần chọn đường đi sao cho (tổng số miếng vàng chia cho tổng số miếng bạc) xét trên các ô đã đi qua là lớn nhất\r\n\r\n#### Input\r\n\r\nDòng đầu tiên chứa 3 số nguyên $R, C, K$ $(1 \\leq R*C \\leq 160, 1 \\leq K \\leq 10^9)$\r\n\r\n- $R$ dòng tiếp theo, dòng thứ $i$ chứa $C$ số nguyên: $G[i][1] ... G[i][C]$ $(1 \\leq G[i][j] \\leq 10^6, G[1][1] = G[R][C] = 0)$\r\n\r\n- $R$ dòng tiếp theo, dòng thứ $i$ chứa $C$ số nguyên: $S[i][1] ... S[i][C]$ $(1 \\leq S[i][j] \\leq 10^6, S[1][1] = S[R][C] = 0)$\r\n\r\n- $R$ dòng tiếp theo, dòng thứ $i$ chứa $C$ số nguyên: $B[i][1] ... B[i][C]$ $(1 \\leq B[i][j] \\leq 10^6, B[1][1] = B[R][C] = 0)$\r\n\r\n\r\n#### Output:\r\n- Gồm 1 dòng, in ra $-1$ nếu không thể đi từ ô $(1,1)$ đến ô $(R,C)$, ngược lại in ra tỉ lệ vàng chia bạc lớn nhất. Đáp án của bạn được chấp nhận nếu sai khác không quá $10^{-6}$ so với đáp án của ban giám khảo. Nói cách khác, gọi $P$ là đáp số của bạn và $J$ là đáp số của ban giám khảo, bạn sẽ được tính là giải đúng khi và chỉ khi $\\dfrac{|P - J|}{max(1, |J|)} \\leq 10^{-6}$.\r\n\r\n#### Scoring\r\nBộ test của bài được chia làm các subtask như sau:\r\n- Subtask 1 (17 điểm): $R*C \\leq 50$\r\n- Subtask 2 (17 điểm): $K  \\leq 3000$\r\n- Subtask 3 (29 điểm): $G, S \\leq 7$\r\n- Subtask 4 (37 điểm): Không có ràng buộc gì thêm.\r\n\r\nĐiểm tối đa của bài là $100$ điểm.\r\n\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        2 2 100\r\n        0 2\r\n        3 0\r\n        0 3\r\n        5 0\r\n        0 70\r\n        80 0\r\n    ???+ success \"Output\"\r\n        0.6666667\r\n    ??? warning \"Note\"\r\n        - Trong ví dụ ở trên, ta di chuyển trên theo đường $(1, 1) -> (1, 2) -> (2, 2)$, như vậy, tổng số miếng vàng chia tổng số miếng bạc trên đường     đi là $\\dfrac{2}{3} = 0.6666667$","points":700.0,"partial":false,"time_limit":4.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}}