Jedi versus Sith
InterviewTime limit2sMemory limit1024 MB
Given Jedi and Sith abilities that grow linearly each day, find the first day when every Jedi ability is at least the matching Sith ability, or report that it never happens.
- Level
Easy3 of 10
- Topics
- Math, Brute force
- Solved
- No attempts yet
Problem
The dark side clouds everything. Impossible to see the future is.
Master Yoda
A Jedi and a Sith are stranded on an abandoned planet. Each of them knows the same number of Force abilities. Day and night, the Jedi and the Sith fight. Over time, each of them improves their abilities. Master Yoda watches the battle from the side. He knows the moment when the Jedi will become no worse than the Sith, the closest such moment. Can you sense the disturbance in the Force and answer this question?
Each Force ability is an integer. Both warriors have abilities. At the start, the Jedi's abilities are and the Sith's abilities are ().
During the battle, the Jedi and the Sith improve their abilities. The Jedi's -th ability grows by each day of battle. The Sith's -th ability grows by each day.
One fighter is no worse than the other if every one of their abilities is at least as large as the corresponding ability of the opponent.
Write a program that finds the first day when the Jedi is no worse than the Sith. Days are numbered starting from zero.
Input
The first line contains one integer (), the number of abilities available to the Jedi and the Sith. The second line contains integers , the Jedi's initial abilities. The third line contains integers , the Jedi's daily growth for each ability. The fourth line contains integers , the Sith's initial abilities. The fifth line contains integers , the Sith's daily growth for each ability. All numbers in the input are non-negative and do not exceed .
Output
Print one integer, the number of the first day when the Jedi is no worse than the Sith. If such a day never comes, print Strong is dark side of the force.