Problem Description

The A levels are coming near and Mr Panda is freaking out over trying to complete his last minute study schedules due to his lack of revision. While panickingly flipping through his Economics notes, he stumbled upon this chapter on Supply and Demnand.

In microeconomics, supply and demand is an economic model of price determination in a market. It concludes that in a competitive market, the unit price for a particular good will vary until it settles at a point where the quantity demanded by consumers (at current price) will equal the quantity supplied by producers (at current price), resulting in an economic equilibrium for price and quantity.

The four basic laws of supply and demand are:
  1. If demand increases and supply remains unchanged, a shortage occurs, leading to a higher equilibrium price.
  2. If demand decreases and supply remains unchanged, a surplus occurs, leading to a lower equilibrium price.
  3. If demand remains unchanged and supply increases, a surplus occurs, leading to a lower equilibrium price.
  4. If demand remains unchanged and supply decreases, a shortage occurs, leading to a higher equilibrium price.

Although it is normal to regard the quantity demanded and the quantity supplied as functions of the price of the good, the standard graphical representation, usually attributed to Alfred Marshall, has price on the vertical axis and quantity on the horizontal axis, the opposite of the standard convention for the representation of a mathematical function.

Your job is to code a program to calculate the equilibrium of a good given it's demand and supply functions within the market.

Implementation Details

You are not allowed to input or output to standard input or output in any of your functions when submitting to the judge. The grader will do that automatically for you (grader.cpp).

Your program will implement only 1 function, int getPrice(int P), which should return the equilibrium price given that it is in the range [0,P]. Note that there is no guarantee that the equilibrium price is an integer so the function is only required to return the price rounded up or down, both of which will be counted as correct.

Your program will also be allowed to call two functions as listed below.

long long supply(int P): Returns the quantity supplied of a good if it is set at price P

long long demand(int P): Returns the quantity demanded of a good if it is set at price P

The function will return -1 if called with a price outside the range [0,P]

There are template files provided under attachment, you are strongly advised to write your solution within the template files instead of creating new source files. The command to compile is g++ -O2 -o ssandd grader.cpp sandd.cpp. Alternatively, you may just run compile_cpp.sh which contains the compilation command. Please ask clarifications if in doubt.

Limits and Scoring

Subtask 1 (10%): 0 < P ≤ 1000, the supply and demand functions will each be limited to P calls

Subtask 2 (10%): 1000 < P ≤ 1000000, the supply and demand functions will each be limited to P calls

Subtask 3 (80%): 1000000 < P ≤ 1000000000, the supply and demand functions will each be limited to P calls and you score for this subtask is given by 80(1-(C^3)/P) where C is the maximum number of times your program calls the supply or demand function

Sample Input

10

Sample Output

5