1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

Помогите придумать алгоритм к задаче

Тема в разделе "Программирование", создана пользователем Knight, 25.03.08.

  1. Knight

    Knight Участник

    335
    0
    Деление на группы
    Ограничение времени: 0.5 секунды
    Ограничение памяти: 16 МБ


    В детском саду N детей. К сожалению, дети иногда ссорятся, хотя и не часто. У каждого ребёнка есть не более трёх недругов. Можно ли разделить детей на две группы (не обязательно равные) так, чтобы у каждого ребёнка в одной с ним группе было бы не более одного неприятеля?

    Исходные данные

    В первой строке находится положительное число N, не превосходящее 7163. В последующих N строках указаны списки недругов для каждого из детей. В начале каждой строки указывается количество недругов для очередного ребёнка, затем перечисляются номера недругов. Числа в одной строке отделяются друг от друга пробелом.

    Результат

    В первой строке указывается количество детей в той из групп, которая содержит меньшее число детей. Затем во второй строке указывается список детей в этой группе. Числа во второй строке разделяются пробелом. Если в обеих группах одинаковое число детей, то следует выводить описание той, в которой оказывается ребёнок номер 1. Заметим, что вполне возможна ситуация, когда ответ состоит из единственного числа 0. Если возможных разбиений несколько, достаточно вывести любое из них. Если разбить детей на группы невозможно, то в первую строку следует вывести строку 'NO SOLUTION'.

    Пример
    исходные данные
    8
    3 2 3 7
    3 1 3 7
    3 1 2 7
    1 6
    0
    2 4 8
    3 1 2 3
    1 6

    результат
    4
    1 2 5 6

    http://acm.timus.ru/problem.aspx?space=1&num=1128

    Мне нужен алгоритм к этой задачи никак немогу придумать подскажите, брут-форс не предлагать:) ...
     
    Последнее редактирование: 25.03.08
  2. Гость

    Гость Гость

    Вот что вышло на вскидку:
    Создать 3 массива без размера, н-р, а, б, ц
    ввести N
    задать размерность массивам: а(N,3) б(N), ц(N)
    ввести недругов для каждого а(N,3)
    цикл по N
    цикл по б(x)
    если неприятелей>1 то
    цикл по ц(x)
    если неприятелей>1 то No Solution
    конец ц
    иначе в группу ц
    конец б
    конец N
    Не знаю как тут может получится 0, но других идей нет.
     
  3. Гость

    Гость Гость

    Да.. еще иначе надо немного добавить...

    цикл по N
    цикл по б(x)
    если неприятелей>1 то
    цикл по ц(x)
    если неприятелей>1 то No Solution иначе в группу ц
    конец ц
    иначе в группу б
    конец б
    конец N

    запутался немного...
     
  4. colorprint

    colorprint Активный участник

    19.654
    51
    IMHO, рекурсия там будет
     
  5. Гость

    Гость Гость

    Согласен, с рекурсией будет работать на порядок быстрее..
     
  6. Knight

    Knight Участник

    335
    0
    да уже решил давно вот код если интересно
    // 1128. Деление на группы.

    #include "stdafx.h"
    #include <iostream>

    using namespace std;

    const int max_dimensionality_children = 7163;
    const int max_quantity_enemies = 3;

    int dimensionality_children;
    int quantity_enemies[max_dimensionality_children];
    int dimensionality_team;
    int enemies[max_dimensionality_children][max_quantity_enemies];
    int dimensionality_first_group;
    int dimensionality_second_group;
    int team[max_dimensionality_children];

    bool first_group[max_dimensionality_children];
    bool second_group[max_dimensionality_children];
    bool flag_team[max_dimensionality_children];

    int set(int, int);
    int verification(int, bool, int);
    int find_enemies(int, bool, int);
    int change(int, bool, int);
    int links(int);
    int find_links(int);
    int print_group(bool, int);

    int set(int current_index, int comes_index)
    {
    if ((current_index == comes_index) || second_group[comes_index])
    {
    first_group[current_index] = 1;
    dimensionality_first_group++;
    }
    else
    {
    second_group[current_index] = 1;
    dimensionality_second_group++;
    }
    team[dimensionality_team] = current_index;
    dimensionality_team++;
    verification(current_index, 1, current_index);
    links(current_index);
    return 0;
    }
    int verification(int verification_index, bool verification_flag, int current_index)
    {
    bool flag_enemies;

    int index;

    flag_enemies = 0;

    for (index = 0; index < quantity_enemies[verification_index]; index++)
    {
    if ((first_group[enemies[verification_index][index]] && first_group[verification_index]) || (second_group[enemies[verification_index][index]] && second_group[verification_index]))
    {
    if (flag_enemies)
    {
    change(verification_index, 0, current_index);
    return 0;
    }
    flag_enemies = 1;
    }
    }
    if (verification_flag)
    find_enemies(verification_index, 0, current_index);
    return 0;
    }
    int find_enemies(int find_enemies_index, bool verification_flag, int current_index)
    {
    int index;

    for (index = 0; index < quantity_enemies[find_enemies_index]; index++)
    {
    if (first_group[enemies[find_enemies_index][index]] || second_group[enemies[find_enemies_index][index]])
    verification(enemies[find_enemies_index][index], 0, current_index);
    }
    return 0;
    }
    int change(int change_index, bool verification_flag, int current_index)
    {
    if (first_group[change_index])
    {
    first_group[change_index] = 0;
    dimensionality_first_group--;
    second_group[change_index] = 1;
    dimensionality_second_group++;
    }
    else
    {
    second_group[change_index] = 0;
    dimensionality_second_group--;
    first_group[change_index] = 1;
    dimensionality_first_group++;
    }
    current_index = change_index;
    find_enemies(current_index, 1, current_index);
    return 0;
    }
    int links(int current_index)
    {
    int index;

    if (flag_team[current_index])
    find_links(current_index);
    for (index = 0; index < dimensionality_team; index++)
    {
    if (flag_team[index])
    find_links(index);
    }
    return 0;
    }
    int find_links(int current_index)
    {
    int index;

    for (index = 0; index < quantity_enemies[current_index]; index++)
    if (!first_group[enemies[current_index][index]] && !second_group[enemies[current_index][index]])
    {
    set(enemies[current_index][index], current_index);
    return 0;
    }
    flag_team[current_index] = 0;
    return 0;
    }
    int print_group(bool group[], int dimensionality_group)
    {
    int index;

    cout << dimensionality_group;
    if (dimensionality_group != 0)
    cout << endl;
    for (index = 0; index < dimensionality_children; index++)
    if (group[index])
    {
    cout << index + 1;
    dimensionality_group--;
    if (dimensionality_group != 0)
    cout << ' ';
    else
    break;
    }
    return 0;
    }
    int main(int argc, _TCHAR* argv[])
    {
    int index, second_index;

    cin >> dimensionality_children;

    for (index = 0; index < dimensionality_children; index++)
    {
    first_group[index] = 0;
    second_group[index] = 0;
    flag_team[index] = 1;
    cin >> quantity_enemies[index];
    for (second_index = 0; second_index < quantity_enemies[index]; second_index++)
    {
    cin >> enemies[index][second_index];
    enemies[index][second_index]--;
    }
    }

    dimensionality_first_group = 0;
    dimensionality_second_group = 0;
    dimensionality_team = 0;

    index = 0;
    do
    {
    if (!first_group[index] && !second_group[index])
    {
    set(index, index);
    dimensionality_team = 0;
    }
    index++;
    }
    while (dimensionality_first_group + dimensionality_second_group != dimensionality_children);

    if (dimensionality_first_group <= dimensionality_second_group)
    print_group(first_group, dimensionality_first_group);
    else
    print_group(second_group, dimensionality_second_group);

    cout << endl;
    return 0;
    }

    добавлено через 20 минут
    Да и кстати ответа 'NO SOLUTION' здесь не может быть...
     
  7. dj

    dj Активный участник

    1.058
    21
    а не пора ли придумать админам форума тэг "code"?