 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
Deltron Z
Expert Cheater
![]() Reputation: 1
Joined: 14 Jun 2009
Posts: 164
|
 Posted: Mon Apr 11, 2011 9:55 am Post subject: Google Code Jam |
 |
|
This is driving me crazy...
I've been practicing on problems from last years and so far they were all pretty easy and every code I wrote for the small input worked on the large input without any changes. but on the first problem from 2009, "All Your Base", which seems pretty easy, I get incorrect for my output. I tried everything, from manually checked the numbers to remove the last new-line and white-space characters...
My algorithm is simple:
An array of size 36 (0~9 + a~z) that contains the values of each symbol. since the number has to be represented in the smallest way possible and it cannot start with leading zeros, the first symbol is 1, the next is 0 and the rest are increasing, starting from 2. now that I have an array containing each symbol's value, simply convert from the known base between 2 to 36 (number has to be minimal, so it is the lowest base possible - number of different symbols) to base 10.
The decimal value is:
i = 0
Σ di * base^i (from left to right)
i -> length (of string)
As I said, works for small input... no idea what is the problem. limitations say the value will never exceed 10^18 < 2^63, so it fits in long.
My code:
| Code: | using System;
using System.IO;
namespace GoogleJam
{
class Program
{
static int CharToIndex(char c)
{
if (c >= '0' && c <= '9')
return (int)(c - '0');
else if (c >= 'a' && c <= 'z')
return (int)(c - 'a' + 10);
else
return -1;
}
static void AllYourBase(string filepath)
{
using (StreamWriter sw = new StreamWriter(filepath + ".out"))
{
using (StreamReader sr = new StreamReader(filepath + ".in"))
{
int n = int.Parse(sr.ReadLine());
int[] values = new int[36];
for (int c = 1; c <= n; c++)
{
for (int i = 0; i < values.Length; i++)
values[i] = -1;
string number = sr.ReadLine();
int val = 2; //also base
int index = 0;
values[CharToIndex(number[0])] = 1;
do
{
index++;
} while (index < number.Length && number[0] == number[index]);
if (index < number.Length)
{
values[CharToIndex(number[index])] = 0;
for (int i = index + 1; i < number.Length; i++)
{
if (values[CharToIndex(number[i])] == -1)
{
values[CharToIndex(number[i])] = val;
val++;
}
}
}
//val is also the minimum base possible
long sum = 0; //the value of number is:
//i = 0, sigma(number[i] * base^i), i -> length
for (int i = 0; i < number.Length; i++)
{
sum += values[CharToIndex(number[i])] * (long)Math.Pow(val, number.Length - i - 1);
}
Console.WriteLine("#{0}: {1} = {2} (base {3})", c, number, sum, val);
sw.WriteLine("Case #{0}: {1}", c, sum);
}
}
}
}
static void Main(string[] args)
{
DateTime time = DateTime.Now;
AllYourBase(@"C:\Google Jam\2009_1C_A-large-practice");
Console.WriteLine(DateTime.Now.Subtract(time));
}
}
} |
_________________
SharpDisassembler
"When I find my code in tons of trouble,
Friends and colleagues come to me...
Speaking words of wisdom:
Write in C."
#pragma message("Let there be byte!") |
|
| Back to top |
|
 |
jgoemat
Master Cheater
![]() Reputation: 23
Joined: 25 Sep 2011
Posts: 264
|
| Posted: Wed Dec 14, 2011 9:31 am Post subject: Not Enough Precision in double |
|
|
Math.Pow uses doubles which are 64 bit, but use 1 bit for sign and 11 bits for the exponent so you only really have 52 significant bits. Case #16 requires 53 significant bits for the first digit, 15^14. The double comes out to be 29192926025390624.0, but the real value should be 29192926025390625. You could use this code instead for summing:
| Code: | long sum2 = 0;
for (int i = 0; i < number.Length; i++)
{
sum2 = (sum2 * val) + values[CharToIndex(number[i])];
}
|
|
|
| Back to top |
|
|
atom0s
Moderator
 Reputation: 205
Joined: 25 Jan 2006
Posts: 8589
Location: 127.0.0.1
|
| Posted: Wed Dec 14, 2011 9:53 am Post subject: |
|
|
While your post is relevant to the topic jgoemat, please don't dig up old threads that aren't active anymore.
_________________
- Retired. |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
