ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1200. Horns and Hoofs

3 algorithms for you !
Posted by Phan Hoài Nam (Harvey Nash) 4 Apr 2011 13:39

1) Slow algorithm O(K*(K+1)/2) : brute force. AC : 0.2 !
-> Find the profit with each number of horn and hoof (horn + hoof <= k).

2) Fast algorithm O(K*2) : caching the optimal number of horns and hoof. AC : 0.031 !
Find :
   +     The optimal number of horns <= k (A)
   +     The optimal number of hoof <= k - num of horns (B)
=>    result = A + B;

2) More Fast algorithm O(K) : caching the optimal number of horn or hoof. AC : 0.031 !
Caching the number of hoof.
-> For each number of horn
   + The optimal number of hoof = 0 ... k - optimal num of horn.
Re: 3 algorithms for you !
Posted by waterlink 27 Aug 2011 20:51
first algorithm could be optimized to AC in 0.046 :)