Problem Link:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Soumyadeep Pal
Tester: Danny Mittal
Editorialist: Ritesh Gupta
DIFFICULTY:
Simple
PREREQUISITES:
Math
PROBLEM:
Alice and Bob are two friends. Initially, the skill levels of them are zero. They work on alternative days, i.e one of Alice and Bob works on the odd-numbered days (1, 3, 5, \dots) and the other works on the even-numbered days (2, 4, 6, \dots). The skill levels of Alice and Bob increase by A, B respectively on the days they work.
Determine if it is possible that the skill levels of Alice and Bob become exactly P, Q respectively on some day.
QUICK EXPLANATION:
As both Alice and Bob will get same A and B skill points for working on any day. So, they can achieve only multiple of A and B respectively at any day. Now, either their score will become P and Q on any odd day or even day. If their skill level become as given on even day then both works for same number of days which implies that P/A = Q/B else the person who start the work on odd day, will contribute one more day then other which implies that P/A = Q/B + 1 if Alice start working on odd day or P/A = Q/B - 1 if Bob start working on odd day .
EXPLANATION:
We can solve the problem with these observations :
- As each person will gain same amount of skill set after working for a day that means the skill set values achieved at any day should be multiple of their respective increase value (A in case of Alice and B in case of Bob).
- P should be the multiple of A or P\%A == 0
- Q should be the multiple of B or Q\%B == 0
- If their skill level become the desired ones on even day that means both of them worked for same amount of days irrespective of who started working first or mathematically P/A == Q/B
- If their skill level become the desired ones on odd day that means the person who started working first will be a day ahead compare to the other person.
- If Alice started working first then P/A == Q/B + 1
- If Bob started working first then P/A == Q/B - 1
TIME COMPLEXITY:
O(1) per testcase
CODE:
Setter (C++)
#include using namespace std; void solve(int tc) { int a, b, p, q; cin >> a >> b >> p >> q; if (p % a == 0 && q % b == 0 && abs(p / a - q / b) <= 1) { cout << "YES\n"; } else { cout <> t; for (int i = 1; i <= t; i++) solve(i); return 0; }
Tester (Kotlin)
import java.io.BufferedInputStream import kotlin.math.abs const val BILLION = 1000000000 fun main(omkar: Array) { val jin = FastScanner() repeat(jin.nextInt(1000)) { val a = jin.nextInt(BILLION, false) val b = jin.nextInt(BILLION, false) val p = jin.nextInt(BILLION, false) val q = jin.nextInt(BILLION) println(if (p % a == 0 && q % b == 0 && abs((p / a) - (q / b)) <= 1) "yEs" else "nO") } jin.endOfInput() } class InvalidInputException(message: String): Exception(message) class FastScanner { private val BS = 1 shl 16 private val NC = 0.toChar() private val buf = ByteArray(BS) private var bId = 0 private var size = 0 private var c = NC private var `in`: BufferedInputStream? = null private val validation: Boolean constructor(validation: Boolean) { this.validation = validation `in` = BufferedInputStream(System.`in`, BS) } constructor() : this(true) private val char: Char private get() { while (bId == size) { size = try { `in`!!.read(buf) } catch (e: Exception) { return NC } if (size == -1) return NC bId = 0 } return buf[bId++].toChar() } fun validationFail(message: String) { if (validation) { throw InvalidInputException(message) } } fun endOfInput() { if (char != NC) { validationFail("excessive input") } if (validation) { System.err.println("input validated") } } fun nextInt(from: Int, to: Int, endsLine: Boolean = true) = nextLong(from.toLong(), to.toLong(), endsLine).toInt() fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine) fun nextLong(endsLine: Boolean): Long { var neg = false c = char if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') { validationFail("found character other than digit, negative sign, space, and newline, character code = ${c.toInt()}") } if (c == '-') { neg = true c = char } var res = 0L while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0').toLong() c = char } if (endsLine) { if (c != '\n') { validationFail("found character other than newline, character code = ${c.toInt()}") } } else { if (c != ' ') { validationFail("found character other than space, character code = ${c.toInt()}") } } return if (neg) -res else res } fun nextLong(from: Long, to: Long, endsLine: Boolean = true): Long { val res = nextLong(endsLine) if (res !in from..to) { validationFail("$res not in range $from..$to") } return res } fun nextLong(to: Long, endsLine: Boolean = true) = nextLong(1L, to, endsLine) }
Editorialist (C++)
#include using namespace std; int main() { int t; cin >> t; while(t--) { int a,b,p,q; cin >> a >> b >> p >> q; if (p%a != 0 || q%b != 0) { cout << "NO\n"; } else if (p/a == q/b || p/a == q/b - 1 || p/a == q/b + 1) { cout << "YES\n"; } else { cout << "NO\n"; } } return 0; }