No.335 Kadomatsu Lottery
タグ : / 解いたユーザー数 62
作問者 :
nmnmnmnmnmnmnm
Problem Statement
A kadomatsu sequence is defined as follows: when 3 integers are arranged as A, B, C from the left,
all the values are distinct and the second largest integer among A, B, C is either A or C.
The "Kadomatsu Lottery" is a lottery that uses kadomatsu sequences to determine winners.
First, each lottery ticket has N numbers written in a single horizontal row from the left.
The numbers are positive integers in the range from 1 to N, with no duplicates.
Winning is checked using 3 distinct numbers.
2 distinct winning numbers out of the 3 are made public at the time of the winning number announcement.
These 2 distinct winning numbers are chosen uniformly from the numbers 1 to N.
The last winning number can be freely chosen by yourself after seeing the 2 numbers.
The 3 winning numbers are located on the lottery ticket and extracted without changing their order from the left.
If the 3 numbers then form a kadomatsu sequence, the maximum of the 3 numbers is the prize amount.
If no kadomatsu sequence can be formed in any way, the prize amount is 0.
D-kun is considering buying a Kadomatsu Lottery ticket before the winning numbers are announced.
Right now, he can look at the numbers written on M lottery tickets and buy one of them.
After the winning numbers are announced, D-kun makes the choice that gives the highest prize amount.
He wants to buy the lottery ticket with the highest expected prize amount, so determine which one it is.
Input
$N\ M$
$E_{0,0}\ E_{0,1}\ \dots\ E_{0,N-1}$
$E_{1,0}\ E_{1,1}\ \dots\ E_{1,N-1}$
$\vdots$
$E_{M-1,0}\ E_{M-1,1}\ \dots\ E_{M-1,N-1}$
N is the count of numbers written on a Kadomatsu Lottery ticket, and the numbers used are from 1 to N. $3\le N \le 800$.
M is the number of Kadomatsu Lottery tickets to choose from. $2\le M \le 3$.
$E_{i,j}$ represents the positive integer written j-th from the left on the i-th lottery ticket. $1\le E_{i,j} \le N$.
The numbers written on the i-th lottery ticket contain no duplicates.
Output
Which lottery ticket in the input should be bought?
Output the answer as a 0-indexed position.
If there are multiple answers, the smallest position is the answer.
Do not forget the newline at the end.
Sample
Sample 1
Input
4 2 4 3 1 2 1 2 3 4
Output
0
The 0-th Kadomatsu Lottery ticket has the 4 integers "4 3 1 2" written from the left.
If the 2 distinct numbers chosen are "1 and 2", choosing "4" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "1 and 3", choosing "2" last gives a prize amount of 3.
If the 2 distinct numbers chosen are "1 and 4", choosing "2" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "2 and 3", choosing "1" last gives a prize amount of 3.
If the 2 distinct numbers chosen are "2 and 4", choosing "1" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "3 and 4", no kadomatsu sequence can be formed. The prize amount is 0.
Therefore, the expected prize amount is 4$\times$3/6+3$\times$2/6, which is 3.
The 1-st Kadomatsu Lottery ticket has the 4 integers "1 2 3 4" written from the left.
The 1-st lottery ticket cannot form a kadomatsu sequence for any winning numbers.
Therefore, the expected prize amount is 0.
Hence, we can see that the 0-th Kadomatsu Lottery ticket should be bought.
Sample 2
Input
3 3 1 2 3 1 2 3 3 2 1
Output
0
It is clear before buying that no Kadomatsu Lottery ticket can ever win, whichever one is bought.
However, the expected prize amount is 0 for all of them, so the answer is the smallest position, 0.
Sample 3
Input
5 3 2 1 3 4 5 3 2 1 5 4 5 2 4 1 3
Output
1
Sample 4
Input
6 3 1 3 2 4 5 6 1 2 4 5 3 6 1 4 3 5 6 2
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。