JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 88
Problem: ViralInfection

Problem Statement

    

You are researching some new anti-viral drugs, and wish to determine the optimal way to apply the medicine in a tissue sample, so that the effects of the virus are minimized.



Initially, you are given the layout of the slide in String[] slide as a 2D array of cells, where each cell can be clean ('C'), dead ('X'), or infected with the virus ('V'). You are also given other parameters. int medStrength indicates the strength of the medication when it is first injected in a single cell. int killTime describes the number of units of time between a cell becoming infected and a cell dying. When a cell dies, the virus may spread to any of the four directly adjacent cells. Lastly, double spreadProb indicates the probability of each surrounding cell becoming infected. Note that the virus spread has no effect on cells that are already infected, already dead, or have a sufficient concentration of medicine.



Your code should call one of three methods during each unit of time to indicate what it would like to do:

  • addMed: Applies medication to one given cell on the slide. This increases the concentration of the medication in that cell by medStrength. Cell coordinates x and y are 0-based, and must be within the limits of the slide. Adding medication takes one unit of time.
  • observe: Returns the current layout of the cells on the slide, in the same format as at the start of the simulation. This will show the progression of the virus since the start. Note that this does not allow observation of the diffusion of the medication. Making the observation takes one unit of time, at the end of which the state of the slide will change and might differ from the observation.
  • waitTime: Lets units of time pass without taking any specific action (units must be between 1 and the number of units of time remaining before reaching the maximum simulation time)



As each unit of time passes, several things will happen:

  • Medication is applied, or an observation is made, if applicable.
  • Any viral-infected cells with a medication concentration of at least 1.0 become clean cells.
  • Any viral-infected cells that have been infected for killTime die, possibly spreading the virus to any of the four adjacent cells.
  • Medication diffuses between adjacent cells. The amount of diffusion is equal to 20% the difference in concentration between the two cells.



The simulation will run for at most 10000 units of time. Your solution is not allowed to perform actions after that time. After your solution returns, the simulation will continue to run until there are no longer any viral-infected cells remaining, or until 10000 units of time have elapsed from the start. The value returned from runSim() will be ignored.



If your method throws any errors, or calls addMed() or waitTime() with invalid parameters, or makes calls in excess of the maximum units of time, you will score a -1 for that test case.



Your raw score for a test case will be (HEALTHY_CELLS_REMAIN - MEDICINE_APPLICTIONS * 0.5) / SIM_TIME.

SIM_TIME is the total time it takes until all viruses are gone or MAX_TIME is reached. Any raw score less than 0 (except for an error as already described) will be treated as 0.



Your combined score for all test cases will be equal to the sum of (YOURS / BEST), scaled to 1,000,000. Thus, a combined score of 1,000,000 implies a solution that has the current best score on all test cases.

Diffusion Examples

Before:

0.00  0.00  0.00
0.00  5.00  0.00
0.00  0.00  0.00

After:

0.00  1.00  0.00
1.00  1.00  1.00
0.00  1.00  0.00

After another step:

0.40  0.60  0.40
0.60  1.00  0.60
0.40  0.60  0.40

And one more step:

0.48  0.60  0.48
0.60  0.68  0.60
0.48  0.60  0.48
 

Definition

    
Class:ViralInfection
Method:runSim
Parameters:String[], int, int, double
Returns:int
Method signature:int runSim(String[] slide, int medStrength, int killTime, double spreadProb)
(be sure your method is public)
 

Available Libraries

    
Class:Research
Method:addMed
Parameters:int, int
Returns:int
Sample Call:val = Research.addMed(x, y);
Method:observe
Parameters:
Returns:String[]
Sample Call:val = Research.observe();
Method:waitTime
Parameters:int
Returns:int
Sample Call:val = Research.waitTime(units);
    
 

Notes

-After test case generation, the random number generator is reseeded. Note also that, except for test cases 0..9, the test servers do not reseed the randomizer in the same manner as the visualizer.
-A visualizer is available for this contest, the manual can be found here.
 

