//import static org.junit.Assert.*;
import java.util.Arrays;
//import org.junit.Test;
class Sol {
public static final class Coord {
private final int col;
private final int row;
public Coord(int _row, int _col) {
col = _row;
row = _col;
}
}
private static final void displayMatrix(int[][] matrix, Coord coord) {
StringBuilder sb = new StringBuilder(matrix.length
* (matrix[0].length * 5) + matrix.length);
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[r].length; c++) {
if (r == coord.row && c == coord.col) {
sb.
append(String.
format("[%2d] ", matrix
[r
][c
])); } else {
sb.
append(String.
format(" %2d ", matrix
[r
][c
])); }
}
sb.append("\n");
}
}
public static Coord findElt(int[][] matrix, int elt) {
for (int r = 0; r < matrix.length; r++) {
int pos
= Arrays.
binarySearch(matrix
[r
], elt
); if (pos >= 0) {
return new Coord(pos, r);
}
if (pos == -1) {
// all values in this row, and all later rows
// are too large.
break;
}
}
return new Coord(-1, -1);
}
private static final void assertEquals(int a, int b) {
if (a != b) {
}
}
// @Test
public void test_0() {
int[][] mat = new int[3][3];
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
displayMatrix(mat, findElt(mat, 8));
assertEquals(-1, findElt(mat, 8).col);
assertEquals(-1, findElt(mat, 8).row);
}
// @Test
public void test_1() {
int[][] mat = new int[3][3];
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
displayMatrix(mat, findElt(mat, 1));
assertEquals(0, findElt(mat, 1).col);
assertEquals(0, findElt(mat, 1).row);
}
// @Test
public void test_2() {
int[][] mat = new int[3][3];
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
displayMatrix(mat, findElt(mat, 3));
assertEquals(2, findElt(mat, 3).col);
assertEquals(0, findElt(mat, 3).row);
}
// @Test
public void test_3() {
int[][] mat = new int[3][3];
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
displayMatrix(mat, findElt(mat, 7));
assertEquals(2, findElt(mat, 7).col);
assertEquals(2, findElt(mat, 7).row);
}
// @Test
public void test_4() {
int[][] mat = new int[3][3];
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
displayMatrix(mat, findElt(mat, 4));
assertEquals(1, findElt(mat, 4).col);
assertEquals(2, findElt(mat, 4).row);
}
public static void main
(String[] args
) { int N = 3;
int[][] mat = new int[N][N];
Sol ex = new Sol();
mat[0][0] = 1;
mat[0][1] = 2;
mat[0][2] = 3;
mat[1][0] = 2;
mat[1][1] = 3;
mat[1][2] = 5;
mat[2][0] = 3;
mat[2][1] = 4;
mat[2][2] = 7;
ex.test_0();
ex.test_1();
ex.test_2();
ex.test_3();
ex.test_4();
Coord a = findElt(mat, 4);
displayMatrix(mat, a);
System.
out.
println(a.
col + " " + a.
row);
}
}
Ly9pbXBvcnQgc3RhdGljIG9yZy5qdW5pdC5Bc3NlcnQuKjsKCmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwoKLy9pbXBvcnQgb3JnLmp1bml0LlRlc3Q7CgpjbGFzcyBTb2wgewoKICAgIHB1YmxpYyBzdGF0aWMgZmluYWwgY2xhc3MgQ29vcmQgewogICAgICAgIHByaXZhdGUgZmluYWwgaW50IGNvbDsKICAgICAgICBwcml2YXRlIGZpbmFsIGludCByb3c7CgogICAgICAgIHB1YmxpYyBDb29yZChpbnQgX3JvdywgaW50IF9jb2wpIHsKICAgICAgICAgICAgY29sID0gX3JvdzsKICAgICAgICAgICAgcm93ID0gX2NvbDsKICAgICAgICB9CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgZmluYWwgdm9pZCBkaXNwbGF5TWF0cml4KGludFtdW10gbWF0cml4LCBDb29yZCBjb29yZCkgewogICAgICAgIFN0cmluZ0J1aWxkZXIgc2IgPSBuZXcgU3RyaW5nQnVpbGRlcihtYXRyaXgubGVuZ3RoCiAgICAgICAgICAgICAgICAqIChtYXRyaXhbMF0ubGVuZ3RoICogNSkgKyBtYXRyaXgubGVuZ3RoKTsKICAgICAgICBmb3IgKGludCByID0gMDsgciA8IG1hdHJpeC5sZW5ndGg7IHIrKykgewogICAgICAgICAgICBmb3IgKGludCBjID0gMDsgYyA8IG1hdHJpeFtyXS5sZW5ndGg7IGMrKykgewogICAgICAgICAgICAgICAgaWYgKHIgPT0gY29vcmQucm93ICYmIGMgPT0gY29vcmQuY29sKSB7CiAgICAgICAgICAgICAgICAgICAgc2IuYXBwZW5kKFN0cmluZy5mb3JtYXQoIlslMmRdICIsIG1hdHJpeFtyXVtjXSkpOwogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBzYi5hcHBlbmQoU3RyaW5nLmZvcm1hdCgiICUyZCAgIiwgbWF0cml4W3JdW2NdKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgc2IuYXBwZW5kKCJcbiIpOwogICAgICAgIH0KICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oc2IpOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgQ29vcmQgZmluZEVsdChpbnRbXVtdIG1hdHJpeCwgaW50IGVsdCkgewogICAgICAgIGZvciAoaW50IHIgPSAwOyByIDwgbWF0cml4Lmxlbmd0aDsgcisrKSB7CiAgICAgICAgICAgIGludCBwb3MgPSBBcnJheXMuYmluYXJ5U2VhcmNoKG1hdHJpeFtyXSwgZWx0KTsKICAgICAgICAgICAgaWYgKHBvcyA+PSAwKSB7CiAgICAgICAgICAgICAgICByZXR1cm4gbmV3IENvb3JkKHBvcywgcik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKHBvcyA9PSAtMSkgewogICAgICAgICAgICAgICAgLy8gYWxsIHZhbHVlcyBpbiB0aGlzIHJvdywgYW5kIGFsbCBsYXRlciByb3dzCiAgICAgICAgICAgICAgICAvLyBhcmUgdG9vIGxhcmdlLgogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIG5ldyBDb29yZCgtMSwgLTEpOwogICAgfQogICAgCiAgICBwcml2YXRlIHN0YXRpYyBmaW5hbCB2b2lkIGFzc2VydEVxdWFscyhpbnQgYSwgaW50IGIpIHsKICAgIAlpZiAoYSAhPSBiKSB7CiAgICAJCXRocm93IG5ldyBJbGxlZ2FsU3RhdGVFeGNlcHRpb24oU3RyaW5nLmZvcm1hdCgiQSAlZCBpcyBub3QgdGhlIHNhbWUgYXMgQiAlZCIsIGEsIGIpKTsKICAgIAl9CiAgICB9CgovLyAgICBAVGVzdAogICAgcHVibGljIHZvaWQgdGVzdF8wKCkgewogICAgICAgIGludFtdW10gbWF0ID0gbmV3IGludFszXVszXTsKCiAgICAgICAgbWF0WzBdWzBdID0gMTsKICAgICAgICBtYXRbMF1bMV0gPSAyOwogICAgICAgIG1hdFswXVsyXSA9IDM7CiAgICAgICAgbWF0WzFdWzBdID0gMjsKICAgICAgICBtYXRbMV1bMV0gPSAzOwogICAgICAgIG1hdFsxXVsyXSA9IDU7CiAgICAgICAgbWF0WzJdWzBdID0gMzsKICAgICAgICBtYXRbMl1bMV0gPSA0OwogICAgICAgIG1hdFsyXVsyXSA9IDc7CgogICAgICAgIGRpc3BsYXlNYXRyaXgobWF0LCBmaW5kRWx0KG1hdCwgOCkpOwoKICAgICAgICBhc3NlcnRFcXVhbHMoLTEsIGZpbmRFbHQobWF0LCA4KS5jb2wpOwogICAgICAgIGFzc2VydEVxdWFscygtMSwgZmluZEVsdChtYXQsIDgpLnJvdyk7CiAgICB9CgovLyAgICBAVGVzdAogICAgcHVibGljIHZvaWQgdGVzdF8xKCkgewogICAgICAgIGludFtdW10gbWF0ID0gbmV3IGludFszXVszXTsKCiAgICAgICAgbWF0WzBdWzBdID0gMTsKICAgICAgICBtYXRbMF1bMV0gPSAyOwogICAgICAgIG1hdFswXVsyXSA9IDM7CiAgICAgICAgbWF0WzFdWzBdID0gMjsKICAgICAgICBtYXRbMV1bMV0gPSAzOwogICAgICAgIG1hdFsxXVsyXSA9IDU7CiAgICAgICAgbWF0WzJdWzBdID0gMzsKICAgICAgICBtYXRbMl1bMV0gPSA0OwogICAgICAgIG1hdFsyXVsyXSA9IDc7CgogICAgICAgIGRpc3BsYXlNYXRyaXgobWF0LCBmaW5kRWx0KG1hdCwgMSkpOwoKICAgICAgICBhc3NlcnRFcXVhbHMoMCwgZmluZEVsdChtYXQsIDEpLmNvbCk7CiAgICAgICAgYXNzZXJ0RXF1YWxzKDAsIGZpbmRFbHQobWF0LCAxKS5yb3cpOwogICAgfQoKLy8gICAgQFRlc3QKICAgIHB1YmxpYyB2b2lkIHRlc3RfMigpIHsKICAgICAgICBpbnRbXVtdIG1hdCA9IG5ldyBpbnRbM11bM107CgogICAgICAgIG1hdFswXVswXSA9IDE7CiAgICAgICAgbWF0WzBdWzFdID0gMjsKICAgICAgICBtYXRbMF1bMl0gPSAzOwogICAgICAgIG1hdFsxXVswXSA9IDI7CiAgICAgICAgbWF0WzFdWzFdID0gMzsKICAgICAgICBtYXRbMV1bMl0gPSA1OwogICAgICAgIG1hdFsyXVswXSA9IDM7CiAgICAgICAgbWF0WzJdWzFdID0gNDsKICAgICAgICBtYXRbMl1bMl0gPSA3OwoKICAgICAgICBkaXNwbGF5TWF0cml4KG1hdCwgZmluZEVsdChtYXQsIDMpKTsKCiAgICAgICAgYXNzZXJ0RXF1YWxzKDIsIGZpbmRFbHQobWF0LCAzKS5jb2wpOwogICAgICAgIGFzc2VydEVxdWFscygwLCBmaW5kRWx0KG1hdCwgMykucm93KTsKICAgIH0KCi8vICAgIEBUZXN0CiAgICBwdWJsaWMgdm9pZCB0ZXN0XzMoKSB7CiAgICAgICAgaW50W11bXSBtYXQgPSBuZXcgaW50WzNdWzNdOwoKICAgICAgICBtYXRbMF1bMF0gPSAxOwogICAgICAgIG1hdFswXVsxXSA9IDI7CiAgICAgICAgbWF0WzBdWzJdID0gMzsKICAgICAgICBtYXRbMV1bMF0gPSAyOwogICAgICAgIG1hdFsxXVsxXSA9IDM7CiAgICAgICAgbWF0WzFdWzJdID0gNTsKICAgICAgICBtYXRbMl1bMF0gPSAzOwogICAgICAgIG1hdFsyXVsxXSA9IDQ7CiAgICAgICAgbWF0WzJdWzJdID0gNzsKCiAgICAgICAgZGlzcGxheU1hdHJpeChtYXQsIGZpbmRFbHQobWF0LCA3KSk7CgogICAgICAgIGFzc2VydEVxdWFscygyLCBmaW5kRWx0KG1hdCwgNykuY29sKTsKICAgICAgICBhc3NlcnRFcXVhbHMoMiwgZmluZEVsdChtYXQsIDcpLnJvdyk7CiAgICB9CgovLyAgICBAVGVzdAogICAgcHVibGljIHZvaWQgdGVzdF80KCkgewogICAgICAgIGludFtdW10gbWF0ID0gbmV3IGludFszXVszXTsKCiAgICAgICAgbWF0WzBdWzBdID0gMTsKICAgICAgICBtYXRbMF1bMV0gPSAyOwogICAgICAgIG1hdFswXVsyXSA9IDM7CiAgICAgICAgbWF0WzFdWzBdID0gMjsKICAgICAgICBtYXRbMV1bMV0gPSAzOwogICAgICAgIG1hdFsxXVsyXSA9IDU7CiAgICAgICAgbWF0WzJdWzBdID0gMzsKICAgICAgICBtYXRbMl1bMV0gPSA0OwogICAgICAgIG1hdFsyXVsyXSA9IDc7CgogICAgICAgIGRpc3BsYXlNYXRyaXgobWF0LCBmaW5kRWx0KG1hdCwgNCkpOwoKICAgICAgICBhc3NlcnRFcXVhbHMoMSwgZmluZEVsdChtYXQsIDQpLmNvbCk7CiAgICAgICAgYXNzZXJ0RXF1YWxzKDIsIGZpbmRFbHQobWF0LCA0KS5yb3cpOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnQgTiA9IDM7CiAgICAgICAgaW50W11bXSBtYXQgPSBuZXcgaW50W05dW05dOwoKICAgICAgICBTb2wgZXggPSBuZXcgU29sKCk7CgogICAgICAgIG1hdFswXVswXSA9IDE7CiAgICAgICAgbWF0WzBdWzFdID0gMjsKICAgICAgICBtYXRbMF1bMl0gPSAzOwogICAgICAgIG1hdFsxXVswXSA9IDI7CiAgICAgICAgbWF0WzFdWzFdID0gMzsKICAgICAgICBtYXRbMV1bMl0gPSA1OwogICAgICAgIG1hdFsyXVswXSA9IDM7CiAgICAgICAgbWF0WzJdWzFdID0gNDsKICAgICAgICBtYXRbMl1bMl0gPSA3OwoKICAgICAgICBleC50ZXN0XzAoKTsKICAgICAgICBleC50ZXN0XzEoKTsKICAgICAgICBleC50ZXN0XzIoKTsKICAgICAgICBleC50ZXN0XzMoKTsKICAgICAgICBleC50ZXN0XzQoKTsKCiAgICAgICAgQ29vcmQgYSA9IGZpbmRFbHQobWF0LCA0KTsKICAgICAgICBkaXNwbGF5TWF0cml4KG1hdCwgYSk7CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihhLmNvbCArICIgIiArIGEucm93KTsKCiAgICB9Cn0=