Informatika gyűjtemény

Egy szinttel feljebb mt_stones.cs

2004050607080910

<<  8. óra  >>

<<  Színes kövek  >>

NézetNyomtat

mt_stones.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: 10 KB
/*
 * Készítette a SharpDevelop.
 * Felhasználó: 02cmezei
 * Dátum: 2007.11.12.
 * Ido: 14:58
 *
 * A sablon megváltoztatásához használja az Eszközök | Beállítások | Kódolás | Szabvány Fejlécek Szerkesztését.
 */
using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;

namespace szinesko
{
       class Program
       {
               public static List<kosor> feladatok=new List<kosor>();
               public class kosor
               {
                       public byte n; //kövek száma
                       public byte s; //színek száma
                       public byte[] k; //kövek

                       public kosor(byte n, byte s)
                       {
                               this.n=n;
                               this.s=s;
                               k=new byte[n];
                       }
/*
                       public bool joe()
                       {
                               int sa=-1;
                               int ss=0;
                               for (int i=0; i!=n; i++)
                               {
                                       if (sa!=k[i])
                                       {
                                               sa=k[i];
                                               ss++;
                                       }
                               }
                               return (sa==s);
                       }

                       public int joe(bool[] t)
                       {
                               int sa=0;
                               int ss=0;
                               int r=0;
                               for (int i=0; i!=n; i++)
                               {
                                       if (t[i])
                                       {
                                               r++;
                                               if ((sa!=k[i]))
                                               {
                                                       sa=k[i];
                                                       ss++;
                                               }
                                       }
                               }

                               if (sa==ss) return r;
                               return int.MaxValue;
                       }

                       public bool joe(BitArray bt)
                       {
                               bool[] szinek=new bool[s];
                               int sa=-1;
                               for (int i=0; i!=n; i++)
                               {
                                       if (k[i]!=sa)
                                       {
                                               if (sa!=-1)
                                               {
                                                       if (szinek[sa-1]) return false;
                                                       szinek[sa-1]=true;
                                               }
                                               sa=k[i];
                                       }
                               }
                               return true;
                       }
*/
}

               public static void Main(string[] args)
               {
                       beolvas("stones.in");
                       int[] m=new int[feladatok.Count];

                       for(int p=0; p!=feladatok.Count; p++) m[p]=munkaLinear(feladatok[p]);

                       kiir("stones.out", m);
               }
#region "régi"
/*
               public class nfo
               {
                       public int min;
                       public bool[] smin;
                       public kosor f;

                       public nfo(kosor f)
                       {
                               this.f=f;
                               min=int.MaxValue;
                               smin=null;
                       }
               }
               //exponenciális
               public static int munkaExp(kosor f)
               {
                       nfo info=new nfo(f);
                       boolsorok(new bool[f.n], info, 0);
                       Console.WriteLine(info.min);
                       return info.min;
               }

               public static void boolsorok(bool[] sor, nfo info, int h)
               {
                       if (h!=info.f.n)
                       {
                               bool[] sor2=(bool[])sor.Clone();
                               sor2[h]=true;

                               boolsorok(sor, info, h+1);
                               boolsorok(sor2, info, h+1);
                       }
                       else
                       {
                               int kivett=info.f.n-info.f.joe(sor);
                               if ((kivett>=0) && (kivett<info.min))
                               {
                                       info.min=kivett;
                                       info.smin=sor;
                               }
                       }
               }

               //egy fokkal jobb
               public static int munkaJobb(kosor f)
               {
                       nfo info=new nfo(f);
                       BitArray bt=new BitArray(f.n, false);
                       int min=opt(bt, info, 0);
                       Console.WriteLine(min);
                       return min;
               }

               public static int noTrue(BitArray bt)
               {
                       int c=0;
                       for (int i=0; i!=bt.Count; i++) if (bt[i]) c++;
                       return c;
               }

               public static int opt(BitArray bt, nfo info, int h)
               {
                       if (h==info.f.n) return (info.f.n-noTrue(bt));

                       BitArray bt2=(BitArray)bt.Clone();
                       bt2[h]=true;

                       int o1=opt(bt, info, h+1);
                       int o2=int.MaxValue;
                       if (info.f.joe(bt2)) o2=opt(bt2, info, h+1);

                       if (o1<o2) return o1;
                       return o2;
               }
               */
#endregion

               //a tökéletes
               public static byte hatvany(byte kit)
               {
                       if (kit==0) return 1;
                       return (byte)(hatvany((byte)(kit-1))*2);
               }

               public struct prefix
               {
                       public byte s, l, h, i; //szinek halmaza, utsó, prefixhossz, hol tartunk
               }

               public class prefixTomb
               {
                       private byte[,,,] p;

                       public prefixTomb(byte szinekszama, byte maxhossz)
                       {
                               p=new byte[hatvany(szinekszama), szinekszama, maxhossz, maxhossz];

                               for (int i=0; i!=hatvany(szinekszama); i++)
                                       for(int j=0; j!=szinekszama; j++)
                                               for(int k=0; k!=maxhossz; k++)
                                                       for(int l=0; l!=maxhossz; l++)
                                                               p[i,j,k,l]=255;
                       }

                       public void setPrefix(prefix P, byte opt)
                       {
                               p[P.s, P.l, P.h, P.i]=opt;
                       }

                       public byte getPrefix(prefix P)
                       {
                               if (P.l!=255) return p[P.s, P.l, P.h, P.i];
                               return 255;
                       }
               }

               static prefixTomb pp;
               static kosor q;
               public static byte munkaLinear(kosor f)
               {
                       pp=new prefixTomb((byte)f.s, (byte)f.n);
                       q=f;
                       prefix u=new prefix();
                       u.s=0;
                       u.i=0;
                       u.l=0;
                       u.h=0;
                       byte min=opt(u);
                       Console.WriteLine(min);
                       return min;
               }

               public static byte opt(prefix p)
               {
                       if (p.i>q.n-1) return (byte)(q.n-p.h);

                       byte ccc=pp.getPrefix(p); if (ccc!=255) return ccc; //ha már cacheltük

                       //hozzáadunk valamit
                       byte o1=byte.MaxValue;
                       if (!((hatvany(q.k[p.i]) | p.s)==p.s) || (q.k[p.i]==p.l))
                       {
                               prefix p2=p;
                               p2.s|=hatvany(q.k[p.i]);
                               p2.l=q.k[p.i];
                               p2.h++;
                               p2.i++;
                               o1=opt(p2);
                       }

                       //nem adunk hozzá semmit
                       p.i++;
                       byte o2=opt(p);
                       p.i--;

                       //minimum
                       if (o2<o1) o1=o2;
                       pp.setPrefix(p, o1);
                       return o1;
               }

               //kiírás, beolvasás
               public static void kiir(string oup, int[] m)
               {
                       TextWriter tw=new StreamWriter(oup);
                       for (int i=0; i!=m.Length; i++) tw.WriteLine(m[i].ToString());
                       tw.Close();
               }

               public static void beolvas(string inp)
               {
                       TextReader tr=new StreamReader(inp);
                       string sor;
                       string[] sorok;
                       while ((sor=tr.ReadLine())!="0 0")
                       {
                               sorok=sor.Split(' ');
                               kosor f=new kosor(Convert.ToByte(sorok[0]),Convert.ToByte(sorok[1]));
                               sorok=tr.ReadLine().Split(' ');
                               feladatok.Add(f);
                               for (int i=0; i!=f.n; i++) f.k[i]=(byte)(Convert.ToByte(sorok[i])-1);
                       }
                       tr.Close();
               }

       }
}
(Vissza)