All Tracks Algorithms Searching Ternary Search Problem

Download file
Tag(s):

Algorithms, Easy-Medium

Problem
Editorial
Analytics

Hasan wants to download a file from the internet, the file size is S MB, the internet speed available for Hasan is not fixed, it can be changed by time.

Hasan knows a list of times when the internet speed will be changed and the new speed for each time. more specifically Hasan has two arrays for length N which means:

starting from time T0 the internet speed is D0 MB per unit time. and starting from T1 the internet speed is D1 MB per unit time. and so on

it is provided that T0=0

Hasan wants the download duration be minimum possible (i.e. duration between starting of download and the end of download be minimum), note that Hasan can choose when to start the download but once it started it cannot be paused, it will continue until the end. Help Hasan by telling him what is the minimum possible duration that he can Achieve.

Input:

First line contains two integers N and S.

the following N lines, each contains two integers Ti and Di

Output:

Output a irreducible fraction,donating the minimum duration required to download the file if starting time is chosen optimally, in this format: a/b

Constraints:

  • 1 ≤ N ≤ 100,000
  • 1 ≤ Di, S ≤ 1,000,000
  • 0 ≤ Ti ≤ 1,000,000
  • T0=0 and all values of T are strictly increasing
SAMPLE INPUT
3 8
0 1
3 2
5 1
SAMPLE OUTPUT
6/1
Explanation

one optimal way is to start the download at T=0

Time Limit: 1.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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications