Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Задача с олимпиады

68K
25 ноября 2011 года
imamatory
6 / / 25.03.2011
Добрый день, прошу помощи в решении задачи. Сегодня на олимпиаде решал, так и не удалось. Интерес не удовлетворен, поэтому прошу помощи.
Цитата:
На соревнования по информационным технологиям приехали команды различных
районов области. Известно, что:
  1. Количество человек в каждой команде может быть любое — от I до N;
  2. Каждый участник соревнований получил индивидуальный порядковый номе^ от I до N, никак не связанный с номером команды;
  3. В каждой команде оказались только знакомые люди (либо непосредственно, либо через другого/других членов этой же команды);
  4. Известны все пары участников соревнований, непосредственно знакомых друг с другом (также считается, что каждый человек знаком сам с собой).
  5. Участники различных команд не знакомы ни лично, ни опосредовано через других людей.
Требуется написать программу, которая определит, какое количество команд прибыло на соревнования.
Ограничения 1 <= n <=200, время 1 с.
Технические требования:
Входной файл COMP.1N.
Выходной файл COMP.OUT.

Внимание! На тестирование принимается исполнимый файл, который дол¬жен иметь имя, соответствующих именам входного и выходного файлов задачи (т.e.COMР.ЕХЕ).
Формат входных данных:
В первой строке входного файла содержится одно натуральное число п (1<п<200).
Во всех остальных строках содержатся разделенные пробелом пары натуральных чисел х (1 < х < п) и у (I < у < п), причем пары могут повторяться произвольное количест¬во раз. Если ни один человек не знаком ни с одним другим, то во входном файле содер¬жится только одна строка с одним натуральное число n (1 < п < 200)
Формат выходных данных:
Выходной файл содержит единственное натуральное число - количество команд
Примеры файлов входных и выходных данных:



З.Ы. Если кому интересно, могу другие выложить, некоторые с решением.

14
25 ноября 2011 года
Phodopus
3.3K / / 19.06.2008
Нужно построить несколько связанных графов.
68K
27 ноября 2011 года
imamatory
6 / / 25.03.2011
Цитата: Phodopus
Нужно построить несколько связанных графов.



А по подробней, граф т.е. используя графику?

287
27 ноября 2011 года
Shiizoo
958 / / 14.03.2004
Цитата: imamatory
А по подробней, граф т.е. используя графику?



Рано, наверное, по олимпиадам :)

граф

443
28 ноября 2011 года
REmindER
292 / / 23.03.2003
Выглядит, как я понял, это примерно так:



То есть для формирования очередной группы нужно выделить ее подграф путем обхода его ребер, связывающих вершины - индивидуальные порядковые номера знакомых участников. Хотя бы можно так:

1. Ищем очередную не отмеченную вершину.
2. Отмечаем ее как пройденную.
3. Определяем список связанных с ней вершин.
4. Для каждой такой вершины из списка, если вершина еще не пройдена, возвращаемся к шагу 2 рекурсивно.
5. Очередная группа определена. Возвращаемся к шагу 1 для определения следующей.
68K
28 ноября 2011 года
imamatory
6 / / 25.03.2011
Цитата: Shiizoo
Рано, наверное, по олимпиадам :)



6-е место у меня, а 5-е уже считается призовым.

А за ссылку спасибо :)

14
28 ноября 2011 года
Phodopus
3.3K / / 19.06.2008
Уж извините не полезу в яндекс, но мне кажется подграф это кусок связанного графа?
68K
30 ноября 2011 года
imamatory
6 / / 25.03.2011
Цитата: REmindER


...

То есть для формирования очередной группы нужно выделить ее подграф путем обхода его ребер, связывающих вершины - индивидуальные порядковые номера знакомых участников. Хотя бы можно так:

1. Ищем очередную не отмеченную вершину.
2. Отмечаем ее как пройденную.
3. Определяем список связанных с ней вершин.
4. Для каждой такой вершины из списка, если вершина еще не пройдена, возвращаемся к шагу 2 рекурсивно.
5. Очередная группа определена. Возвращаемся к шагу 1 для определения следующей.



Я так прикинул, суть и без графов понятна. Если бы они помогли помочь в реализации программы на стадии кодирования – другое дело. Все упирается в код.

443
01 декабря 2011 года
REmindER
292 / / 23.03.2003
Цитата: imamatory
Я так прикинул, суть и без графов понятна. Если бы они помогли помочь в реализации программы на стадии кодирования – другое дело. Все упирается в код.


Была бы ясна суть алгоритма, а код, как говорится, не проблема. В чем конкретно загвоздка в коде тогда?

68K
01 декабря 2011 года
imamatory
6 / / 25.03.2011
Цитата: REmindER
Была бы ясна суть алгоритма, а код, как говорится, не проблема. В чем конкретно загвоздка в коде тогда?



Я представляю себе решение в виде цикла где за одну итерацию от массива(с номерами команд) отсекается ровно одна команда, так вот как отсечь от массива все связанные номера??

443
01 декабря 2011 года
REmindER
292 / / 23.03.2003
Цитата: imamatory
Я представляю себе решение в виде цикла где за одну итерацию от массива(с номерами команд) отсекается ровно одна команда, так вот как отсечь от массива все связанные номера??


Ну хотя бы в самом простом случае их (найденные связанные номера) отмечать как-нибудь и в следующей итерации не просматривать. Pascal под рукой нет, но в общем виде код будет содержать нечто следующее:

Код:
type
{ массив пар }
    M = array[1..200, 1..2] of integer;

{ вспомогательный массив для отметки идентификаторов проверенных участников }
    T = array[1..200] of integer;
var
    C, groups_total, i: integer;

procedure familiarity(id: integer);
var
    j: integer;
begin

T[id] := 1;

for j := 1 to C do
    begin

    if M[j][1] = id and T[M[j][2]] = 0 then familiarity(M[j][2]);
    if M[j][2] = id and T[M[j][1]] = 0 then familiarity(M[j][1]);

    end;

end;

begin

{ ...читаем количество пар в переменную C... }
{ ...читаем пары в массив M... }

for i := 1 to 200 do T := 0;

groups_total := 0;

for i := 1 to C do
    begin

    if T[M[1]] = 0 then
        begin

        groups_total := groups_total + 1;
        familiarity(M[1]);

        end;

    end;

{ groups_total содержит количество выделенных групп со знакомыми участниками }

end.


Если участник n ни с кем не знаком, то пара должна содержать значение [n, n]. Вариант далеко не оптимален, да и я не особый специалист по этому.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог