God of Battle
InterviewTime limit1sMemory limit1024 MB
Given a budget N and two mercenary types with power A and B and costs PA and PB, find the counts x and y that maximize Ax+By within the budget.
- Level
Medium5 of 10
- Topics
- Greedy, Brute force, Math
- Solved
- No attempts yet
Problem
Gisung has never lost a battle. Mingyeong, who loses every battle, kept begging Gisung to share the secret to winning. Tired of the pestering, Gisung told Mingyeong his own formula for choosing the mercenaries who join a battle. Mingyeong hires mercenaries according to that formula.
According to Gisung's formula, if one tanker has combat power and one dealer has combat power , Mingyeong hires tankers and dealers so that is maximized.
Mingyeong has only won to spend on hiring, so the hiring is limited. If hiring one tanker costs and hiring one dealer costs , write a program that finds how many tankers and how many dealers Mingyeong should hire.
Input
The first line contains , the amount of money Mingyeong can spend on hiring mercenaries.
The second line contains , , , and , separated by spaces.
All input values are integers.
Output
Print the number of tankers and the number of dealers to hire, separated by a space.