Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 27.01.2016, 18:52   #1
Чума
Новичок
Джуниор
 
Регистрация: 27.01.2016
Сообщений: 4
По умолчанию Олимпиадная задача (K человечков, N населенных пунктов, между ними есть М дорог

Условие:
Есть K человечков (1<=K<=100). Они хотят встретиться в населенном пункте. Их N (1<=N<=1000). между населенными пунктами есть М дорог (1<=М<=10000). Нужно вычислить, в скольких населенных пунктах они могут встретиться, если ввести кол-во человечков, потом в К рядках номер населенного пункта, а в М рядках дорога от одного населенного пункта в другой (как координаты). Вывести количество пунктов.
Пример:
Ввели
2 4 4
2 4
1 3
2 1
4 2
4 6

Вывели
3

Последний раз редактировалось Чума; 27.01.2016 в 18:55.
Чума вне форума Ответить с цитированием
Старый 28.01.2016, 22:59   #2
dimon_snake
Форумчанин
 
Регистрация: 05.11.2015
Сообщений: 167
По умолчанию

А наработки какие-либо есть?
dimon_snake вне форума Ответить с цитированием
Старый 29.01.2016, 09:03   #3
Mad_Lord
Пользователь
 
Регистрация: 23.01.2016
Сообщений: 14
По умолчанию

Вот, держи решение:

Код:
Label Q;
Var Map:Array of array of boolean;
    man: array of integer;
    i, j, p,                        //счетчики
    k, n, m,                       //данные в условии переменные
    town1, town2, KolVo: integer; 
    odinak, obshiy:boolean;
    
Begin
 Writeln('Введите количество людей');
 Readln (k);
 Setlength (man, k);
 For i:=0 to k-1 do Begin 
                    Writeln ('Введите местоположение человека под номером ', (i+1)); 
                    Readln (town1);
                    man[i]:= town1;
                    End;
 //местоположение людей записано
 
 
 //начинается создание карты
 Writeln('Введите количество населенных пунктов');
 Readln (n);
 Setlength (map, n);
 For i:=0 to n-1 do Begin 
                    Setlength (map[i], n); 
                    (map[i])[i]:= true; 
                    End;
 //создана карта без дорог
                    
 Writeln ('Введите количество дорог');
 Readln (m);
 For i:=1 to m do Begin
                  Writeln('Введите 2 соединенных населенных пункта');
                  Readln (town1, town2);
                  (Map[town1])[town2]:=true;
                  (Map[town1])[town1]:=true;
                  End;
//города попарно соединены

//Начинается сведение городов
Q: For i:=0 to n-1 do For j:= 0 to n-1 do Begin
                                           odinak:=true;
                                           obshiy:=false;
                                           For p:=0 to n-1 do If (((map[i])[p]))<>(((map[j])[p])) then odinak:=false;
                                           For p:=0 to n-1 do If (((map[i])[p]))=(((map[j])[p])) then obshiy:=true;
                                           If (odinak=false) and (obshiy=true)then Begin               //если есть хоть 1 общий город и дороги не одинаковы, то выполнить сведение
                                                                                   For p:=0 to n-1 do Begin
                                                                                                      If (map[i])[p] = true then (map[i])[p]:=true;
                                                                                                      If (map[j])[p] = true then (map[j])[p]:=true;
                                                                                                      End;
                                                                                   goto Q;             //после сведения вернуться к началу проверки
                                                                                   End;
                                           End; 
                                           
                                           //создание карты завершено
                                           
 
 Kolvo:=0;
 For i:=0 to n-1 do Begin 
                    obshiy:=true;
                    For j:=0 to k-1 do If ( (  map[i]  ) [ man[j] ] )= false then obshiy:=false;     //если из i того города нельзя попасть в город с человеком
                    If obshiy=true then inc (KolVo);                                                 //если в i тый город можно попасть всеми людьми, то...
                    End;
 Writeln ('Количество подходящих для встречи городов ', kolvo);
 End.
Mad_Lord вне форума Ответить с цитированием
Старый 29.01.2016, 17:45   #4
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

О мой Бог. Да тут четвёртая степень будет. Мрак и ужасть.. Даёшь бфс в массы
Poma][a вне форума Ответить с цитированием
Старый 29.01.2016, 23:14   #5
Naive
Раздолбайских Дел
Старожил
 
Аватар для Naive
 
Регистрация: 22.05.2009
Сообщений: 3,828
По умолчанию

именно после таких задач либо становятся фронтендерами, либо навсегда забивают на программирование)))

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

Последний раз редактировалось Naive; 29.01.2016 в 23:35.
Naive вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача на паскале: Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна. Rhc Помощь студентам 27 31.12.2013 15:04
1 и 2 форма. Связь между ними. Roman1295 Общие вопросы Delphi 1 02.11.2012 17:15
тяжелая, но интересная задача: Дано 3 числа. Между ними можно ставить знаки операций: сложения, вычитания, умножения, деления ВДПУ Помощь студентам 2 25.02.2012 19:59
Ноты и интервалы между ними треч Помощь студентам 5 01.02.2008 02:39