419. Hexagonal Walkaround

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

A hexagonal leftist tank is a very complicated piece of machinery. It lives on a hexagonal grid, moving from a cell to some of its adjacent cells each turn.

More specifically, each moment of time the tank is located in some cell (x,y) of the grid, heading in one of six directions (see picture for the definition of coordinate system and directions). In one turn, the tank can either move forward in the direction it is heading, or turn left one direction (i.e., increase the direction it is heading by one modulo six), and then move forward in the new direction the tank is heading. Moreover, it is forbidden to move more than b times in the same direction consecutively.

You need to put the tank into cell (x,y), heading in direction d2, given it is located in cell (0,0) initially, heading in direction d1. What is the minimal number of turns required to do that?

The input file contains five integer numbers x, y, d2, d1, b (-1012x, y ≤ 1012, 0 ≤ d1, d2 ≤ 5, 2 ≤ b ≤ 10).

Output one integer number — the minimal number of turns required to get the tank to the required position.

sample input
sample output
3 3 1 5 3

sample input
sample output
-1 -3 4 2 2

The second example is solved as follows (see next page):

Online Contester Team © 2002 - 2010. All rights reserved.