[help] Modular Multiplication and Maximum

Revision en1, by LaKsHiTh_, 2020-08-10 21:35:08

Today i tried to solve IOI 2015 horses problem. I observed that maximum profit can be gained by selling all horses on the same year. Obvious bruteforce would be to check every year.

Here is my solution:

Spoiler

But we have to keep the maximum profit. It is given that the answer could be very large therefore output it modulo 1e9+7; Because of the constraints above code works for subtask 1.

For remaining subtasks it won't. For keeping MAX i thought of maintaining a pair in the form of {n/ 1e9+7 , n% 1e9+7}. I think it could work.

But What if h exceeds integer bounds. we can't keep it modulo 1e9+7 because then h*y[i] will be wrong. How do i keep h such that it won't exceed integer bounds AND it won't give a wrong answer for h*y[i].

Thank you for your time

Tags #ioi, #modular arithmetic, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LaKsHiTh_ 2020-08-10 21:35:08 1081 Initial revision (published)