problem1

暴力即可。因为即便所有数字的和是50，50所有的不同的划分数只有204226中。所以最长的循环也就这么大。

problem2

令$f[i][j]$表示有$i$个红色和$j$个黑色时最大的期望，那么：

（1）当$j=0$时,$f[i][0]=f[i-1][0]+1$;

（2）当$j>0$但是$i=0$时,$f[i][j]=0$;

（3）当$j>0$且$i>0$时,$f[i][j]=max(0,(f[i-1][j]+1)*\frac{i}{i+j}+(f[i][j-1]-1)*\frac{j}{i+j})$

problem3

设$B$为$outputValues$中的最大值。

当$inputValue \geq B*(B-1)$时，在将$inputValue$置换后的输出中一定有$B$。否则，将有大于等于$B$个小于等于$B-1$的数字。那么这大于等于$B$个数字中，一定有某些数字的和是$B$的倍数（$x_{1},x_{1}+x_{2},,,,,x_{1}+x_{2}+..+x_{n}$中要么存在$B$倍数的数字，要么一定存在两个数字模$B$的值相等，它们的差就是$B$的倍数）。这时将其拿掉换成都是$B$得到的数字个数更小。

这样的话，只需要解决小于$B*(B-1)$的部分（大于等于$B*(B-1)$的部分都可以直接换成若干$B$）。这里可以使用动态规划。记录置换$i$需要的最少数量以及在这种置换中用到的最大的是$outputValues$中哪一种。

这里需要解决的是，当$i$是$outputValues$中的某个数字时，一定要将$i$替换成至少两个数字之和。可以令$bestPay[i]$表示将$i$置换所需要的最小的个数（可以是一个数字），$bestChange[i]$表示将$i$置换所需要的最小的个数（至少两个数字），而$bestPayCoin[i],bestChangeCoin[i]$分别表示两种情况下最大的是$outputValues$中哪一个。

有了这些，可以推导出小于$B*(B-1)$的$inputValue$被置换成了:

$t_{1}=bestChangeCoin[inputValue]$

$t_{2}=bestPayCoin[inputValue-t_{1}]$

$t3=bestPayCoin[inputValue-t_{1}-t_{2}]$

$...$

最后是对于最终答案的计算。可以从大到小依次置换每一种$outputValues$。

 code for problem1

import java.util.*;import java.math.*;import static java.lang.Math.*;public class SolitaireSimulation {	public int periodLength(int[] heaps) {		List
     
       list=new ArrayList<>();		for(int x:heaps) {			list.add(x);		}		List
      
        list1=next(list);		while(!list.equals(list1)) {			list=next(list);			list1=next(next(list1));		}		int step=1;		list=next(list);		while(!list.equals(list1)){			++step;			list=next(list);		}		return step;	}	List
       
         next(List
        
          list) {		List
         
           list1=new ArrayList<>();		for(int i=0;i
          
           1) { list1.add(list.get(i)-1); } } list1.add(list.size()); Collections.sort(list1); return list1; }}
          
         
        
       
      
     

　　

code for problem2

import java.util.*;import java.math.*;import static java.lang.Math.*;public class RedIsGood {		public double getProfit(int R, int B) {		double[][] f=new double[2][B+1];		for(int i=0;i<=B;++i) {			f[0][i]=0;		}		int pre=0,cur=1;		for(int i=1;i<=R;++i) {			for(int j=0;j<=B;++j) {				if(j==0) {					f[cur][j]=i;					continue;				}				double p=1.0*i/(i+j);				f[cur][j]=p*(f[pre][j]+1)+(1-p)*(f[cur][j-1]-1);				if(f[cur][j]<0) {					f[cur][j]=0;				}			}			pre^=1;			cur^=1;		}		return f[pre][B];	}}

　　

code for problem3

import java.util.*;import java.math.*;import static java.lang.Math.*;public class ChangeOMatic {		public long howManyRounds(int[] outputValues,long inputValue) {		if(outputValues.length==1) {			return 1;		}		final int N=outputValues.length;		final int B=outputValues[N-1];		final int MAX=B*B+B+47;		int[] bestPay=new int[MAX];		int[] bestPayCoin=new int[MAX];		int[] bestChange=new int[MAX];		int[] bestChangeCoin=new int[MAX];		for(int i=0;i
     
      =bestPay[i-outputValues[c]]+1) {					bestPay[i]=bestPay[i-outputValues[c]]+1;					bestPayCoin[i]=c;				}			}			for(int i=outputValues[c]+1;i
      
       =bestPay[i-outputValues[c]]+1) {					bestChange[i]=bestPay[i-outputValues[c]]+1;					bestChangeCoin[i]=c;				}			}		}		long[] coinCounts=new long[N];		if(inputValue>=MAX) {			coinCounts[N-1]=(inputValue-(MAX-1))/B;			inputValue-=coinCounts[N-1]*B;			if(inputValue>=MAX) {				inputValue-=B;				++coinCounts[N-1];			}			while(inputValue>0) {				++coinCounts[bestPayCoin[(int)inputValue]];				inputValue-=outputValues[bestPayCoin[(int)inputValue]];			}		}		else {			++coinCounts[bestChangeCoin[(int)inputValue]];			inputValue-=outputValues[bestChangeCoin[(int)inputValue]];			while(inputValue>0) {				++coinCounts[bestPayCoin[(int)inputValue]];				inputValue-=outputValues[bestPayCoin[(int)inputValue]];			}		}        long result=1;		for(int q=N-1;q>0;--q) {			result+=coinCounts[q];			int remains=outputValues[q];			coinCounts[bestChangeCoin[remains]]+=coinCounts[q];			remains-=outputValues[ bestChangeCoin[remains ]];			while(remains>0) {				coinCounts[bestPayCoin[remains]]+=coinCounts[q];				remains-=outputValues[bestPayCoin[remains]];			}		}		return result;	}}