Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

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.

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.

A sample arena

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

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 - 3gs - 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.

Added by:kuszi
Date:2013-02-02
Time limit:2s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 ASM64 BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.