Connection Status:
Competition Arena > Symbolic

Symbolic

TCCC05 Semi 1 · 2005-01-10 · by dgoodman

TCCC05 Semi 1 · 2005-01-10 · by dgoodman · Advanced Math, Simple Search, Iteration
Class Name: Symbolic
Return Type: int
Method Name: compare
Arg Types: (string, vector<int>)
Problem Statement

Problem Statement

Let I_Zero denote the real interval from 0 to 1/3, including 0 but not including 1/3. Let I_One denote the real interval from 1/3 to 1 including both endpoints.

We have a dynamic system, in which real values are generated by the following rule: xt+1 = f(xt) where f is the function 

               f(x) =  3x        (for x in I_Zero) 
                      (3-3x)/2   (for x in I_One)
The trajectory of a value c is the sequence of real values that would be generated by the system starting with c. These would be c, f(c), f(f(c)), etc. The "itinerary" of c is defined to be the sequence of 0's and 1's indicating whether the corresponding trajectory values are in I_Zero or I_One.

For example, the trajectory of 1/2 is 1/2,3/4,3/8,15/16,3/32,9/32, ... so its itinerary is 1,1,1,1,0,0,...

Given a value and the itinerary of an unknown value c, we would like to determine whether the given value is less than or greater than c. Since an itinerary is an infinite sequence, we will be given only the first part of an itinerary, so it may be impossible to determine whether the given value is smaller or larger than c.

Create a class Symbolic that contains a method compare that is given value as a decimal String and a int[] itin (the first elements in the itinerary of the unknown c). The method returns -1, 0, or 1 depending on whether value is less than c, indeterminate, or greater than c.

Constraints

  • value will contain between 2 and 20 characters inclusive.
  • value will consist of a decimal point followed by digits '0'-'9'.
  • itin will contain between 1 and 50 elements inclusive.
  • Each element of itin will be 0 or 1.
Examples
0)
".5"
{1,1,1,1,0}
Returns: 0

The first elements of the itinerary of 0.5 match the values in itin, so we cannot determine whether 0.5 is less than, equal to, or greater than c.

1)
".300000"
{1,1,1,1,0}
Returns: -1

0.3 is less than 1/3 so it is in I_Zero. c is between 1/3 and 1.0 since its itinerary starts in I_One. So 0.3 is less than c.

2)
".6"
{1,1,0,1,0,0}
Returns: 1

The trajectory of .6 is .6,.6,.6,.6,... If c were greater than or equal to .6, then f(c) would be less than or equal to (3 - 3*.6)/2 = .6 and f( f(c) ) would be greater than or equal to .6 which contradicts the fact that the third element of itin is 0. Therefore, .6 must be greater than c.

3)
".713"
{0,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 1
4)
".12"
{0,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: -1
6)
".00"
{0,0,0,0,0}
Returns: 0

Indeterminate: value may either be less than or equal to c. (It cannot be greater than c since a number less than .0 has no itinerary.)

10)
".1111111111111111111"
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1}
Returns: 0

Be careful about the precision of your calculations.

Submissions are judged against all 62 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Symbolic with a public method int compare(string value, vector<int> itin) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous