Algorithm


Problem Name: beecrowd | 2823

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2823

Eearliest Deadline First

By Emilio Wuerges, UFFS BR Brazil

Timelimit: 1

Your job for this problem is to check if it is possible to schedule a set of periodic tasks under real-time constraints.

A real-time task is defined by two numbers. The first number is the computational cost of the task. It is the computational cost of each complete run of the task. The second number is the period of the process. In other words, the process restarts again after each period.

The task set will be scheduled using the EDF algorithm (Earliest Deadline First). It is known that EDF is optimal. This means that if a set of tasks cannot be scheduled by EDF, there isn't another algorithm that can schedule it.

The operating system that will run these tasks runs on a single core machine. The tasks are preemptable. That is, a task can take the place of another task during its run, if required.

Consider that the cost of switching tasks is 0.

Input

The first line of the input has a value 

, which states the number of processes under schedule.

Every N following line represents a process, and has 2 values

and

, that represent the computational cost and the period of each process, respectively.

Output

The output consists of a single line, with the string OK or the string FAIL, if the scheduling is possible or not, respectively.

 
Input Samples Output Samples

2
3 5
2 5

OK

 

4
1 5
4 9
5 15
2 45

FAIL

 

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const { readFileSync } = require("node:fs")
const [[N], ...input] = readFileSync("/dev/stdin", "utf8")
	.split("\n", 10 + 1)
	.map((line) => line.split(" ", 2).map(value => Number.parseInt(value, 10)))

console.log(
	input.splice(0, N).reduce((total, [C, P]) => total + (C / P), 0) <= 1
		? "OK"
		: "FAIL"
)

Copy The Code & Try With Live Editor

Input

x
+
cmd
2 3 5 2 5
Advertisements

Demonstration


Previous
#2813 Beecrowd Online Judge Solution 2813 Avoiding Rain Solution in C, C++, Java, Js and Python
Next
#2826 Beecrowd Online Judge Solution 2826 Lexical Solution in C, C++, Java, Js and Python