// is22 // Ürmössy Dorottya, 150382833199, Budapest, Budapesti Fazekas M . Gyak. Ált. Isk. és Gimn, dorottya.urmossy@gmail.com, // Microsoft Visual Studio Community 2015 Version 14.0.25431.01 // Visual C# 2015 using System; //using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace is22 { class Program { const int URES = 0, PIROS = 1, KEK = 2; static int u, l; static int N, K, P; static bool Keres(int N, int K, int P, out int u, out int l) { // ha egyszerű, kiszámítja u-t és l-ut // ha hosszú, kiveszi a felesleget // különben elindítja a rekurziv számítást u = 0; l = 0; if (P>K) { int a = P; P = K; K = a; } if(N-P-K==1) { // ha egyszerű u = P * K; l = P + K; return true; } if(N>(P+K)*2+1) { // ha hosszu és sok az ures int x = N - ((P + K) * 2 + 1); N = N - x; Program.N = N; if (Keres(N, K, P, out u, out l)) { int k1 = K % 2; int p1 = P % 2; int k2 = K / 2; int p2 = P / 2; u = u + x * (k2 + p2); l = l + x * (k1 + p1); N = N + x; Program.N = N; return true; } else { N = N + x; Program.N = N; return false; } } // a szamitas indítása Status StartStatus = new Status(); Status S2 = new Status(); if (BFS(StartStatus, out S2)) { u = S2.jumps; l = S2.steps; return true; } else { return false; } } public class Status { // egy allapotot és jellemzői public int[] ribbon; // maga a szalag public int jumps; // ugrasok szama public int steps; // lepesek szama public int counter; // a következő lépések vezerlesehez public int distance; // az allapot "jósága" public bool marked; // ha már volt ilyen állapot és abból továbbszámoltunk public Status() { ribbon = new int[N]; jumps = 0; steps = 0; counter = 0; distance = 0; //P * (N - P) + K * (N - K); for (int i = 0; i < N; i++) ribbon[i] = URES; for (int i = 0; i < P; i++) ribbon[i] = PIROS; for (int i = 0; i < K; i++) ribbon[N - 1 - i] = KEK; marked = false; } public Status(Status S2) { ribbon = new int[N]; ribbon = S2.CopyRibbon(); jumps = S2.jumps; steps = S2.steps; counter = S2.counter; distance = S2.distance; marked = S2.marked; } public void Move(int a, int b) { // a szalag ket elemet csereli ki int ra = ribbon[a]; ribbon[a] = ribbon[b]; ribbon[b] = ra; if (Math.Abs(a - b) == 2) jumps++; else steps++; distance = 1000 * steps - jumps; counter = 0; } public void Mark(List SQ) { // egy mar letezo allapotot kizar marked = true; distance = Int32.MaxValue; SQ.Insert(Rank(SQ, this), this); } public int[] CopyRibbon() { // a szalag masolasa egyik allapotból a masikba int[] copiedRibbon = new int[N]; for (int i = 0; i < N; i++) copiedRibbon[i] = ribbon[i]; return copiedRibbon; } public bool ThisIsTheEnd() { // ezt az állapotot keressük? for (int i = 0; i < K; i++) if (ribbon[i] != KEK) return false; for (int i = 0; i < P; i++) if (ribbon[N - 1 - i] != PIROS) return false; return true; } public bool NextChild(out Status S2) { // előállatja egy állapot következő "gyermekét" S2 = new Status(this); int index = counter / 10; // melyik pozicióban keresünk üres elemet int type = counter % 10; // milyen jellegő mozgást fog keresni (az előző kereséskor lett beállítva if (index >= N) return false; // nincs több if (ribbon[index] != URES) { // a következő pozicióban kell keresni index++; counter = index * 10; return NextChild(out S2); } if (type == 0) // kék ugras { if (index < N - 2) { if (ribbon[index + 1] != URES && ribbon[index + 2] == KEK) { if (!((index == 1) && (ribbon[2] == KEK) && (ribbon[0] == PIROS)) && (!((index > 1) && (ribbon[index + 1] == KEK) && (ribbon[index - 1] == PIROS) && (ribbon[index - 2] == PIROS)))) { S2.Move(index + 2, index); counter++; return true; } } } type = 1; counter = 10 * index + type; } if (type == 1) // piros ugras { if (index > 1) { if (ribbon[index - 1] != URES && ribbon[index - 2] == PIROS) { if (!((index == N - 2) && (ribbon[N - 3] == PIROS) && (ribbon[N - 1] == KEK)) && (!((index < N - 2) && (ribbon[index - 1] == PIROS) && (ribbon[index + 1] == KEK) && (ribbon[index + 2] == KEK)))) { S2.Move(index - 2, index); counter++; return true; } } } type = 2; counter = 10 * index + type; } if (type == 2) // kek lepes { if (index < N - 1) { if (ribbon[index + 1] == KEK) { if (!((index == 2) && (ribbon[1] == KEK) && (ribbon[0] == PIROS)) && (!((index > 2) && (ribbon[index - 1] == KEK) && (ribbon[index - 2] == PIROS) && (ribbon[index - 3] == PIROS)))) { S2.Move(index + 1 , index); counter++; return true; } } } type = 3; counter = 10 * index + type; } if (type == 3) // piros lepes { if (index > 0) { if (ribbon[index - 1] == PIROS) { if (!((index == N - 3) && (ribbon[N - 2] == PIROS) && (ribbon[N - 3] == KEK)) && (!((index < N - 3) && (ribbon[index + 1] == PIROS) && (ribbon[index + 2] == KEK) && (ribbon[index + 3] == KEK)))) { S2.Move(index - 1, index); index++; counter = index * 10; return true; } } } } // ide nem lehetett lépni, nézzük a következőt index++; counter = index * 10; return NextChild(out S2); } } static public bool NotTooDeep(Queue SQ, Status S2) { // nem használt foreach (Status S1 in SQ) if (S1.steps < S2.steps) return false; foreach (Status S1 in SQ) if (S1.steps == S2.steps && S1.jumps > S2.jumps) return false; return true; } static public bool AreSame(Status S1, Status S2) { // megállapítja, hogy egyforma-e két állapot for (int i = 0; i < N; i++) if (S1.ribbon[i]!=S2.ribbon[i]) return false; if (S1.steps != S2.steps) return false; return true; } static public bool NoSameInTheList(List SQ, Status S2) { // megnézi, hogy volt-e illetve van-e ilyen állapot a litsában for (int i = 0; i < SQ.Count; i++) if (AreSame(SQ[i],S2)) return false; return true; } static public int Rank(List SQ, Status S2) { // kiszámítja, hová kell betenni a listába az új elemet for (int i = 0; i < SQ.Count; i++) if (SQ[i].distance > S2.distance ) return i; return SQ.Count; } static public void printribbon(Status S) { // kiirja egy allapot szalagját for (int i = 0; i < N; i++) { switch (S.ribbon[i]) { case URES: Console.Write('.'); break; case PIROS: Console.Write('O'); break; case KEK: Console.Write('X'); break; default: break; } } Console.WriteLine(" {0} {1} {2}", S.jumps, S.steps, S.distance); //Console.ReadKey(true); } static public void printqueueall(List SQ) { // kiirja a lista összes elemét Console.WriteLine("----------------"); foreach (Status S in SQ) if (S.distance!=Int32.MaxValue) printribbon(S); Console.ReadKey(true); } static public void printqueue(List SQ) { // kiirja a lista első 20 elemet Console.WriteLine("----------------"); //foreach (Status S in SQ) if (S.distance!=Int32.MaxValue) printribbon(S); int max = 20; if (SQ.Count < max) max = SQ.Count; for (int i = 0; i < max; i++) if (SQ[i].distance != Int32.MaxValue) printribbon(SQ[i]); Console.ReadKey(true); } static public void printqueue2(List SQ) { // kiirja a lista legfelső elemét printribbon(SQ[0]); } static bool BFS(Status StartStatus, out Status EndStatus) { // a fő logikai rész // a listába helyezi (sorrendet tartva) egy adott állapot összes lehetséges gyerekét és aztán a legjobbakkal tovabb dolgozik EndStatus = new Status(); List SQ = new List(); SQ.Add(StartStatus); // berakja a kezdő állapotot if (StartStatus.ThisIsTheEnd()) // és megnézi, hogy ez végállapot-e { EndStatus = new Status(StartStatus); return true; } Status S; while (SQ.Count!=0) // ez soha sem lesz 0, mert mindig van megoldas { S = SQ[0]; SQ.RemoveAt(0); // az első elem kivétele S.Mark(SQ); // es eltarolasa, mint már nem vizsgalando allapot bool ThereIsaNext = true; Status S2 = new Status(S); //cases++; while (ThereIsaNext) { ThereIsaNext = S.NextChild(out S2); // a következo gyermek if (ThereIsaNext && NoSameInTheList(SQ, S2)) // ha még nem volt ilyen { SQ.Insert(Rank(SQ, S2), S2); // a helyére illeszti //printribbon(S2); if (S2.ThisIsTheEnd()) // megnézzük, hogy végállapot-e { EndStatus = new Status(S2); //Console.WriteLine(cases); return true; } } } //printqueueall(SQ); } return false; } static void Main(string[] args) { bool autoinput = false; // true, hogy ne kelljen mindig beírni kézzel, false ha standard input string[] stringlist; String line; //--------------------- // adatok beolvasasa //--------------------- if (autoinput) line = "9 2 2"; else line = Console.In.ReadLine(); stringlist = line.Split(new char[] { ' ' }); N = int.Parse(stringlist[0]); K = int.Parse(stringlist[1]); P = int.Parse(stringlist[2]); //--------------------- // számítások elvégzése //--------------------- if (Keres(N, K, P, out u,out l)) //--------------------- // eredmény kiirasa //--------------------- { Console.WriteLine("{0} {1} {2}", u + l, u, l); } else { Console.WriteLine("{0} {1} {2}", 0, 0, 0); } //Console.ReadKey(); } } }