Informatika gyűjtemény

NézetNyomtat

kb_kimer.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 5 KB
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Kimer
{
    class Measurement
    {
        private int from, to, q;

        public Measurement(int _from, int _to, int _q)
        {
            from = _from + 1;
            to = _to + 1;
            q = _q;
        }

        public void print(StreamWriter outs)
        {
            outs.WriteLine("{0} {1} {2}", from, to, q);
        }
    }

    class Program
    {
        private int[] t = new int[3];
        private int[] k = new int[2];
        private int[,] m = new int[3, 2];
        private List<Measurement> res = new List<Measurement>(10);

        public Program()
        {
            StreamReader ins = new StreamReader("kimer.be");
            string[] line = ins.ReadLine().Split(' ');
            t[0] = int.Parse(line[0]);
            t[1] = int.Parse(line[1]);
            t[2] = int.Parse(line[2]);
            line = ins.ReadLine().Split(' ');
            k[0] = int.Parse(line[0]);
            k[1] = int.Parse(line[1]);

            // elől legyen a kisebb, hogy abból legyen kevesebb, a többet pedig mellé konfigoljuk!
            if (k[1] < k[0])
            {
                int tmp;
                tmp = k[1];
                k[1] = k[0];
                k[0] = tmp;
            }

            Solve();
        }

        private void Solve()
        {
            int desire = (t[0] + t[1] + t[2]) / 3;
            bool noSolution = false;

            // csak akkor van gond, ha mindkét edényünk páros, mert azzal csak párost lehet összehozni, és ha van páratlan különbség az szívás!
            if (k[0] % 2 == 0 && k[1] % 2 == 0)
            {
                for (int i = 0; i < 2; i++)
                {
                    if (Math.Abs(t[i] - desire) % 2 == 1)
                    {
                        noSolution = true;
                        break;
                    }
                }
            }

            if (!noSolution)
            {
                GetMinChanges(desire);

                // megvannak, hogy hova mennyi kell, szépen csináljuk meg a kért változtatásokat!
                for (int i = 0; i < 2; i++)
                {
                    // i = melyik kancsót használjuk áttöltéshez
                    for (int a = 0; a < 3; a++)
                    {
                        // ha az adott edénnyel nincs mit áttölteni, akkor ne próbálkozzunk
                        if (m[a, i] == 0) continue;
                        for (int b = a + 1; b < 3; b++)
                        {
                            if (m[a, i] > 0 && m[b, i] < 0)
                            {
                                res.Add(new Measurement(b, a, k[i]));
                                m[a, i]--;
                                m[b, i]++;
                                a--; // ugyanazt még vizsgáljuk tovább!
                                break;
                            }
                            else if (m[a, i] < 0 && m[b, i] > 0)
                            {
                                res.Add(new Measurement(a, b, k[i]));
                                m[b, i]--;
                                m[a, i]++;
                                a--; // ugyanazt még vizsgáljuk tovább!
                                break;
                            }
                        }
                    }
                }
            }

            StreamWriter outs = new StreamWriter("kimer.ki");
            if (!noSolution)
            {
                outs.WriteLine(res.Count);
                for (int i = 0; i < res.Count; i++)
                    res[i].print(outs);
            }
            else
            {
                outs.WriteLine(-1);
            }
            outs.Close();
        }

        private void GetMinChanges(int desire)
        {
            // Tulajdonképpen itt egy ilyen diofantoszi egyenlet megoldását keressük:
            // desire - t[i] = k[0] * x + k[1] * y
            // ahol k[0] = A, k[1] = B, és igaz, hogy A<B (ez ahhoz kell, hogy a kisebb kancsóból legyen kevesebb áttöltés, így lesz minimális)
            
            int x;
            // csak az első 2-t állítjuk be a harmadik magától beáll!
            for (int i = 0; i < 2; i++)
            {
                // amit össze kell hoznunk a két kancsóból: (desire - t[i])
                x = 0;
                while (true)
                {
                    if ((desire - t[i] - x * k[0]) % k[1] == 0)
                    {
                        // ha találunk egy jó x-et, és y-t, akkor az nagyon tuti!
                        m[i, 0] = x;
                        m[2, 0] -= x;
                        m[i, 1] = (desire - t[i] - x * k[0]) / k[1];
                        m[2, 1] -= m[i, 1];
                        break;
                    }
                    else if ((desire - t[i] + x * k[0]) % k[1] == 0)
                    {
                        m[i, 0] = -x;
                        m[2, 0] += x;
                        m[i, 1] = (desire - t[i] + x * k[0]) / k[1];
                        m[2, 1] += m[i, 1];
                        break;
                    }
                    x++;
                }
            }
        }

        static void Main(string[] args)
        {
            new Program();
        }
    }
}
(Vissza)