Constraints

-Time limit is 60 seconds.
-Memory limit is 1GB.
-medStrength will be between 10 and 100, inclusive.
-killTime will be between 1 and 10, inclusive.
-spreadProb will be in the interval [0.25, 1.00).
-The height and width of the slide will be between 15 and 100, inclusive.
-The first five example cases have sizes which are specially determined.
 

Examples

0)
    
Med Strength = 15
Kill Time = 9
Spread Prob = 0.43040231175361443

CCCCCCCCCC
VCCCCCCCCC
VCCVCCCCCC
CCVCCCCCVC
CCCCCVCVCC
CCCCVVCCCC
CCCCCCCCCC
CCCCCCCVCC
CCCCCCCCCC
CCCCXCCCCC
1)
    
Med Strength = 14
Kill Time = 9
Spread Prob = 0.5575606086191512

CXCVCCCCCCCCCCV
CCCVCCCCCCCCCCC
CCCCCCCCCCCCXCC
CCCCCCCCCCCCCCC
CVCCCCCCCCCCCXC
CCCCCCCCVCCCCCC
CCCCCCCCCCVCCCX
CCCXCCCCCCCCVCC
XCCCVCCCCCCCCCC
VCCCCCCCCCCCCCC
CCVCXVCCCCCCCVX
VCXCCCCCCCCCCCC
CCXCXCCCCCCCVCC
CCCCCCVCXCCCCXC
CCCCCCCCCCCCCCX
2)
    
Med Strength = 15
Kill Time = 3
Spread Prob = 0.9260857180225408

CCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCC
XCCCCCCCCCCCCCCXCVCC
CCCCCCCVCXCCCCCCCCCC
CCCCCCCCCCCCCCCCCVCC
VCCCCCCCCCCCCCCCCCCX
CCCCCXCCCCCCCCCXCCCC
CCCCCCCCXCXCCCCCCCCX
CCCXCCCCCCCCCCCCCXCC
CCCCCCCCCCCCCCCCCCCV
CCCCXCCCCCCXCXCCCCCC
CCCCCCCCCCCCCXCCXCCC
CCCCCCCCCCCCXCCCCCCC
CCXCCCCCCCCXCCCCCCCC
CCXXCCXXCCCCCXXCXCCC
CCXCCCCCXCCCCCCCCCCC
CCCCCCVXCCCVCCXCCCCC
CCCCCCCVCCCCCCCXCCCC
CCXCVCXXCCCXCCCCCCCX
CCXCCCXCCXCCCCCCCCCC
3)
    
Med Strength = 15
Kill Time = 1
Spread Prob = 0.3032440260639485

CCCVCCCCCXCXCVCCVCCVCVCCC
XCCXCCVXCCCCXCCVCCCCCCVCC
CCVCVCCCXCCCCCXCCCCXVCCCC
CCCCCCCCCVXVXXCCCCXCCCCCC
CCCVCCCCCCCCCXCCCVCXCCCCC
CXCCCCCXCCXCVCCCVCCCCCCVC
CCCCCCXCCCCCCCVCCCCCCCCCC
CCCCCCCCVXCCCCXCCCCCCXCCX
CCVCVCCCCVCCCCCCCCCCCCCCC
CCCCCVXCCCCXCCCVCCCCCCCCC
CVCCCCCXCCCCCCCVCCCCXCCCC
VCCCCCCCCXCVCCCCXXCCVCCCX
CCCCCCCCCVCCCCCCVCVCCCCCC
CCCCCCCCCVXCCCCCVCCCCCCCC
CCCCVCCVCVCCCVCCCCXCCXXCV
CCCCCXCCCCCCCCCCCCCCCCVCV
CCCVCCCCCCCCCCCCCCCCCCCCV
CCCCCCCCCCCCCCCVCXCCCXCCC
CCCVCCCVVCCXCCCVCCXCCCCCC
CCCCCCXCCCCCCCCCCCCCCCCCC
CCVCCCCCCCCCCCCCVXVCXCXVC
CVCCXCCCCCXVXVVCCCXCXCCCC
CCCCCCCCCCCCCCCCCCXCCCVCC
CCCCCCXCCCCXCCCXCCCCCCCCC
CCCCCCCVXVCVVCXCCCCCCXCCC
4)
    
