Mock CCC '19 Contest 2 S4 - Tudor Walks Among the Goats

View as PDF

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Tudor is going for a walk!

In this scenario, Tudor has goats tied to fence posts at various locations with varying lengths of ropes. Tudor is going to go walking on an infinite line. If, at any point along the walk, a goat is able to reach Tudor, even at the maximal range of the rope, then the goat will run at Tudor. Tudor will then be able to check on the goat to make sure that it's in fine health.

The goats are rather territorial, so Tudor's initial assignments of rope lengths to goats ensures that two goats can never interact with each other, not even at a single point.

Compute the maximum number of goats that Tudor can check on given that he can choose what line to travel on.

Constraints

In tests worth 5 marks, .

Input Specification

The first line of input will contain a single positive integer, .

Each of the next lines will contain three space-separated floating point numbers specified to exactly two decimal places, , , and , indicating that goat is tied to a fence post at with a rope of length .

Output Specification

Output, on a single line, the maximum number of goats Tudor can visit.

Sample Input

3
0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00

Sample Output

2