|
|
back to boardWA3--C#--Help! Posted by roshan 30 Aug 2015 19:50 hello,i got wa3.can you tell me why?or give me some tests.thank you very much! the source: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Timus1003 { class Program { static void Main(string[] args) { System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture; List<Phone> arrayList=new List<Phone>(); while(true) {
string phoneNumber=Console.ReadLine(); if(phoneNumber=="-1") { break; } Phone phone = new Phone(); phone.PhoneNumber =phoneNumber ; phone.Size =Convert.ToInt32(Console.ReadLine()); string[] dics = new string[phone.Size]; int n=0; while(n<phone.Size) { dics[n] = Console.ReadLine(); n++; } phone.Dics = dics; arrayList.Add(phone); } // Console.WriteLine("out"); for(int i=0;i<arrayList.Count;i++) {
Phone phone = arrayList[i]; phone.Dics = phone.Dics.OrderByDescending(s => s.Length).ToArray<string>(); String[] str = new String[phone.Dics.Length]; for(int j=0;j<phone.Dics.Length;j++) { str[j] = wordToNumber(phone.Dics[j]); } phone.HasSolution=find(phone.PhoneNumber, str, phone); if(phone.HasSolution) { string solutionStr = ""; for(int k=0;k<phone.Solutions.Count;k++) { if(k==phone.Solutions.Count-1) { solutionStr = solutionStr + phone.Solutions[k] + ""; } else { solutionStr = solutionStr + phone.Solutions[k] + " "; }
} Console.WriteLine(solutionStr); } else { Console.WriteLine("No solution."); } } Console.ReadLine();
} public static bool find(string phoneNumber,string[] dics,Phone phone) {
for (int i = 0; i < dics.Length;i++ ) { // if (phoneNumber == "") return true; if (phoneNumber == dics[i]) { phone.Solutions.Add(phone.Dics[i]); //Console.Write(phone.Dics[i] + " "); return true; }
if (phoneNumber.IndexOf(dics[i]) == 0) { phone.Solutions.Add(phone.Dics[i]); // Console.Write(phone.Dics[i] + " "); string newPhoneNumber = phoneNumber.Substring(dics[i].Length); if(find(newPhoneNumber, dics, phone)) { return true; } else { phone.Solutions.RemoveAt(phone.Solutions.Count-1); continue; }
}
} // Console.WriteLine("No solution."); return false; }
public static string wordToNumber(string word) { char[] wordArr = word.ToCharArray(); char[] numArr = new char[wordArr.Length]; for (int i = 0; i < wordArr.Length;i++ ) { numArr[i] = charToNumber(wordArr[i]); } return new String(numArr); } public static char charToNumber(char mychar) { switch(mychar) { case 'i': case 'j': return '1'; case 'a': case 'b': case 'c': return '2'; case 'd': case 'e': case 'f': return '3'; case 'g': case 'h': return '4'; case 'k': case 'l': return '5'; case 'm': case 'n': return '6'; case 'p': case 'r': case 's': return '7'; case 't': case 'u': case 'v': return '8'; case 'w': case 'x': case 'y': return '9'; case 'o': case 'q': case 'z': return '0'; default: return mychar; }
} } class Phone { string phoneNumber; public string PhoneNumber { get { return phoneNumber; } set { phoneNumber = value; } } int size; public int Size { get { return size; } set { size = value; } } string[] dics; public string[] Dics { get { return dics; } set { dics = value; } } List<string> solutions = new List<string>(); public List<string> Solutions { get { return solutions; } set { solutions = value; } } bool hasSolution; public bool HasSolution { get { return hasSolution; } set { hasSolution = value; } } } } Re: WA3--C#--Help! Posted by monsky 11 Oct 2016 17:46 If I understood your algorithm properly, you intent to get best result with sorting you dictionary by word length and trying words from longest to shortest, but it's not always true. For example, let's test contains words with lengths 5 3 2 1, and proper results are 5-2-1 and 3-5. Your algorithm will find the 5-2-1, and not 3-5. (It was my mistake too and I got WA3 as well.)))) |
|
|