Med Strength = 13
Kill Time = 3
Spread Prob = 0.9390355103916326

CCVCCCCCCCCCCCCVCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCVCCCCCCCCCCCVCC
CCVCCCCXXCCCXCCCCCCCXCCCCCCCVC
CCCXVVVCCCCCVVCVCVCCCCCCCCCCCC
CCCCCCCCCCCCCXCCCCXCXCCCCCCCCC
CCCCCCCVVCCCXCCCCCCCCCCCCCCCCX
CCCCCCCCCCCCXCXCCCCCCCCCCCVCCX
CCCCCCCCCCCCCCXCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCXCVCCCCCCCVCCCCC
CCXCCCCCCCCCCCCCCCCCCVCCCCCCCC
CVCCCCCCVCCCCCVCCCCCCCCCCCCCCC
CCCVCCCCCCCCCCXCCCCCCCCCCXCCVC
CCCCCCCXCVCCCCCCCCCCCCCCCCCCCC
CVXXCCCVCCCCXVCCCCCCCCCCCCCCCC
CCCCCVCCCCCCCCCCCCCCCVCCVCCCCX
CCCCCCCXCCCCCCCCCCCCVCCCCCCCCC
CCCVXCVCCCCCCVCCVCXCCCCCCCCCCV
CCCCCCCCCCCCCCCCCCVCCCCCCCCCCC
CCCCVCCCVCCCCCVCXCCCCCCCCCCCCC
CCCXCVXCVCCCCCCXVCCCCCCVCVCCVC
VCCCCCCCCCCCCCCCVVCCCCCCCCCCCC
CCCCCCCCCCCCCCCCXCCCCCCCCCCVCC
VVCXCXCCCVCCCXCCCCXCCCCCCCCCCV
XCCCCCCCCCCCCCCCCCCCCCCCCCVCCC
CCCCCCCCCCCCCXCCCCCCXCCCCCCCCC
VCCXCCCCCCCCCCCCCCCCCXCCCCCCCC
CCCCCCCCCCCXCCCCCCCCCCCCCCCCCV
CCCCCXCCCCVCCCCCCCCCCXCCCCCVCC
CCCCCCCCCXCCCCCVCCCCCCCXCCCCCC
CCVCCCCCCCVXCCCCCCCCCCCCVCCCCC
5)
    
Med Strength = 12
Kill Time = 3
Spread Prob = 0.3161938072571694

CCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCC
CCCXCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCC
CCCCCCXCCCXCCCCCCCCVCCCCXCCCCXCCCCCVCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXC
CVCCCCCCCCCCCCCCCCCCCVCCCVCCCCCCCCCCCCCCCVCC
CCCCXCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCVVCC
CCCCCCCCCCCCCCCCCXCCCCCCCCCCXCCCCCCCCCCCCCCC
VCCXCCCCCCCCCCCXCCCCCCCCCCCCCCCVCVVCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCVCCCCCCC
CXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCXCCCCC
CCCCCXCCVCCCXCCCCCCVVCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCVC
CCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCXCCCC
VVCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCVCCCC
CCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCVCCCCCCCCCCXCCCCCCCXCCXCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCC
CCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCXXC
CCCCCCCCCCCCCXCCCXCCCCCCCCCCXVCVCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCVCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCC
CCCCCCCCCCCCCCCCXCCCCCCCVCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCXCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
6)
    
Med Strength = 14
Kill Time = 7
Spread Prob = 0.6847189054846881

