/************************************************ Grundlegende Algorithmen mit Java, http://algorithmen-und-problemloesungen.de/ Copyright @2007-2009 by Doina Logofatu in C#: Michael Gärtner ************************************************/ using System; using System.Collections; using System.Collections.Generic; using System.IO; // ********************************************************************* // ACHTUNG: Laufzeitumgebung = .NET Framework 3.5 (wegen HashSet Klasse) // ********************************************************************* namespace Logofatu { class P11Orangensport { private static String FileInputName = "orangen.in"; private static String FileOutputName = "orangen.out"; private static void makeDecision(int n1, int n2, StreamWriter sw) { List> b = new SetsList(n1).getValue(); List> c = new SetsList(n2).getValue(); if ( b.Count == 0 && c.Count == 0 ) sw.WriteLine("Beide luegen! Unentschieden!"); else if ( b.Count == 0 ) sw.WriteLine("Der Erste luegt! Der Zweite gewinnt!"); else if (c.Count == 0) sw.WriteLine("Der Zweite luegt! Der Erste gewinnt!"); else if (n1 < n2) if ( isADisjointCombination(b,c) ) sw.WriteLine("Der zweite Spieler gewinnt!"); else sw.WriteLine("Der erste Spieler gewinnt!"); else if ( isADisjointCombination(b, c) ) sw.WriteLine("Der erste Spieler gewinnt!"); else sw.WriteLine("Der zweite Spieler gewinnt!"); } private static bool isACommonElement(HashSet setA, HashSet setB) { foreach ( int el in setA ) { if ( setB.Contains(el) ) return true; } return false; } private static bool isADisjointCombination(List> b, List> c) { bool flag = false; short bSiz = (short) b.Count; short cSiz = (short)c.Count; for ( short i = 0; !flag && i < bSiz; i++ ) for ( short j = 0; !flag && j < cSiz; j++ ) if ( !isACommonElement(b[i],c[j]) ) flag = true; return flag; } static void Main(string[] args) { StreamReader sr = null; StreamWriter sw = null; try { sw = new StreamWriter(FileOutputName); sr = new StreamReader(FileInputName); while ( !sr.EndOfStream ) { string[] sArray = sr.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); int n1 = int.Parse(sArray[0]); int n2 = int.Parse(sArray[1]); makeDecision(n1, n2, sw); } } catch ( IOException ex ) { Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex.ToString()); } finally { if ( sr != null ) { sr.Close(); } if ( sw != null ) { sw.Close(); } } } } class SetsList { private BitArray x; private List a; private List> value; public SetsList(int n) { this.value = new List>(); this.a = new List(); this.x = new BitArray(100); for ( int i = 2; i < 100; i++ ) if ( 0 == n % i ) a.Add(i); back(n, 1, this.value); } public List> getValue() { return value; } private void addSet(int k, List> b) { HashSet auxSet = new HashSet(); for ( int i = 1; i < k; i++ ) if ( x[i] ) auxSet.Add(a[i - 1]); b.Add(auxSet); } private void back(int n, int k, List> b) { int p = 1; int aSiz = a.Count; for ( int j = 1; j < k; j++ ) if ( x[j] ) p *= a[j - 1]; if ( p == n ) { addSet(k, b); } else if ( k <= aSiz ) for ( int i = 0; i < 2; i++ ) { x.Set(k, 0 != i); if ( i == 0 ) back(n, k + 1, b); else if ( 0 == (n / p) % a[k-1] ) { x.Set(k,true); if ( 1 == (n / p) / a[k-1] || (n / p) / a[k-1] > a[k-1] ) back(n, k+1, b); } } } } }