89. Раскраска кубиков

Сара познакомилась с новой игрой, похожей на Игрушку - конструктор, которую ей подарили на день рождения. Эта игра называется Неограниченное Воображение (НВ). Она состоит из большого количества одинаковых кубиков таких, что каждая их грань имеет площадь 1 см². Эта игра (НВ) имеет специфическое свойство состоящее в том, что можно соединить два кубика вместе грань к грани при помощи специального клея, если эти грани точно подогнаны одна к другой. Старший брат Сары Дариус решил придумать задачу для Сары с использованием НВ. Он построил трехмерный объект, используя эти кубики и хочет, чтобы Сара раскрасила все грани кубиков, которые не связаны между собой. Считается, что грань не есть связанной, если она не соединена с другим кубиком. Например, представьте объект изображенный на рисунке.

В приведенном примере количество всех не связанных граней равно 16. Проблема состоит в следующем – найти число, указывающее площадь, которую должна покрасить Сара.

Вход. Первая строка содержит количество тестов. Каждый тест начинается со строки, содержащей количество кубиков n (1 ≤ n ≤ 200). Кубики пронумерованы числами от 1 до n.

Следующие n строк описывают создание новых объектов: данные о связывании каждого кубика задаются в одной строке. Каждая из этих строк начинается с целого числа І, являющегося номером кубика, после чего идет символ двоеточия ":" и пробел, за которым следуют несколько целых чисел(не более шести), которые есть номерами кубиков, соединенных с кубиком І, и заканчивается единственным нулевым символом "0", указывающим на конец этого множества.

Гарантируется, что данные для каждого теста могут реализовать действительный объект в пространстве. Важным является также то, что кубы могут сконструировать любой сложный объект или даже несколько небольших отдельных объектов.

Выход. Для каждого теста вывести в отдельной строке количество несвязанных граней для всех кубиков.

Пример входа	Пример выхода
3 4 1: 2 3 0 2: 1 4 0 3: 4 1 0 4: 2 3 0 3 1: 2 0 2: 3 1 0 3: 2 0 4 1: 2 0 2: 1 0 3: 4 0 4: 3 0	16 14 20

РЕШЕНИЕ

математика - вычисления

Анализ алгоритма

Каждый кубик имеет 6 граней. В каждом тесте нам известно, сколько граней каждого кубика связано с другими. Следовательно остальные грани свободны. Остается для каждого теста просуммировать количество несвязанных граней для всех кубиков.

Реализация алгоритма

Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

s = 0;

for(i = 0; i < n; i++)

{

Читаем номер кубика. В переменной cnt подсчитываем количество связанных граней.

scanf("%d:",&val);

cnt = 0;

while(scanf("%d",&val), val != 0) cnt++;

Суммируем количество несвязанных граней для всех кубиков.

s += 6 - cnt;

}

Выводим ответ.

printf("%d\n",s);

}

Java реализация

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String []args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("89.in"));

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int s = 0;

for(int i = 0; i < n; i++)

{

con.next(); // skip token 1:

int cnt = 0;

while(true)

{

int val = con.nextInt();

if (val == 0) break;

cnt++;

}

s += 6 - cnt;

}

System.out.println(s);

}

}

}