CCCCCCCCCCXCCCCCCCCCCCCCCCCCXCCCCVCCXCCVCCCCCCCCXCCCCCCV
XCCCCCCCCCCCVCCCVCCCCCCCCCCCCCCXCCCCCCCCCCCCVCCXCCCXCCCC
CCCCCCCCCVCCCCCCCXCCCCCCCVCCCCCCCCCCVCCCCCCCCCCCVCCCCCCC
CCCVCCCCCCCCCCCCXCCCCXCVCCCVCCCCVCCCCCCCCCCVCCCCVCCCCCCC
VCCCCCCXCCCCCCCCCCCCCCCCVCCVCXCCCCXCCXCCCXCCCCCCXCCCCCCC
CCCCCCCCCCCCCCCCCCCCCXVVCVCCCVCCCCCCCCCCVCCCCCCCCCCCCCCC
CCCXCXCVCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCXCCCCCCCC
CCCCCCCCCCCCCCCCVCCCCXCCCCCCXCCVCVCCCCCVCCCCCCCCCCCXCCCC
CXXCCCCCCCXCVCCCCVCCCVCCCVCCCCCCCXVVCCCCCCCCCVCCCCVCCCCC
CCCCCCCCCCCCXVXCCCCCCCVCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCVCCCCCCXCCCCVCCVCXCCCCXCCCCCCCCCCCCXCCCXCXCCCCCCCCCCCC
XCCCCCVCCCCCCCCCCVCVCCCXCCCCCCCCCCCVCCCCXCCCXCCVCCCCCCCC
CCCCCCCCCCCCCCCCCCCVCXCXCCCVCCCCCCCCCCCCCCCCCCCXCCCCVVCC
XCCVCXCXCCCCCCCCCCCCCCCCCCCCVCCCXCCCCCCCCCXCXCCCVCCCCCCC
CCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCXCCCCC
CCXCCCVCCCCCCCCCVCCCCCCCCCXVCCCVXCCCCCCCCXCCCXCCCCVCCCCC
XXCVCCCCCCCCCCCCXXVCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCXCCCCCC
CCCCCCXCXCCVCCCCCCCXCCCCCCXCCCCCCVCCVCCCCCVCCCCCCCCCCCCC
CCCVCVCCCCVCCCCCXCCXCCCCCCCCXCCCCCCCCCCCCCCCXCCCCCCCCCVC
CXCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCC
CVCCCCCCCCCXCCCCVCCCCCCCCVCCXCCCVCCCCCCCCCVCCXCCCCCCXCCC
CCCXCCCCCCCXCCXCCCCVCCCCCCCCCCCCCVCCCCCCCCCCCCVCXCVCCCCC
CCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCC
CCCCCCCCCCVVCCCCVCCCCCCCCCCCCCCCCCCCCCCVXXCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCXXCCCVCCCXCCCCCCCCCCCCCCXCXXCCCCC
CXCXCVCCCCCCCCCCCCCCCCCCXCVCCCCVCCCCCCCCCCCCCCCVCCCCCCCV
CXCCCCCCCXCXCCCCXCCCCCCCCCCCXCCCCCCCCCCCVCCCCCCCCXCCVCCC
XCXCCCCCVCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCVCXCC
CCCCCCXCCCCCVCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCVCCCCCCCXCCXCXCCCCCCCCCCCCVCCCCCCVCCCCCCCVCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCXXCCCCCCCCCCCCCVCCCCCXCCCXCCCVCCCCCCC
CCCCCCCCCCCCVCCXVCCVXVCCVCCCCCCCCCCCCVXCCCCCXXCCCXCVCCCC
CCCXCVCCCXCCCCCVVCCCCCCVCCCCCCCCCCCCCCXCCVCCCCCCCCCCCCCC
CCCCCCVCCCCCXCVCCCCCCCCCCCCCVCCCXCCCCCCCCCCCCCCCCCCCCXCC
CCCCCCCCXCCCCCCCCCCCCXCVCCCCCCCCCCCCCCCCCCCCCCCCVCCXCCCC
CCCCCCCCXCCCCVCCCCCCCCCCCCCVCCCCCCCCCXCCCCCCCXCCCCCCCXCC
CXCXCCCCCCCCCCCCCCCCXCCCCCCCCCCCXCVCCCCCCCCCCCCCCCCCXVCC
CCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCXCCCCVCCCCCCCCCCCC
CCCCXCCCCCCCCVCVVCCCCCXCCCCCCCCCCCCCCCCCXCCCCCCXCCVCVCCC
CXCCCCCCCCXCCCCCCVCCCCCCCCCCCCXCXCCVCCCCVCCCCCCCCCCCCCCC
CCCCCXCVXCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCVCCCCCCCC
CCXCCCCCCVCCCCCCCCCCCXCCVCCCCVCCCCCCCCCCVVCCCCCCCCCCCCXV
CCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVC
CCCCCCCCCCCCCCCCCCCCCCCXCCCCVCCCCCCCCCCVCCCXCCCCCCCCCCXC
7)
    
Med Strength = 13
Kill Time = 5
Spread Prob = 0.8118772023502249

CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCC
CCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCVCCCCXCCCCC
CXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCVCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCXCCCCCCCCXCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCV
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVXCCCCCC
CCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCC
CCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CXCCCCCCCCCCVCCCCCCCVCCCCCCCCCCCVCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCC
CCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCVCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCXCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCXVCCCCXCCCCCCCCCCCCXCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCC
CCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
XCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCV
CCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCC
CCCCCCVCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCC
CXCCXCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
VCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCVCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCCCCXCCCCC
CCCCCVVCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCXCCCCCCCCCCCCCCCCCCCCVXCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCXCCCVCCCCCCCCCVCXCCCCXCCCCCCXC
CCCCCCXCXCCCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCXXCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCXCCCCCCXCCCXCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCCXCCCCCCCCCCXCCCCC
VCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCVCCCCCXC
CCCVCCCXCCCCCCCCCCCCCCCCCCCXCCCVCCCCCCCCCCCCCCCCC
CCCCXCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCXCCCCCCCC
VCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCXC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCXCCCCCXCCCCCCCCCCCCCCC
CCCCCCCCXCCCCCCCCCCCCCCCCCCCVCCCCCCCCCCCCCCCCCCCC
8)
    
Med Strength = 11
Kill Time = 7
Spread Prob = 0.6976686866779089

CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCVCCCCCCCCCCCCCC
CCCCCVCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCVCC
CCCCCCCCCCCVCCCCCCCCCCC
CCCCCCCCCCCCCCCCCVCCCVC
CCCCCCCCCCCCCCCCXCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCVCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCXCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCVCCCCCCCCCCCVC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCXCCCCCCCCCCCCCC
CCCCCVCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCC
9)
    
Med Strength = 10
Kill Time = 7
Spread Prob = 0.8248269947193166

CXCCXCCCCCCCCCCCCCCCCCCC
VCCCCCVVCXCCCCCCCCCCCCCC
CCVXCCCCCVCXCCCVCCCCXCXC
VCCVCCCCCCCCCCCCXCCXCCCC
CCCVCCCCCCXXCCXCCCCCVCCC
XCCCCCCCCCCCCXCCXCCCCCCC
VCCCCVCCXCCXCCCXCCCCCCCC
VCCCCCCCCCCCCXCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCVCCXX
CCCCCCVCCCVXCCCCCCCCXCCC
CCXXCCCCCCCCCCCCCCCXCCCC
VCCCCVCCCXCCCCCCCVCCCCXC
CCXCCCCCCCXCCCCCCCCCCCCC
CCCCCCCCCXCCCCCCCCCCCCCC
VCXCCCVCCCCCCCCCCVCCXCCC
CCVCCCCCCCCVCCCCCCCCCCCC
CCCCCCCCCCVCCCCCCCCXCVCC
CCCCCCCCCXCCCCCCCCXCCCCC
CCCXCCCCCCVVCCCCCCCCCCCC
CCCVCCCCCCCCVCCCCCCCCCCC
CCCCCCCCCCCCXCCCCCCCCCCC
CXCCCCCVCCCCCCCCCCCCCCCC
CCXCCCXCCCCCCCCCVCCCCCCC
CXXCCCCVCCCCCCCCCCCCCCCX
CXCCCCCCCCCCCCCXCCCCCCCC
CCCCCXCCCCXCCCCCCCCCCCXC
CXCCCCCCCCCCCXCCCCCCXCCC
VCCCCVCCCCCCXCCCXCCCCCCC
CCCCVCCCCCVCCCCCCCXCCVCX
CXCCCXCCCCCCVCCCVCCCCCCC
XCCCCCCCCCXXCCCCCCCCCCCC
XCCXCCVCCCCCCCCCCCCCCCCV
CXCCCCCCCCCVVCCCCCVCCCXC
VCXCCCCCCCCCCCCCCCCCCCCC
CCXCCCVCCCCXCXCCCCCCCCCV
CCCCCCCCCCCCCVCCCCCCCCCC
CCCCCCCXVCCCCCVCCCCCXCXC
CCCCCCCCCCCCCCCCCXXCCCCV
CCXCCCCCCCCCCCCCCCCCCCCC
CXCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCVCCCCCCCCCVCCCCCX
CCCVCCCCCCCVCCCCVCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCX
CCXCCCCCCCCCCCCCCCCCCXCC
CCCCCCCCCCVCCXCCCVCXCCCC
CXCCCCXXCCCCCCCVCCCCXCCC
CCXCCXCXCCCCCCCCCCCCCCCC
CCCCCCCCCCVCCXCCCCCCCCCC
CVCCCCCCCCCVCXCCCCCCCCCC
CCCCCCCCCXCCCCCCCCVCCCCC
CCCCCCCCCCCXCCCCCCCCCCCC
CCCXCCCCCCCCCCCCCCCCCCCC
CCXCCCXCCCCCCCCCCCCCXCCC
CCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCXCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCC
VCXCCXXCVCCCCCCCCCCCVCCC
CXCCCCCCXVCCCCCCCXCCVCCC
CXCVCCCCCCCCVVCCCCCCCCCC
XCCCCCCCCCCCCCCCCCCCCCCX
CCCCCCCCCCCCCCXCCCCCXCVC
CXCVCCCCCCCCCCCCCCCCCCXC
CCCCCVXCVCCCCCCCCCCCCCCC
CCCCCCCCXCCCCCXCXCCCCCCC
CCXCCXCCCCCCXCCCCCCCXCCC
CCCXCCXCCCCCCXCXCCCCCCCC
XCCCXCCCCCCXCCCCCCCCCCCC
CCXCCCCCCCCCCCCCCCCCCXCC
CCCCCCCCCCCCCCCCCCXXCCCC
CCCCCXCCCCCCCCCCCXCCXCVC
CCXXCCCVCCCCVXCXCCCCCCCC
CCCCCCCCCCXCCCCCCCCCCCCC
CCXCXCCCCCCCXCVCCCCXCCCC
XCCCCCCCCCCCVCCCCCCCCCXC
CCCCCCCCCCCCCCCCCCVVCCCC
CCCCCCCVXCCCCCCXXCCCCCCC
CCVCCCVCCVCCCCXCCVCCCXCC
CCCXCCCVCCCCXXCCCCCCCCCC
CCCCCCCCCCCCCCVCCXCCCCCC
CCCCCCCCXCCCCCCCVCCCCCCC
CCCCXVCCCCCXCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCC

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.