Problem:


MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

A: トーナメント

問題

 AOR イカちゃんとあなたは、トーナメント形式の卓球大会シングルスの部に偵察に来た。
全ての試合を録画したい AOR イカちゃんのために、あなたはこの大会で行われる試合数を求めてあげることにした。

この大会には $N$ 人の選手が参加しており、それぞれ $0, \dots , N - 1$ の背番号を持っている。
そのうち、 $M$ 人の選手が棄権し、試合には出場しなかった。

この大会の試合数は、以下のルールに基いて決定される。

    
シード選手は存在せず、任意の出場者が優勝するために必要な勝利回数は一定である。

    
対戦相手が不在の場合は試合を行わず、出場した選手が勝利する。試合数にはカウントされない。

    
優勝者が決まった段階で大会は終了する。

    
一度試合に負けた人が再び試合をすることはない。つまり敗者復活戦や 3 位決定戦などは行わない。

    
なお、卓球台が 1 台しか無いため異なる試合が同時に行われることはなく、また各試合では必ず勝者が決まる (引き分けとなることはない)。

なお、トーナメントの定義は次のとおりである。
トーナメントは高さ $L = \log_2 N$ の完全二分木で表され、葉にあたる各頂点には参加者の背番号が書き込まれている。
根の深さを 0 とすると、 $i$ 回戦 ($1 \le i \le L$) では、
深さ $L - i$ の各頂点の子に書かれた番号の選手同士が試合を行い、その勝者の背番号をその頂点に書き込む。

制約

$2 \le N \le 2^8$

$0 \le M \le N - 1$

$0 \le a_i \le N - 1 \ (0 \le i \le M - 1)$

 $N$ は 2 の累乗である。

 $a_i \ (0 \le i \le M - 1)$ は相異なる

入力形式

入力は以下の形式で与えられる。

$N \ M$

$a_1$

$\vdots$

$a_M$

    
1 行目には、参加者を表す整数 $N$ 、参加者のうち棄権した者の人数を表す整数 $M$ が与えられる。

    
続く $M$ 行には、棄権して出場しなかった選手の番号を表す整数 $a_i$ が与えられる。

出力

この大会が終了するまでに行われる試合数を 1 行で出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

2 0

サンプル出力 1

1

最初の試合で優勝者が決まる。

サンプル入力 2

4 2
2
3

サンプル出力 2

1



Sample input:
2 0


Sample output:
1

Submission status: Wrong Answer

Solution code:
import math
N,M=map(int,input().split())
for _ in [0]*M:
    a=input()
print(math.ceil(math.log2(N-M)))

Submission status: Wrong Answer

Solution code:
def main():
    N,M=map(int,input().split())
    a = [ int(input()) for _ in [0]*M ]
    ans = N - 1
    for i in range(0,N,2):
        if ( i + 1 in a ) or ( i + 2 in a):
            ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AOJ 2805: Tournament
# Python3 2018.7.11 bal4u

def calc(l, n):
	if n == 2:
		if a[l] and a[l+1]: return [0, True]
		if a[l] or a[l+1]: return [0, False]
		return [1, False]
	m = n >> 1
	c1, f1 = calc(l, m)
	c2, f2 = calc(l+m, m)
	if f1 and f2: return [c1+c2, True]
	if f1 or f2: return [c1+c2, False]
	return [c1+c2+1, False]

N, M = map(int, input().split())
if M == 0: print(N-1)
else:
	a = [False]*256
	for i in range(M): a[int(input())] = True
	print(calc(0, N)[0])

Submission status: Accepted

Solution code:
# AOJ 2805: Tournament
# Python3 2018.7.11 bal4u

N, M = map(int, input().split())
print(N-1-M)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = n - m - 1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    return n-m-1

print(main())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
print(N - M - 1)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
print n - m - 1

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
print (n - m - 1)
for i in range(m):
 a = input()

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    a = [ int(input()) for _ in [0]*M ]
    print(N-len(a)-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))
num = N - M
ans = 0
while(num):
    ans += 1
    num -= 1
print(ans - 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
for _ in [0]*m:input()
print(n-m-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
print(N-1-M)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
for i in range(m):
    input()
print(n-1-m)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
l = []
for i in range(M):
    l.append(int(input()))

count = N - 1 - M
print(count)

Submission status: Accepted

Solution code:
a = input().split(' ')
tour = int(a[0])-1
no_vs = 0

if int(a[1]) != 0:
    absent = []
    for _ in range(int(a[1])):
        absent.append(int(input()))
    num = int(int(a[0])/2)
    while absent != []:
        next_absent = []
        for n in range(num):
            if 2*n in absent or 2*n+1 in absent:
                no_vs+=1
                if 2*n in absent and 2*n+1 in absent:
                    next_absent.append(n)
        absent = next_absent
        num = int(num/2)
            
print(tour-no_vs)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
print(n-m-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
[input() for _ in range(m)]
print(n - m - 1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
for _ in range(m):
    tmp = input()

print(n-m-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))

ns = [i for i in range(n)]

for i in range(m):
  ha = int(input())
  ns[ha] = None

#print(n, m)
#print(ns)

count = 0
while True:
  size = len(ns)
  ns2 = []
  for j in range(0, size, 2):
    flag = ns[j] is not None and ns[j+1] is not None
    if flag:
      ns2.append( 0 )
      count += 1
    elif ns[j] is not None or ns[j+1] is not None:
      ns2.append( 0 )
    else:
      ns2.append( None)
  #print(ns2)
  ns = ns2
  if len(ns) == 1:
    break
print(count)

Submission status: Runtime Error

Solution code:
# AOJ 2805: Tournament
# Python3 2018.7.11 bal4u

def calc(l, n):
	if n == 2:
		if a[l] and a[l+1]: return [0, True]
		if a[l] or a[l+1]: return [0, False]
		return [1, False]
	m = n >> 1
	c1, f1 = calc(l, m)
	c2, f2 = calc(l+m, m)
	if f1 and f2: return [c1+c2, True]
	if f1 or f2: return [c1+c2, False]
	return [c1+c2+1, False]

while True:
	N, M = map(int, input().split())
	if M == 0: print(N-1)
	else:
		a = [False]*256
		for i in range(M): a[int(input())] = True
		print(calc(0, N)[0])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = map(int, input().split())

print(N - 1 - M)

Submission status: Runtime Error

Solution code:
a = input().split(' ')

while a != ['0','0']:
    recomend = [0 for _ in range(int(a[1]))]
    for i in range(int(a[0])):
        b = input().split(' ')
        if recomend[int(b[0])-1] < int(b[1]):
            recomend[int(b[0])-1] = int(b[1])
    print(sum(recomend))
    a = input().split(' ')

Submission status: Runtime Error

Solution code:
def make_alphabet(now_alphabet, alphabet):
    next_alphabet = []
    for n_al in now_alphabet:
        for al in alphabet:
            next_alphabet.append(n_al+al)
    return next_alphabet

a = int(input())
b = []
for a in range(a):
    b.append(input())
alphabet = [chr(ch) for ch in range(97,123)]
now_alphabet = alphabet
count=0
flag=0

while flag==0:
    letter = []
    for word in b:
        for i in range(len(word)-count):
            letter.append(word[i:i+1+count])
    rem = list(set(now_alphabet) - set(letter))
    if rem!=[]:
        print(sorted(rem)[0])
        flag=1
    count+=1
    now_alphabet = make_alphabet(now_alphabet, alphabet)