Задача
В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.
Вводные данные
В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.
Выходные данные
Вывести одно число — количество дорог на планете «Neptune».
Тесты
| Входные данные | Выходные данные |
|
$3$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$ |
$3$ |
|
$3$ $0$ $1$ $0$ $1$ $0$ $0$ $0$ $0$ $0$ |
$1$ |
|
$5$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ |
$3$ |
Код программы(использование матрицы смежности)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] x = new int[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { x[i][j] = in.nextInt(); } } int roads = 0; for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { if(x[i][j] == 1) roads++; } } System.out.print(roads); } } |
Решение задачи(использование матрицы смежности)
Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и если попадается $1$, то увеличиваем число дорог на $1$. Выводим количество дорог. Задача решена.
Код программы(потоковая обработка)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n=0; int i; while(in.hasNextInt()) { i = in.nextInt(); if(i == 1) n++; } System.out.print(n/2); } } |
Решение задачи(потоковая обработка)
Для решения задачи вводим числа пока они вводятся. Поскольку дороги идут с одного города в другой и наоборот, то их количество будет равно половине единичек в матрице смежности, то есть половине единичек входящих во входной поток. Cчитаем их количество и делим на $2$. Выводим количество дорог. Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com(матрица смежности)
Код решения на ideone.com(потоковая обработка)