problem statement
Divide and Conquer, like binary search
In this problem You have a number a/b that want to construct it as stated in the problem description.
In each step you have to decide whether go left or go right? So you compare a/b with your current number which is (s1+t1)/(s2+t2) and decide to go right or left and when you arrive in a level that you've found the number, write the string that you've constructed.
Initially s1=0, t1=1 and s2=1, t2=0.
I have a function which takes ( s1, s2, a, b, t1, t2 ) and Divides and Conquers. :-D
if( b*(s1+t1) < a*(s2+t2) ) D_and_C( s1+t1, s2+t2, a, b, t1, t2 ), output += 'R';
else D_and_C( s1, s2, a, b, t1+s1, t2+s2 ), output += 'L';
if( a==s1+t1 && b==s2+t2 ) print output;
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Sunday, December 12, 2010
Subscribe to:
Post Comments (Atom)
USACO - Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
-
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment