JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Final Round
Problem: Tank

Problem Statement

    You control a tank and must hit a number of moving targets as quickly and efficiently as possible. The targets and tank exist on a 1000x1000 grid, where each location on the grid has an elevation. During each time step, you may either move to one of the 4 adjacent grid locations, or fire a round of artillery, or pass.



Your gunnery is spot on, and if it's possible to hit a target, you'll hit it for sure. However, some locations will be out of range. The base range of your artillery is 200. The actual range depends on the elevation difference. The range increases by 4 for every unit of elevation. Thus, you may hit a location if distance <= 200 + 4 * elevation difference (distance is Euclidean, elevation difference can be negative).



Your score for each test case will be the 100 times the number of targets divided by the number of turns it takes you to hit all of them. If you fail to hit all the targets after 10,000 turns, your score will be hit / 200, where hit is the number you hit. Your final score will simply be the average of your scores for the individual test cases.



The simulation is turn-based. On each turn you either move, shoot, or pass. Next some of the remaining targets move to new locations. Each target will have a speed associated with it, selected randomly in [0,1). The targets move in a sequence of roughly straight lines by executing the following algorithm 5 times per turn:
  while(current == target)
    target = new random point
  dx = target_x - current_x
  dy = target_y - current_y
  if(rand() < speed)
    if(rand()*(abs(dx)+abs(dy)) < abs(dx))
      move closer to target in x dimension
    else
      move closer to target in y dimension
There will be between 10 and 100 targets, inclusive, each starting at a random point on the map. At the beginning of the game, you will be given the elevation of every location on the map (the first element of map represents y=0, while the first number in each element represents x=0). On each turn until you have hit all the targets, the turn function will be called with the x and y coordinates of each target, as well as your coordinate (which starts at (0,0)). You should return a string "R", "L", "U", "D", or "P", for right (positive x), left, up (positive y), down or pass, respectively. If you wish to shoot instead, you should return a string giving the ID of the target to shoot, where the ID is an index into the x and y parameters. If the target is in range, you will hit it, and all subsequent calls to turn will list its location as (-1,-1). If it is out of range, your shot will have no effect. Similarly, trying to move off the board (less than 0 or more than 999) will be treated as passing.



The map will be generated with the following code
        for (i = 0; i < 20; i++) {
            x[i] = nextInt(1000);   //return an int in [0,999]
            y[i] = nextInt(1000);
            z[i] = nextInt(100);
            w[i] = nextInt(100) / 200.0 + 0.3;
            f[i] = nextInt(100) + 100;
        }
        for(i = 0; i < 1000 ;i++){
            for(j = 0; j < 1000 ;j++){
                double n = 0, d = 0;
                for(int k = 0; k < 20;k++){
                    double dist = hypot(i-x[k],j-y[k]); //gives length of vector
                    dist = pow(dist+f[k],-w[k]);
                    n += dist * z[k];
                    d += dist;
                }
                hh[i][j] = n/d;
                min = min(min,hh[i][j]);
                max = max(max,hh[i][j]);
            }
        }
        for(i = 0; i < 1000; i++){
            for(j = 0; j < 1000;j++){
                h[i][j] = (int)((hh[i][j]-min)*100/(max-min));
            }
        }
        //h is the final height data
The visualizer works much like those of the past. Your program should first read 1000 lines representing the map in the same format you'd receive it in init. You should then read an integer, N. One each turn, you should read x, then y, followed by N lines, each giving the coordinates of one target. The password for the visualizer is tank.
 

Definition

    
Class:Tank
Method:init
Parameters:String[], int
Returns:int
Method signature:int init(String[] s, int N)
 
Method:turn
Parameters:int, int, int[], int[]
Returns:String
Method signature:String turn(int x, int y, int[] tx, int[] ty)
(be sure your methods are public)
    
 

Notes

-The time limit is 60 seconds, and the memory limit is 1024M.
 

Examples

0)
    
N = 57
Seed = 10861885
1)
    
N = 45
Seed = 13295578
2)
    
N = 70
Seed = 38635893
3)
    
N = 88
Seed = 6952715
4)
    
N = 58
Seed = 26746734
5)
    
N = 59
Seed = 8837753
6)
    
N = 24
Seed = 37028398
7)
    
N = 53
Seed = 7926700
8)
    
N = 73
Seed = 22153526
9)
    
N = 79
Seed = 6936926

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.