Hi All,
I wrote the following solution to the POUR1 problem in the C#:
using System;
public class Test
{
public static int a, b, c;
public static int gcd( int x, int y )
{
if (y == 0)
return x;
return gcd(y, x % y);
}
public static int pour( int aa, int bb )
{
int steps = 0;
int in_a = 0;
int in_b = 0;
int amount = 0;
while (in_a != c && in_b != c)
{
if (in_a == 0)
{
in_a = aa;
steps++;
}
else if (in_b == bb)
{
in_b = 0;
steps++;
}
else
{
amount = Math.Min(in_a, bb - in_b);
in_a -= amount;
in_b += amount;
steps++;
}
}
return steps;
}
public static int compute()
{
if (c > a && c > b)
return -1;
if (c == 0)
return 0;
if (c % gcd(a, b) != 0)
return -1;
return Math.Min(pour(a, b), pour(b, a));
}
public static void Main( string[] args )
{
int t;
t = int.Parse(Console.ReadLine());
while (t > 0)
{
a = int.Parse(Console.ReadLine());
b = int.Parse(Console.ReadLine());
c = int.Parse(Console.ReadLine());
Console.WriteLine(Convert.ToString(compute()));
t--;
}
}
}
I tested that for several sets of data, and even wrote BFS version and compared results for all 0<=a,b,c<=20. Everything worked well, but the SPOJ was returning the WA to that solution.
After few days of looking for the root cause of the problem I gave up and rewritten that to the plain C:
#include <stdio.h>
int a, b, c;
int gcd( int x, int y )
{
if( y == 0 )
return x;
return gcd( y , x % y );
}
int pour( int aa, int bb )
{
int steps = 0;
int in_a = 0;
int in_b = 0;
int amount = 0;
while( in_a != c && in_b != c )
{
if( in_a == 0 )
{
in_a = aa;
steps++;
}
else if( in_b == bb )
{
in_b = 0;
steps++;
}
else
{
amount = in_a < bb - in_b ? in_a : bb - in_b;
in_a -= amount;
in_b += amount;
steps++;
}
}
return steps;
}
int compute()
{
int result0, result1;
if( c > a && c > b )
return -1;
if( c == 0 )
return 0;
if( c % gcd(a,b) != 0 )
return -1;
result0 = pour(a,b);
result1 = pour(b,a);
return result0 < result1 ? result0 : result1;
}
int main( int argc, char *argv[] )
{
int t;
scanf( "%d" , &t );
while( t > 0 )
{
scanf( "%d" , &a );
scanf( "%d" , &b );
scanf( "%d" , &c );
printf( "%d\n" , compute() );
t--;
}
}
Code is almost the same, the differences are dictated by the language. However, the C one got the AC immediately.
I am suspecting some strange behaviour of the C# compiler being used on SPOJ. Has anyone encountered similar situation? I am mainly resolving problems in Python with fallback to the C#, if there are performance issues. But the C# does not seem to be reliable to me any more...
Best regards,
--
Marcin Gajda