|Submit||All submissions||Best solutions||Back to list|
HS12ICSL - Ice sliding race
Adam and his team are about to take part in an unusual competition. It will be a race of sliding vehicles propelled by jet force. During the race, the vehicles fire projectiles in order to steer, accelerate, or to slow down. Using brakes and other steering mechanisms is strictly forbidden.
Adam's team is working hard to prepare a perfect vehicle and you are the member responsible for designing and testing racing strategies.
To evaluate a race strategy the following simulation model has been created: The simulation proceeds in steps. At the beginning (step 0) the vehicle is placed at point (x0, y0) with initial velocity [vx0, vy0] and initial mass M0.
The coordinates and the velocity of the vehicle during the simulation depend on the coordinates, velocity and action taken in the previous step. The possible actions are to wait (w) or to shoot in one of the the four possible directions (NSWE).
Shooting and moving
Suppose, in the step k, the vehicle position is (xk, yk), the velocity is equal to [vxk, vyk] and the mass of the vehicle is equal to Mk.
After a wait action (w) - the vehicle moves in a straight line with constant speed (friction and other forces are negligible):
(xk+1, yk+1) = (xk+vxk, yk+vyk) [vxk+1, vyk+1] = [vxk, vyk] Mk+1 = Mk
Every shot action reduces the mass of the vehicle by the mass of the projectile mb and
it moves according to its previous velocity:
(xk+1, yk+1) = (xk+vxk, yk+vyk) Mk+1 = Mk-mb
The velocity reacts according to the law of conservation of the momentum: momentum of the vehicle in step k is equal to the momentum of the vehicle in step k+1 plus the momentum of the projectile. Take the mass of the vehicle equal to Mk-mb, the projectile mass equal to mb and the projectile velocity equal to:
- [vxk, vyk-vb] in the case of the N shot,
- [vxk+vb, vyk] in the case of the E shot,
- [vxk, vyk+vb] in the case of the S shot,
- [vxk-vb, vyk] in the case of the W shot.
The maximum number of possible shots is bounded by the number of available projectiles: B.
The arena is of rectangular shape, where the vertices are: (-s, 0), (s, 0), (-s, h), (s, h). The goal is to cross the gate: a line segment connecting (-g, 0) and (g, 0). Your vehicle must not cross the other borders of the arena. The size of the vehicle is negligible.
The first line contains the number of test cases t. Each of the following t lines contains: 3 integers describing the arena: 100 < s, h, g < 10000, g≤s, 7 numbers: M0 (0<M0<1000), vb (0<vb<1000), mb (0<mb), x0 (-s<x0<s), y0 (0<y0<h), vx0 (-10≤vx0≤10), vy0 (-10≤vy0≤10), and a positive integer B<100 (0<mbB<M0) describing the vehicle and its capabilities.
For each test case output the number k (k≤1000) of steps which could have led from the initial vehicle position to the gate and in the next line, the description of those steps (please consult the example below) or one word NO if you do not want to solve this particular test case.
Input: 1 500 1500 200 500.0 50.0 10.0 0.0 30.0 -5.0 0.0 40 Output: 9 SSSSSSwSw Score: 991 Vehicle's trace: (-5.0000, 30.0000) [-5.0000, -1.0204] (-10.0000, 28.9796) [-5.0000, -2.0621] (-15.0000, 26.9175) [-5.0000, -3.1259] (-20.0000, 23.7916) [-5.0000, -4.2129] (-25.0000, 19.5788) [-5.0000, -5.3240] (-30.0000, 14.2548) [-5.0000, -6.4603] (-35.0000, 7.7944) [-5.0000, -6.4603] (-40.0000, 1.3341) [-5.0000, -7.6231] (-45.0000, -6.2890) [-5.0000, -7.6231]
Input: 1 1000 1000 750 100.0 500.0 10.0 900.0 20.0 5.0 -5.0 9 Output: 8 NWEEESSS Score: 992 Vehicle's trace: (905.0000, 15.0000) : [5.0000, 50.5556] (910.0000, 65.5556) : [67.5000, 50.5556] (977.5000, 116.1111) : [-3.9286, 50.5556] (973.5714, 166.6667) : [-87.2619, 50.5556] (886.3095, 217.2222) : [-187.2619, 50.5556] (699.0476, 267.7778) : [-187.2619, -74.4444] (511.7857, 193.3333) : [-187.2619, -241.1111] (324.5238, -47.7778) : [-187.2619, -241.1111]
The score awarded to your program for a given test case is computed as 1000-k.
The score awarded for a given test set is computed as the sum of scores for individual test cases. The overall score of the program is the sum of scores obtained for correctly solved tests.
The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.
n t l h 1 4 2s H1, H3, H4 2 4 2s H2, H3 3 4 2s H2 4 40 5s H2, H4 5 40 5s H4 6 40 5s (some cases might be unsolvable) n - test set number t - the amount of test cases in the test set l - time limit h - additional hints, see the description below
H1 - your vehicle needs many S shots but a few (likely only 1) E or W shots to correct its trajectory.
H2 - B≤4 - there are very few shots available (maybe even only one).
H3 - 3g≥s - the gate is wide.
H4 - your vehicle's initial speed is [0, 0].
- All submitted solutions will be visible to all users and tested on full data sets.
- After the deadline datasets will be slightly modified and all solutions will be rejudged.
- Please do not submit more than 100 times to this problem (all submissions starting with the 101st will be ignored). Submissions sent before 2013-02-20 11:11:57 (last major bug removal in the judge program) will not be counted.
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET|
|Resource:||High School Programming League|