Skip to content

Instantly share code, notes, and snippets.

@Nucleareal
Created October 5, 2013 14:24
Show Gist options
  • Save Nucleareal/6841531 to your computer and use it in GitHub Desktop.
Save Nucleareal/6841531 to your computer and use it in GitHub Desktop.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AOJ
{
class Program
{
public static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
double[,] rate = new double[401,401];
var dict = new Dictionary<string, int>();
string[] smp = new string[401];
for (int i = 0; i < n; i++)
{
string[] par = Console.ReadLine().Split(' ').ToArray();
int j = int.Parse(par[1]);
string s1 = par[0];
string s2 = par[2];
if (!dict.ContainsKey(s1))
{
dict[s1] = dict.Count;
smp[dict[s1]] = s1;
}
if (!dict.ContainsKey(s2))
{
dict[s2] = dict.Count;
smp[dict[s2]] = s2;
}
rate[dict[s2], dict[s1]] = j;
rate[dict[s1], dict[s2]] = 1D/j;
}
n = dict.Count;
for (int k = 0; k < 2; k++)
{
for (int l = 0; l < n; l++)
for (int m = 0; m < n; m++)
for (int q = 0; q < n; q++)
{
if (rate[m, q] == 0D && rate[m, l] > 0 && rate[l, q] > 0) rate[m, q] = rate[m, l] * rate[l, q];
if (rate[m, q] == 0D && rate[m, l] > 0 && rate[q, l] > 0) rate[m, q] = rate[m, l] / rate[q, l];
}
}
double rr = 0;
string st = "", en = "";
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
if (rr < rate[x, y])
{
rr = rate[x, y];
st = smp[y];
en = smp[x];
}
}
}
Console.WriteLine("1{0}={1}{2}", st, (long)(rr+0.001), en);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment