Counting Frog Paths

3.7

96 votes
Algorithms, Easy, Searching
Problem

There is a frog initially placed at the origin of the coordinate plane. In exactly 1 second, the frog can either move up 1 unit, move right 1 unit, or stay still. In other words, from position (x,y), the frog can spend 1 second to move to:

  • (x+1,y)
  • (x,y+1)
  • (x,y)

After T seconds, a villager who sees the frog reports that the frog lies on or inside a square of side-length s with coordinates (X,Y), (X+s,Y), (X,Y+s), (X+s,Y+s). Calculate how many points with integer coordinates on or inside this square could be the frog's position after exactly T seconds

Input Format:

The first and only line of input contains four space-separated integers: XYs, and T.

Output Format:

Print the number of points with integer coordinates that could be the frog's position after T seconds.

Constraints:

0X,Y100

1s100

0T400

Note that the Expected Output Feature for Custom Invocation is not supported for this contest. 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The points shown are the points on or in the specified square, and those that are red are the points that the frog could be at after 6 seconds.

Editor Image

?