All Tracks Algorithms Searching Linear Search Problem

Counting Frog Paths
Tag(s):

Algorithms, Easy, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #2

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?