ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1002. Телефонные номера

WA3--C#--Help!
Послано roshan 30 авг 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!
Послано monsky 11 окт 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.))))