PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: S. Manuj Nanthan
Preparer: Mradul Bhatnagar
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
718
PREREQUISITES:
None
PROBLEM:
Alice’s office is A kilometers and she takes X hours to reach it.
Bob’s office is B kilometers and he takes Y hours to reach it.
Who is driving faster?
EXPLANATION:
Alice’s speed is \frac{A}{X} and Bob’s speed is \frac{B}{Y}. Comparing these two numbers with an if
condition is enough to solve the problem.
I did this, why am I still getting WA?
Note that all four values given in the input are integers, but the speeds need not be. So, directly comparing the values as
if (a/x < b/y) {...}
will not work in languages such as C++ and Java, where /
denotes integer division when it operates on integers.
You can test your code on
1
3 3 3 2
and see if your output matches what you expect to see.
To resolve this, there are a couple of options:
- Convert all four values to doubles and do the comparison there, which is still unsafe but will work in this problem since the values of A, B, X, Y are small.
- The better option is to not use division at all. Note that \frac{A}{X} \lt \frac{B}{Y} if and only if A\cdot Y \lt B\cdot X, so you can instead compare the values of A\cdot Y and B\cdot X instead, which works purely with integers and is completely safe.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (C++)
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, x, b, y; cin >> a >> x >> b >> y;
if (a*y == b*x) cout << "Equal\n";
else if (a*y < b*x) cout << "Bob\n";
else cout << "Alice\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
a, b, x, y = map(int, input().split())
print('alice' if a*y > b*x else ('bob' if a*y < b*x else 'equal'))