{"raw_statement":[{"iden":"statement","content":"Percolation is the process of a liquid slowly passing through a filter or surface. We will consider a 2d mesh or lattice grid for our surface. \n\nA lattice grid here is a normal 2-dimensional grid (where each cell is connected to at most 4 cell at its 4-side) with an additional circular connection at its border. Meaning if we have a lattice of dimension (4, 5) then cell at position (2, 1) will have a connection with cell (2, 5), and cell at position (1, 4) will have a connection with cell (4, 4). In other words the left-most cells will have a connection with the right-most cells in the same row and the top-most cells will have a connection with the bottom-most cells in the same column.\n\nEach lattice grid is made of different surface or material, which determines the atomic gap in each cell and whether it will allow any liquid to pass through. For each cell (i, j) in the lattice you will be given the probability pij of accepting any given liquid. Each liquid also has its own probability threshold p, if any cell has less probability than p then that liquid does not pass through and that cell remains unoccupied.\n\nGiven the details of lattice cells and the threshold p it will create clusters of occupied cells (by the liquid) using the connection of each cell. Now if at least one of the cluster has all the following characteristics then the lattice percolates—\n\n * Has at least 1 cell from each row.\n\n * Has at least 1 cell from each column.\n\nThe first line of input contains two integers and a float. The two integers n and m (1 ≤ n, m ≤ 1000) indicates width and length of the lattice. The float p (0.00 ≤ p ≤ 1.00) indicates the threshold for the given liquid.\n\nThe following n lines each contains m floats p11, pij, ...pnm which indicates the probability of accepting any given liquid for cell (i, j).\n\nThe input data set is big.\n\nPrint 'YES' if the lattice percolates or else 'NO', without the qoutes.\n\n"},{"iden":"input","content":"The first line of input contains two integers and a float. The two integers n and m (1 ≤ n, m ≤ 1000) indicates width and length of the lattice. The float p (0.00 ≤ p ≤ 1.00) indicates the threshold for the given liquid.The following n lines each contains m floats p11, pij, ...pnm which indicates the probability of accepting any given liquid for cell (i, j).The input data set is big."},{"iden":"output","content":"Print 'YES' if the lattice percolates or else 'NO', without the qoutes."},{"iden":"examples","content":"Input4 4 0.500.19 0.52 0.23 0.330.78 0.65 0.45 0.490.48 0.66 0.77 0.890.30 0.36 0.88 0.15OutputYESInput3 3 0.100.09 0.09 0.090.09 0.10 0.090.09 0.09 0.09OutputNO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the lattice, with $ 1 \\leq n, m \\leq 1000 $.  \nLet $ p \\in [0,1] $ be the liquid's threshold probability.  \nLet $ P = (p_{i,j}) \\in [0,1]^{n \\times m} $ be the probability matrix for each cell $ (i,j) $, where $ i \\in \\{1, \\dots, n\\} $, $ j \\in \\{1, \\dots, m\\} $.  \n\nDefine the occupied set:  \n$$\nO = \\left\\{ (i,j) \\in \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} \\mid p_{i,j} \\geq p \\right\\}\n$$\n\nThe lattice has toroidal (circular) connectivity:  \n- Horizontal neighbors: $ (i,j) \\sim (i, j \\pm 1 \\mod m) $  \n- Vertical neighbors: $ (i,j) \\sim (i \\pm 1 \\mod n, j) $  \n\nLet $ \\mathcal{C} $ be the set of connected components (clusters) of $ O $ under this toroidal adjacency.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 1000 $  \n2. $ 0.00 \\leq p \\leq 1.00 $  \n3. $ 0.00 \\leq p_{i,j} \\leq 1.00 $ for all $ i,j $\n\n**Objective**  \nDetermine whether there exists a cluster $ C \\in \\mathcal{C} $ such that:  \n- $ \\forall i \\in \\{1, \\dots, n\\}, \\exists j \\in \\{1, \\dots, m\\} : (i,j) \\in C $  (covers all rows)  \n- $ \\forall j \\in \\{1, \\dots, m\\}, \\exists i \\in \\{1, \\dots, n\\} : (i,j) \\in C $  (covers all columns)  \n\nIf such a cluster exists, output \"YES\"; otherwise, output \"NO\".","simple_statement":"You are given an n×m grid where each cell (i,j) has a probability pij of allowing liquid to pass. A liquid with threshold p can only pass through cells where pij ≥ p. The grid wraps around: left connects to right, top connects to bottom.\n\nLiquid forms connected clusters (up/down/left/right). The grid \"percolates\" if there exists one cluster that touches every row and every column.\n\nPrint \"YES\" if such a cluster exists, otherwise \"NO\".","has_page_source":false}