Matematické Fórum

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using CodEx;

namespace Loupeznici
{
    class Nacitac
    {
        Reader reader;

        public Nacitac()
        {
            reader = new Reader("poklad.in");
        }
        
        private bool JeCislice(int znak)
        {
            return ((znak >= (char)'0') && (znak <= (char)'9'));
        }

        public int[] NactiVstup(out int soucetPrvku)
        {
            soucetPrvku = 0;
            int pocetPrvku = this.reader.Int();
            if (pocetPrvku == 0) throw new Exception("Autor si ze mne dělá legraci, ale já se jen tak nedám!");
            string zahodit = this.reader.Line();
            int[] vystup = new int[pocetPrvku + 1];
            int nacteneCislo = 0;
            for (int i = 1; i <= pocetPrvku; i++)
            {
                nacteneCislo = this.reader.Int();
                if (nacteneCislo < 1) throw new Exception("Autor si ze mne dělá legraci, ale já se jen tak nedám!");
                vystup[i] = nacteneCislo;
                soucetPrvku += nacteneCislo;
            }
            return vystup;
        }
    }

    class Loupeznici
    {
        static void Main(string[] args)
        {
            //inicializace výstupu
            FileStream vystupni_soubor = new FileStream("poklad.out", FileMode.Create, FileAccess.Write);
            StreamWriter vystup = new StreamWriter(vystupni_soubor);
            try
            {
                Nacitac nacitac = new Nacitac();
                int hledanySoucet = 0;
                int[] poklad = nacitac.NactiVstup(out hledanySoucet);
                //Pokud je vstup prázdný nebo součet prvků nelze dělit dvěma beze zbytku, nemá smysl dále počítat.
                if ((poklad.Length == 0) || ((hledanySoucet % 2) != 0)) throw new Exception("prazdny vstup nebo zarucene neexistujici reseni");
                else
                {
                    hledanySoucet /= 2;
                    int pocetPredmetu = poklad.Length - 1;
                    int[] iteracniPole = new int[2000001];
                    iteracniPole[0] = -1;
                    //int counter = 0;
                    for (int k = 1; k <= pocetPredmetu; k++)
                    {
                        for (int i = hledanySoucet; i >= poklad[k]; i--)
                        {
                            if ((iteracniPole[i - poklad[k]] != 0) && (iteracniPole[i] == 0))
                            {
                                iteracniPole[i] = k;
                                //counter++;
                                if (i == hledanySoucet) goto skok;
                            }
                        }
                    }
                    skok:
                    if (iteracniPole[hledanySoucet] == 0) throw new Exception("Reseni nenalezeno."); //Největší možné zaplnění není optimální.
                    int nalezenyMaxSoucet = hledanySoucet;
                    //while (iteracniPole[nalezenyMaxSoucet] == 0) { nalezenyMaxSoucet--; }
                    while (iteracniPole[nalezenyMaxSoucet] != -1)
                    {
                        vystup.Write("{0} ", iteracniPole[nalezenyMaxSoucet]);
                        nalezenyMaxSoucet = nalezenyMaxSoucet - poklad[iteracniPole[nalezenyMaxSoucet]];
                    }
                }
            }
            catch //Pokud jakákoliv fáze výpočtu ukazuje na neexistenci řešení, je vyhozena výjimka, která je zde "ošetřena" vypsáním informace o neexistenci řešení.
            {
                vystup.Write("no");
            }
            finally //Nakonec je třeba soubor uzavřít.
            {
                vystup.Close();
            }
        }
    }
}