ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1002. Phone Numbers

WA3--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.))))