Spoj: SCRAPER

Yet another Spoj-problem: SCRAPER. Short description of the problem (shorter than the official one): F (F?5·10?) floors in a scyscraper ([0,F[), E (E<100) elevators with a min-floor X?[0,F[ and an increment Y. Now you should decide if you can use the elevators to get from floor A to floor B. My solution (it took some time to fix all bugs, because I am out of practice): Two elevators ((X?, Y?) and (X?, Y?)) are “adjacent” if there is a common floor, i.e. {x ? [X?, F[ ? [X?, F[ | x ? X? (Y?) ? x ? X? (Y?)} ? ø. If we are able to compute the adjacency, we can simply use a depth-first-search to check if there is a path between A and B (identifying all elevators visiting a certain floor is trivial). How to check it? Without loss of generality X??X?. Let d := X? - X?. If the elevator 0 wants to reach a floor visited by elevator 1, the number of Y?-steps f has to comply with Y?·f ? d (Y?). We can compute a solution for f by using the extended Euclidean algorithm. It can solve the equation a·Y? + b·Y? = gcd(Y?, Y?) =: g, and there exists a solution for f iff g|d. If this is the case, we can conclude Y?/g·a ? 1 (Y?) ? Y?/g·a·d ? d, that looks like our previous equation, now we know that f ? a·d/g. We can perform a “plain” integer division, because, since g|d. For the computed f we want to know if there exists any n such that X? ? X?+Y?·f+n·lcm(Y?, Y?) < F (adding n·lcm(Y?, Y?) floors does not change anything). We can perform that quite simply by comparing the expression with X? for the biggest possible n (where the expression is smaller than F): X? ? F-1 - ((F-1 - (X?+Y?·f)) % lcm(Y?,Y?)). That's it. I used some caching and handled special cases for the extended Euclidean algorithm for optimisation, but that is not that interesting. Here you can get the source-code, but of course you should try to solve it yourself and you should not have even read this text!

Leave a Reply

XHTML: Use <blockquote cite="name"> for quotations, <pre lang="text    ∨ cpp-qt ∨ cpp ∨ bash ∨ other language"> for code, [latex] for formulas and <em> for em. Contact me if the comment does not get published, it may have accidentally been marked as spam.

Anti-Spam Quiz: