2013
11-10

# POJ 2163 Easy Trading [解题报告] Java

Frank is a professional stock trader for Advanced Commercial Markets Limited (ACM Ltd). He likes “easy trading” — using a straightforward strategy to decide when to buy stock and when to sell it. Frank has a database of historical stock prices for each day. He uses two integer numbers m and n (1 <= m < n <= 100) as parameters of his trading strategy. Every day he computes two numbers: P(m) -- an average stock price for the previous m days, and P(n) — an average stock price for the previous n days. P(m) > P(n) is an indicator of the upward trend (traders call it bullish trend), and P(m) < P(n) is an indicator of the downward trend (traders call it bearish trend). In practice the values for P(m) and P(n) are never equal.

When a trend reverses from bearish to bullish it is a signal for Frank to buy stock. When a trend reverses from bullish to bearish it is a signal to sell.

Frank has different values for m and n in mind and he wants to backtest them using historical prices. He takes a set of k (n < k <= 10 000) historical prices pi (0 < pi < 100 for 1 <= i <= k). For each i (n <= i <= k) he computes Pi(m) and Pi(n) — an arithmetic average of pi-m+1 . . . pi and pi-n+1 . . . pi respectively. Backtesting generates trading signals according to the following rules.
• If Pi(m) > Pi(n) there is a bullish trend for day i and a “BUY ON DAY i” signal is generated if i = n or there was a bearish trend on day i – 1.
• If Pi(m) < Pi(n) there is a bearish tread for day i and a "SELL ON DAY i" signal is generated if i = n or there was a bullish trend on day i - 1.

Your task is to write a program that backtests a specified strategy for Frank — you shall print a signal for the first tested day (day n) followed by the signals in increasing day numbers.

The first line of the input contains three integer numbers m, n, and k. It is followed by k lines with stock prices for days 1 to k. Each stock price pi is specified with two digits after decimal point. Prices in the input file are such that Pi(m) != Pi(n) for all i (n <= i <= k).

Write to the output a list of signals — one signal on a line, as described in the problem statement.

3 5 17
8.45
9.10
9.40
10.15
10.40
11.08
11.52
12.12
12.51
12.15
11.90
11.25
11.73
10.77
10.80
10.01
9.14

BUY ON DAY 5
SELL ON DAY 12

//* @author:
import java.util.*;
public class Main
{

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
int k=sc.nextInt();
node a[]=new node[k+1];
for(int i=0;i<=k;i++)
a[i]=new node();
for (int i=1;i<=k;i++) {
a[i].p=sc.nextDouble();
a[i].pm=a[i-1].pm+a[i].p;
a[i].pn=a[i-1].pn+a[i].p;
if (i>m) a[i].pm-=a[i-m].p;
if (i>n) a[i].pn-=a[i-n].p;
}
for (int i=n;i<=k;i++) {
if (a[i].pm/m>a[i].pn/n&&(a[i-1].pm/m< a[i-1].pn/n||i==n))
else if (a[i].pm/m< a[i].pn/n&&(a[i-1].pm/m>a[i-1].pn/n||i==n))
System.out.printf("SELL ON DAY %d\n",i);
}
}
}

class node{
double p;
double pm;
double pn;

public node(){
}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

4. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

5. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3