All Tracks Algorithms Searching Linear Search Problem

Counting Frog Paths
/

Algorithms, Linear search, Searching algorithm

Problem
Editorial
Analytics

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: \(X\)\(Y\)\(s\), and \(T\).

Output Format:

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

Constraints:

\(0 \le X,Y \le 100\)

\(1 \le s \le 100\)

\(0 \le T \le 400\)

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

SAMPLE INPUT
2 2 3 6
SAMPLE OUTPUT
6
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?