【Python】長テーブルのうなぎ屋

6783 ワード
Python 初心者 Python3 paiza Python テキストリンク

1.問題

円状になったテーブル(テーブル数n)に何人が座る事ができるかを求める問題。
グループの内、一人でも座れない場合そのグループは帰ってしまう。

入力はm+1行から成る。
1行目にはn(座席数)とm(グループ数)が半角スペース区切りで入力される。
i+1行目(1≦i≦m)には2個の整数a_i(グループの人数)とb_i(着席開始座席番号)が半角スペース区切りで入力される。

条件
全てのテストケースにおいて、入力される値は以下の条件を満たす。
1≦n≦100
1≦m≦100
1≦a_i≦n
1≦b_i≦n

2.考えた方法

(1)テーブル番号

あるグループiがk人おり、b_i番テーブルから座る時
このグループは

b_i,...,b_(i+k-1)

までのテーブルに座る事を想定している。

例えば、上記でテーブル数が6、(a_i,b_i)=(4,5)だった場合
座る予定のテーブル番号は(5,6,7,8)ではなく(5,6,1,2)となる事に注意する。
ここで全てのテーブル番号はb_j%n(b_jをnで割った余り)と考える事にした。

(2)あるグループが座るか座らないか:check_arr関数で判定

着席しているテーブル配列:ar_table
あるグループが座る想定をしているテーブル番号の配列
(make_tblarr関数で作成):ar_chk
ar_tableにar_chkの要素が一つでも含まれる場合座れないと判定する。

(3)座っている人数の表示

上記で座れる判定をされたグループは、それらのテーブル番号を着席テーブル配列に追加していく。
最終的に、着席テーブル配列のサイズを表示する。

3.コード例

動作は確認済。


# coding: utf-8
# Your code here!
in1=input()
arr1=in1.split()
n1=int(arr1[0])
n2=int(arr1[1])

in2=[]
for i in range(n2):
    tmp=input()
    in2.append(tmp)
#print(in2)


def make_tblarr(in2,nmax):
    arr3=[]
    arr2=in2.split()
    nn=int(arr2[0])
    st=int(arr2[1])

    for i in range(nn):
        arr3.append((st+i)%nmax)

    return arr3


#ar_table:座っているテーブル番号の配列
#ar_chk:チェック対象の配列
#ar_tableにar_chkの全ての要素が含まれない時0、含まれる要素が見つかった場合1
def check_arr(ar_table,ar_chk):
    flg=0
    for i in range(len(ar_chk)):
        #チェック対象の配列要素が既にar_tableに含まれる場合
        if ar_table.count(ar_chk[i])>0:
            #flgを1にする
            flg=1
            break
    return flg


retar=[]
for i in range(n2):
    ar3=make_tblarr(in2[i],n1)
#print(ar3)
    if check_arr(retar,ar3)== 0:
        for j in range(len(ar3)):
            retar.append(ar3[j])

print(len(retar))