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

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

Running time of my C# algorithm
Послано dark_ai 30 сен 2009 01:05
My C# Algorithm, error on Test 5 "Time limit exceeded". Help me make it faster. My email dark4ai@gmail.com

using System;
using System.Collections.Generic;

namespace timus1002
{
    public class Word
    {
        public int wordscount = 0;
        public int[] strs;
    }
    class Program
    {
        public static Dictionary<char, char[]> rules = new Dictionary<char, char[]>(10);
        public static string[] strings = new string[16];
        static bool TestWord(string word, string number)
        {
            if (number.Length < word.Length)
                return false;

            for (int i = 0; i < word.Length; i++)
                if (Array.IndexOf<char>(rules[number[i]],word[i])==-1)
                    return false;
            return true;
        }
        static Word TestNumber(string number, string[] dictionary, int min, int[] stros)
        {
            Word[] words = new Word[dictionary.Length];
            int m = dictionary.Length + 1;
            int mi = -1;
            for (int i = 0; i < dictionary.Length;i++)
            {
                int[] resu = new int[stros.Length + 1];
                for (int f = 0; f < resu.Length - 1; f++)
                    resu[f] = stros[f];
                resu[resu.Length - 1] = i;
                if (TestWord(dictionary[i], number))
                {
                    if (dictionary[i].Length == number.Length)
                    {
                        Word result = new Word();
                        result.strs = resu;
                        result.wordscount = min + 1;
                        words[i] = result;
                    }
                    else
                    {
                        words[i] = TestNumber(number.Substring(dictionary[i].Length), dictionary, min + 1, resu);
                    }
                    if (words[i] != null && words[i].wordscount < m)
                    {
                        m = words[i].wordscount;
                        mi = i;
                    }
                }
            }
            if (mi >= 0)
                return words[mi];
            return null;
        }
        static void Main(string[] args)
        {
            rules.Add('0', new char[]{ 'o', 'q', 'z' });
            rules.Add('1', new char[]{ 'i', 'j' });
            rules.Add('2', new char[]{ 'a', 'b', 'c' });
            rules.Add('3', new char[]{ 'd', 'e', 'f' });
            rules.Add('4', new char[]{ 'g', 'h'});
            rules.Add('5', new char[]{ 'k', 'l'});
            rules.Add('6', new char[]{ 'm', 'n'});
            rules.Add('7', new char[]{ 'p', 'r', 's' });
            rules.Add('8', new char[]{ 't', 'u', 'v' });
            rules.Add('9', new char[]{ 'w', 'x', 'y' });
            string end;
            while (true)
            {
                end = Console.ReadLine();
                if (end.Length != 2 && end != "-1")
                {
                    int numbers = int.Parse(Console.ReadLine());
                    string[] dictionary = new string[numbers];
                    for (int i = 0; i < numbers; i++)
                        dictionary[i] = Console.ReadLine();
                    Word res = TestNumber(end, dictionary, 0, new int[0]);
                    if (res == null)
                        Console.WriteLine("No solution.");
                    else
                    {
                        string result = dictionary[res.strs[0]];
                        for(int k =1;k<res.strs.Length;k++)
                            result+=" "+dictionary[res.strs[k]];
                        Console.WriteLine(result);
                    }
                }
                else break;
            }
            Console.Read();
        }
    }
}
Re: Running time of my C# algorithm
Послано Oleg Strekalovsky aka OSt [Vologda SPU] 30 сен 2009 21:45
I think, it's not problem of C#. It's problem of your algorithm :)