### Problem Statement

After years of research and development, your firm has developed a new product; one so fantasic that everyone will have to have one once they realize how great it is. Unfortunately for you, a competing company is also bringing a similar product to market. There is no reason for anyone to have both your product and your competitor's and market research suggests that people slightly prefer your competitor's product, so you will need to out-manuever them if you want to be successful.

Lucky for you, your competitor thinks their product is so amazing that they don't need to advertise. If you play your cards right, you may be able to turn a handy profit yet.

In this problem, you need to dynamically determine where to locate ads to maximize your profit. Each person will be located at a point in two dimensions. A simulation will then occur over a number of time steps. At the beginning of each time step, you may place advertisements at particular locations, which will have an effect for that timestep only. Each person will be influenced by three factors: the prior preference for your competitor's product, the influence of your advertising, and the influence of other people who have already purchased one product or the other.

The initial locations of the N people will be chosen from K normal distributions, each with a weight si chosen as r2, where r is a uniform random variable in (0,1). Each distribution will have independently chosen standard deviations in the x and y directions from the range (200,1200), along with means chosen independently in (0,10000) for each coordinate. A person will be chosen from distribution i with probability proportional to si.

You will first be given the locations of all the people in the simulation, along with some of the parameters of the simulation, and you should return an int (which will be ignored). The update method will then be called repeatedly, telling you which people bought which products. Element i of index gives the 0-based index into x and y, and element i of product tells which one they purchased (1 for your's, -1 for your competitor's). You should then return your advertising scheme for the next time step. Each element of the returned String[]'s should be formatted as "<x> <y>". The first time the update function is called, the arrays will have size 0, as no one has bought either product before the start of the simulation.

For each ad you place in each timestep, a cost \$adCost will be incurred. For each person that buys your product, you will make a profit of \$1. Your goal, naturally, is to maximize your overall profit. Your overall score will simply be the average of you profit on all the test cases.

### Definition

 Class: Advertising Method: update Parameters: int[], int[] Returns: String[] Method signature: String[] update(int[] index, int[] product) Method: init Parameters: double, double, double[], double[] Returns: int Method signature: int init(double competitor, double adCost, double[] x, double[] y) (be sure your methods are public)

### Notes

-If no one buys any product during one step of the simulation, the simulation will be rerun for that timestep, until at least one person purchases a product.
-Negative scores will be increased to 0.
-If you place more than N/adCost ads, the simulation will terminate, and you will receive a 0.
-While you can test the examples in the visualizer by entering the seeds 1..10, you may also download the locations of the people from http://www.topcoder.com/contest/problem/Advertising/ex0, http://www.topcoder.com/contest/problem/Advertising/ex1 ...
-The time limit is 60 seconds, and the memory limit is 1024MB.

### Constraints

-All parameters except N and K are chosen as real numbers.
-competitor will be chosen uniformly at random in (-2,-0.2)
-adCost will be chosen uniformly at random in (1,10)
-K will be chosen uniformly at random in [1,10]
-N will be chosen uniformly at random in [1000,10000]
-C will be chosen uniformly at random in (1000,10000)
-D will be chosen uniformly at random in (10000,100000)

### Examples

0)

 `"1"`
```Returns:
"N = 7391
K = 9
competitor = -1.3996769602268109
C = 6301.356583692691
D = 45932.296033727725
"```
1)

 `"2"`
```Returns:
"N = 5472
K = 9
competitor = -1.0045314816459034
C = 4963.193236302646
D = 12305.219227908448
"```
2)

 `"3"`
```Returns:
"N = 2957
K = 2
competitor = -1.0124084785466487
C = 8352.767238144268
D = 20771.48561706445
"```
3)

 `"4"`
```Returns:
"N = 1919
K = 4
competitor = -0.9458449941876446
C = 8844.189389597545
D = 25647.04548673069
"```
4)

 `"5"`
```Returns:
"N = 5140
K = 1
competitor = -0.5652464571554352
C = 4899.988907012099
D = 14373.876861986962
"```
5)

 `"6"`
```Returns:
"N = 2405
K = 7
competitor = -1.3993566754565898
C = 9852.743130232526
D = 65726.35643776048
"```
6)

 `"7"`
```Returns:
"N = 8827
K = 1
competitor = -1.0003950048572934
C = 4269.086656520765
D = 37525.0749757682
"```
7)

 `"8"`
```Returns:
"N = 7707
K = 1
competitor = -1.624774126161923
C = 4693.371585706174
D = 55541.24266699317
"```
8)

 `"9"`
```Returns:
"N = 9239
K = 7
competitor = -0.3999948330662635
C = 7088.008974203557
D = 84879.89527259486
"```
9)

 `"10"`
```Returns:
"N = 7933
K = 10
competitor = -0.46486861795146006
C = 3455.1239532547734
D = 11926.436040241912
"```

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8176

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10502&pm=8176

Unknown

Simulation