Карлики
Цитата: Тимур от 23.09.2021, 14:09Всем привет, решил порешать задачки на c# и наткнулся на эту. Уже около часа сижу туплю, подтолкните в сторону решения, пожалуйста.
[spoiler title="ссылка на задачу"]https://www.e-olymp.com/ru/problems/7945[/spoiler]
Всем привет, решил порешать задачки на c# и наткнулся на эту. Уже около часа сижу туплю, подтолкните в сторону решения, пожалуйста.
Цитата: Вася от 24.09.2021, 13:37Привет!
Создал клас Gnome, который имеет список (HashSet) гномов поменьше, и если получилось так, что гном который выше, является дочерним дочернего гнома, то-есть меньше меньшего, тогда результат будет impossible.
[spoiler title="Код"]
using System; using System.Collections.Generic; namespace ConsoleApp2 { class Gnome { public string Name { get; set; } public HashSet<Gnome> LesserGnomes { get; set; } = new HashSet<Gnome>(); } class Program { static List<Gnome> gnomes = new List<Gnome>(); /// <summary> /// Создаёт гнома и добавляем в список если его нет. Если есть - возвращает из списка. /// </summary> /// <param name="name">имя гнома</param> /// <returns>найденного или созданного гнома</returns> static Gnome FindOrCreateGnome(string name) { Gnome gnome = gnomes.Find(g => g.Name == name); if (gnome == null) { gnome = new Gnome { Name = name }; gnomes.Add(gnome); } return gnome; } /// <summary> /// Рекурсивно проверяет является ли меньший гном выше /// </summary> /// <param name="higherGnomes">список гномов, которые выше</param> /// <param name="gnome">гном, которые содержит гномов, которые поменьше</param> /// <returns>true если меньший гном является выше, иначе false</returns> static bool Check(HashSet<Gnome> higherGnomes, Gnome gnome) { foreach (Gnome lesserGnome in gnome.LesserGnomes) { foreach (Gnome higherGnome in higherGnomes) { if (higherGnome.Name == lesserGnome.Name) { return true; } } higherGnomes.Add(lesserGnome); if (Check(higherGnomes, lesserGnome)) { return true; } higherGnomes.Remove(lesserGnome); } return false; } static void Main(string[] args) { int count = int.Parse(Console.ReadLine()); for (int i = 0; i < count; i++) { string[] split = Console.ReadLine().Split(); Gnome first = FindOrCreateGnome(split[0]); Gnome second = FindOrCreateGnome(split[2]); bool firstIsHigher = split[1] == ">"; if (firstIsHigher) { first.LesserGnomes.Add(second); } else { second.LesserGnomes.Add(first); } } bool isImpossible = false; foreach (Gnome gnome in gnomes) { if (Check(new HashSet<Gnome> { gnome }, gnome)) { isImpossible = true; break; } } Console.WriteLine(isImpossible ? "impossible" : "possible"); } } }[/spoiler]
[spoiler title="Результаты"]
[/spoiler]
Привет!
Создал клас Gnome, который имеет список (HashSet) гномов поменьше, и если получилось так, что гном который выше, является дочерним дочернего гнома, то-есть меньше меньшего, тогда результат будет impossible.
using System;
using System.Collections.Generic;
namespace ConsoleApp2
{
class Gnome
{
public string Name { get; set; }
public HashSet<Gnome> LesserGnomes { get; set; } = new HashSet<Gnome>();
}
class Program
{
static List<Gnome> gnomes = new List<Gnome>();
/// <summary>
/// Создаёт гнома и добавляем в список если его нет. Если есть - возвращает из списка.
/// </summary>
/// <param name="name">имя гнома</param>
/// <returns>найденного или созданного гнома</returns>
static Gnome FindOrCreateGnome(string name)
{
Gnome gnome = gnomes.Find(g => g.Name == name);
if (gnome == null)
{
gnome = new Gnome { Name = name };
gnomes.Add(gnome);
}
return gnome;
}
/// <summary>
/// Рекурсивно проверяет является ли меньший гном выше
/// </summary>
/// <param name="higherGnomes">список гномов, которые выше</param>
/// <param name="gnome">гном, которые содержит гномов, которые поменьше</param>
/// <returns>true если меньший гном является выше, иначе false</returns>
static bool Check(HashSet<Gnome> higherGnomes, Gnome gnome)
{
foreach (Gnome lesserGnome in gnome.LesserGnomes)
{
foreach (Gnome higherGnome in higherGnomes)
{
if (higherGnome.Name == lesserGnome.Name)
{
return true;
}
}
higherGnomes.Add(lesserGnome);
if (Check(higherGnomes, lesserGnome))
{
return true;
}
higherGnomes.Remove(lesserGnome);
}
return false;
}
static void Main(string[] args)
{
int count = int.Parse(Console.ReadLine());
for (int i = 0; i < count; i++)
{
string[] split = Console.ReadLine().Split();
Gnome first = FindOrCreateGnome(split[0]);
Gnome second = FindOrCreateGnome(split[2]);
bool firstIsHigher = split[1] == ">";
if (firstIsHigher)
{
first.LesserGnomes.Add(second);
}
else
{
second.LesserGnomes.Add(first);
}
}
bool isImpossible = false;
foreach (Gnome gnome in gnomes)
{
if (Check(new HashSet<Gnome> { gnome }, gnome))
{
isImpossible = true;
break;
}
}
Console.WriteLine(isImpossible ? "impossible" : "possible");
}
}
}
Цитата: Тимур от 25.09.2021, 16:14Спасибо, буду разбираться.
Спасибо, буду разбираться.


