Структуры данных: определить все пары чисел (h, s), при которых компания h контролирует компанию s - C#
Формулировка задачи:
Всем добрый вечер!
Пытался решать через двумерный массив,вылетает постоянно за границу...Да и дальше как именно выбрать 50% и подвладельцев не знаю...
Помогите пожалуйста написать это чудо
Заранее спасибо за помощь!
Условие
Некоторые компании являются совладельцами других компании, так как приобрели часть их акций. Говорят, что компания А контролирует компанию В, если имеет место по меньшей мере одно из следующих условий:
· А=В;
· А владеет более, чем 50% акций В;
· А контролирует k (k>0) компаний С1,…,Сk таких, что компания Сi владеет соответственно Xi% акций компании В (i=1,…,k) и Х1+Х2+ …+Хk>50%.
Необходимо определить все пары чисел (h, s), при которых компания h контролирует компанию s.
Входные данные: input.txt
Во входном файле задается последовательность троек (i, j, p), которые означают, что компания i владеет p% акций компании j.
Общее число компаний не превышает 100.
Выходные данные: output.txt
Выходные данные заносятся в файл, каждая строка которого соответствует найденной паре (h, s) (элементы в строке разделены пробелом).
Пары упорядочены лексикографически.
Пример
input.txt
2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
4 2 52
5 3 30
output.txt
4 2
4 3
4 5
Парни очень нужна помощь
Решение задачи: «Структуры данных: определить все пары чисел (h, s), при которых компания h контролирует компанию s»
textual
Листинг программы
using System; using System.Collections.Generic; using System.IO; namespace CompanyProblem { using Grapth = List<List<int>>; class Program { private readonly static Grapth _g = new Grapth(); private static readonly int[,] _stock = new int[100,100]; private static int _c; private static void BuildGraph(TextReader reader) { string line; var lines = new List<string>(100); while (!string.IsNullOrEmpty(line = reader.ReadLine())) lines.Add(line); for (int i = 0; i < 100; ++i) _g.Add(new List<int>()); InitStock(lines.Count); foreach (var s in lines) { var ss = s.Split(); int i = int.Parse(ss[0]) - 1; int j = int.Parse(ss[1]) - 1; int p = int.Parse(ss[2]); _g[i].Add(j); _stock[i, j] = p; } } private static void InitStock(int size) { //_stock = new int[size, size]; for (int i = 0; i < _stock.GetLength(0); ++i) for (int j = 0; j < _stock.GetLength(1); ++j) _stock[i, j] = 0; } private static void Resolve(TextReader reader, TextWriter writer) { BuildGraph(reader); for (_c = 0; _c < _g.Count; ++_c) for (int v = 0; v < _g.Count; ++v) Dfs(v); var res = GetResult(); Print(res, writer); } private static void Dfs(int v) { if (_stock[_c, v] <= 50 || _c == v) return; foreach (var t in _g[v]) { _stock[_c, t] += _stock[v, t]; Dfs(t); } } private static IEnumerable<string> GetResult() { var res = new List<string>(); int size = _stock.GetLength(0); for (int i = 0; i < size; ++i) for (int j = 0; j < size; ++j) if (_stock[i, j] > 50) res.Add(string.Format("{0} {1}", i + 1, j + 1)); res.Sort(); return res; } private static void Print(IEnumerable<string> res, TextWriter writer) { foreach (var s in res) writer.WriteLine(s); } static void Main() { using (var reader = new StreamReader("input.txt") /* Console.In*/) using (var writer = new StreamWriter("output.txt")/* Console.Out*/) Resolve(reader, writer); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д