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

Обсуждение задачи 1295. Бред

Bruteforce on C#
Послано Leonid (SLenik) Andrievskiy 13 июл 2009 22:51
Can some body help me to optimize my C# solution? I have TL 10 (it works approximately 0.8s if N=30000).

PLEASE, DO NOT OFFER TO USE THE PERIOD OF THE IMPLEMENTED FUNCTION!

Here is my code:

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

#if (!ONLINE_JUDGE)
using System.IO;
#endif

namespace _295__acm.timus.ru_
{
    class InfinumNumber
    {
        public const int Base = 10000;
        public static InfinumNumber Zero = new InfinumNumber(0);
        public static InfinumNumber PlusOne = new InfinumNumber(1);
        private LinkedList<int> value;
        public int Length
        {
            get
            {
                return value.Count;
            }
        }

        private static void MoveForward(ref LinkedListNode<int> k)
        {
            if (k.Next == null) k.List.AddLast(0);
            k = k.Next;
        }

        public InfinumNumber()
        {
            value = new LinkedList<int>();
        }
        public InfinumNumber(int value)
        {
            this.value = new LinkedList<int>();
            this.value.AddLast(value % Base);
            value /= Base;
            if (value != 0)
            {
                this.value.AddLast(value % Base);
                value /= Base;
            }
            if (value != 0) this.value.AddLast(value);
        }
        public static InfinumNumber operator +(InfinumNumber a, InfinumNumber b)
        {
            int modulo = 0;
            int length = Math.Min(a.Length, b.Length);
            InfinumNumber rezult = new InfinumNumber();
            LinkedListNode<int> i = a.value.First;
            LinkedListNode<int> j = b.value.First;
            for (int k = 0; k < length; k++)
            {
                int current = i.Value + j.Value + modulo;
                modulo = 1;
                if (current > Base) current -= Base;
                else modulo = 0;
                rezult.value.AddLast(current);
                i = i.Next;
                j = j.Next;
            }
            if (modulo > 0) rezult.value.AddLast(modulo);
            if (length < b.Length) i = j;
            while (i != null)
            {
                if (modulo > 0)
                {
                    rezult.value.Last.Value += i.Value;
                    modulo = 0;
                }
                else rezult.value.AddLast(i.Value);
                i = i.Next;
            }
            return rezult;
        }
        public static InfinumNumber operator *(InfinumNumber a, InfinumNumber b)
        {
            int modulo = 0;
            InfinumNumber rezult = new InfinumNumber(0);
            LinkedListNode<int> i = a.value.First, j = b.value.First;
            LinkedListNode<int> k, k0 = rezult.value.First;
            for (i = b.value.First; i != null; i = i.Next)
            {
                k = k0;
                modulo = 0;
                for (j = a.value.First; j != null; j = j.Next)
                {
                    k.Value += j.Value * i.Value + modulo;
                    modulo = k.Value / Base;
                    k.Value %= Base;
                    MoveForward(ref k);
                }
                k.Value += modulo;
                MoveForward(ref k0);
            }
            while (rezult.Length > 1 && rezult.value.Last.Value == 0) rezult.value.RemoveLast();
            return rezult;
        }
        public int Zeros()
        {
            int results = 0;
            for (LinkedListNode<int> t = this.value.First; t != null; t = t.Next)
            {
                int value = t.Value;
                for(int i = 0; i < 4; i++)
                {
                    if (value % 10 == 0) results++;
                    else return results;
                    value /= 10;
                }
            }
            return results;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

#if (!ONLINE_JUDGE)
            Console.SetIn(new StreamReader(@"..\..\input.txt"));
            Console.SetOut(new StreamWriter(@"..\..\output.txt"));
#endif
            int n = int.Parse(Console.ReadLine());
            InfinumNumber pow2 = new InfinumNumber(1), pow3 = new InfinumNumber(1),
                t2 = new InfinumNumber(2), t3 = new InfinumNumber(3);

            for (int i = n; i > 0; i = (i >> 1))
            {
                if ((i & 1) == 1)
                {
                    pow2 *= t2;
                    pow3 *= t3;
                }
                t2 = t2 * t2;
                t3 = t3 * t3;
            }
            Console.WriteLine((pow2 * (pow2 + InfinumNumber.PlusOne) + InfinumNumber.PlusOne + pow3).Zeros());

#if (!ONLINE_JUDGE)
                Console.Out.Flush();
#endif
        }
    }
}
Re: Bruteforce on C#
Послано Petrenuk (NNSTU) 28 сен 2011 03:12
F**** disgrace. What a code.
Mine has 10 lines and i spent bout 40 seconds to type it lol