思考题 with anime again
Spicy Wolf
XGN have watched the famous anime Spice and Wolf and now as usual, he will propose a problem.
In the country, there are N cities and M bidirectional roads. Each road connects two city and has a dangerous point Di. Each city has three properties: Pi - the profit, Fi - the deliciousness of the food there and Gi - the number of attractions in the city.
Now Lawrence, Horo and Nora are at city 1. Before the trip, Lawrence will give Nora X coins, which will be determined by you. This will make all roads with dangerous points less than or equal to X be available for passing.
Their journey will last for T days. In each day, they will first move to an adjacent city. There Lawrence will do some business and get Pi coins. The way they determine which city to go will follow these rules:
- Assume they are at city x and all adjacent cities are in
adj - Horo will first choose an adjacent city i randomly with the probability
- Then Nora will choose an adjacent city j randomly with the probability
- Then among city i and j, they will go to the one with higher profit.
For example, if the adjacent cities have [{P,F,G}]=[{1,2,3},{2,3,4},{5,6,7}], then a possible process is:
- Horo chose city 1
- Nora chose city 3
- Lawrence decided to go to city 3 because it had higher profit
- Possibility of this scene:
What’s the maximum expected profit after day T when the initial X is optimal? Please print the profit and the initial X.
Constraints
For all tests,
The size of the set of all Di is no bigger than 50.
All Pi are different
Hint
Brute force X, calculate expected value adjacent matrix, do matrix fastpow on it.