Начиная с левого верхнего угла начнем кодировать клетки, двигаясь в верхнем ряду слева направо, в следующем в обратную сторону (т.е. справа налево) и так до конца.
Дорога, соединяющая города i и j, даст единицу в две позиции - (i, j) и (j, i). Тогда общее количество единиц в матрице равно удвоенному числу дорог. Отсюда и простое решение - считать N^2 чисел, подсчитать количество единиц и поделить его на 2. Можно считать и сумму - от этого ничего не изменится.
#include <iostream> int main() { int n = 0, sum = 0, temp = 0; std :: cin >> n; for (int i = 0; i < n * n; i++) { std :: cin >> temp; sum += temp; } std :: cout << sum / 2; return 0; }
8288A7F₁₆
Объяснение:
1 - черная клетка;
0 - белая клетка.
Начиная с левого верхнего угла начнем кодировать клетки, двигаясь в верхнем ряду слева направо, в следующем в обратную сторону (т.е. справа налево) и так до конца.
Будет получен код в двоичной системе:
1000001010001000101001111111
Переведем в десятичную систему:
1000001010001000101001111111₂ =
= 1∙2²⁷+0∙2²⁶+0∙2²⁵+0∙2²⁴+0∙2²³+0∙2²²+1∙2²¹+0∙2²⁰+1∙2¹⁹+
+0∙2¹⁸+0∙2¹⁷+0∙2¹⁶+1∙2¹⁵+0∙2¹⁴+0∙2¹³+0∙2¹²+1∙2¹¹+0∙2¹⁰+
+1∙2⁹+0∙2⁸+0∙2⁷+1∙2⁶+1∙2⁵+1∙2⁴+1∙2³+1∙2²+1∙2¹+1∙2⁰ =
= 134217728+0+0+0+0+0+2097152+0+524288+0+0+0+
+32768+0+0+0+2048+0+512+0+0+64+32+16+8+4+2+1 =
= 136874623₁₀
136874623₁₀ переведем в шестнадцатиричную систему:
136874623₁₀ = 8288A7F₁₆
Перевод из десятичной системы в шестнадцатеричную подробнее на фото.
#include <iostream>
int main() {
int n = 0, sum = 0, temp = 0;
std :: cin >> n;
for (int i = 0; i < n * n; i++) {
std :: cin >> temp;
sum += temp;
}
std :: cout << sum / 2;
return 0;
}