High School Programming League Problems Archive

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 (x₀, y₀) with initial velocity [vx₀, vy₀] and initial mass M₀.

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 (x_k, y_k), the velocity is equal to [vx_k, vy_k] and the mass of the vehicle is equal to M_k. 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 m_b 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 M_k-m_b, the projectile mass equal to m_b and the projectile velocity equal to:

• [vx_k, vy_k-v_b] in the case of the N shot,
• [vx_k+v_b, vy_k] in the case of the E shot,
• [vx_k, vy_k+v_b] in the case of the S shot,
• [vx_k-v_b, vy_k] in the case of the W shot.

The maximum number of possible shots is bounded by the number of available projectiles: B.

Arena

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.

Input

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: M₀ (0<M₀<1000), v_b (0<v_b<1000), m_b (0<m_b), x₀ (-s<x₀<s), y₀ (0<y₀<h), vx₀ (-10≤vx₀≤10), vy₀ (-10≤vy₀≤10), and a positive integer B<100 (0<m_bB<M₀) describing the vehicle and its capabilities.

Output

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.

Example 1

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]

Example 2

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]

Scoring

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.

Input data

 
 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].

Please note

• 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.