ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1295. Crazy Notions

Bruteforce on C#
Posted by Leonid (SLenik) Andrievskiy 13 Jul 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);
public int Length
{
get
{
return value.Count;
}
}

private static void MoveForward(ref LinkedListNode<int> k)
{
k = k.Next;
}

public InfinumNumber()
{
}
public InfinumNumber(int value)
{
value /= Base;
if (value != 0)
{
value /= Base;
}
}
public static InfinumNumber operator +(InfinumNumber a, InfinumNumber b)
{
int modulo = 0;
int length = Math.Min(a.Length, b.Length);
InfinumNumber rezult = new InfinumNumber();
for (int k = 0; k < length; k++)
{
int current = i.Value + j.Value + modulo;
modulo = 1;
if (current > Base) current -= Base;
else modulo = 0;
i = i.Next;
j = j.Next;
}
if (length < b.Length) i = j;
while (i != null)
{
if (modulo > 0)
{
rezult.value.Last.Value += i.Value;
modulo = 0;
}
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;
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.SetOut(new StreamWriter(@"..\..\output.txt"));
#endif
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#
Posted by Petrenuk (NNSTU) 28 Sep 2011 03:12
F**** disgrace. What a code.
Mine has 10 lines and i spent bout 40 seconds to type it lol