2531回転寿司


質問する


回転寿司レストランは回転するベルトの上で、皿の中でいろいろな寿司を盛って、客はその中から自分の好きな寿司を選んで食べます.寿司の種類を数字で表す場合、下図は回転寿司レストランのベルト状態の例を示しています.ベルトには2種類以上の寿司があります.
新しくオープンした回転寿司店は、不況で営業が困難なため、以下の2つの活動で売上を伸ばしたいと考えています.
もともと回転寿司は客が勝手に寿司を選び、食べた寿司によって食事量を計算していたが、ベルトのいずれかの位置からk個の皿を連続して食べると、割引の固定価格で提供された.
お客様1人につき1種類の寿司が書かれたクーポンを配布し、1番のイベントに参加する際に、そのクーポンに書かれた寿司を無料でプレゼントします.この番号に書いてある寿司が今ベルトにない場合、コックはお客様に作り直します.
以上の割引イベントに参加して、できるだけいろいろな寿司を食べます.図の例を取って考えなさい.k=4、クーポンとして30番寿司を受け取ったとします.クーポンを考えなければ4種類の異なるお寿司(9、7、30、2)、(30、2、7、9、25)、(2、7、9、25)の3種類を食べることができ、30番のお寿司をクーポンに加えれば(2、7、9、25)、5種類のお寿司を食べることができます.
回転寿司店のベルト状態、メニュー上の寿司の種類数、連続して食べる皿の数、クーポン番号を取得するプログラムを作成し、お客様が食べられる寿司の種類の最低価格を取得します.

入力


1列目は回転寿司ベルトに乗せた皿の数N、寿司の種類数d、連続して食べる皿の数k、クーポン番号cの間にそれぞれスペースを残します.しかし,2≦N≦30000,2≦d≦3000,2≦k≦3000(k≦N),1≦c≦dであった.2行目からN行目では、ベルトの1つの位置から回転方向に沿って歩くと、寿司の種類を表す1以上d以下の整数が各行に与えられる.

しゅつりょく


与えられた回転寿司ベルトにおいて、食べられる寿司の種類数の最値は整数として出力される.

に答える

  • 回転盤なので、連続で引いた寿司の数に応じて、最初の寿司を足します.
    (ターンテーブルが1文字で立っていると仮定)
  • 1~4,2~5,3~6すべての組合せを確認し、
  • .
  • セットにクーポンがない場合は追加してください.
  • 重複を解消し、最も多くの寿司数を得る
  • .
    N,d,k,c = map(int,input().split())
    
    # N 초밥개수 d : 의미x  k:연속 초밥 , c : 쿠폰번호
    
    graph =[]
    for _ in range(N):
        graph.append(int(input()))
    
    graph.extend(graph[0:k])
    # 회전판이기 때문에 연속으로 뽑는 초밥수만큼 처음의 초밥들을 더해줍니다.
    
    result = 0 # 최대초밥수
    for i in range(N):
        newgraph =graph[i:i+k] # 1~4, 2~5,3~6... 모든 조합을 보는데
        if c not in newgraph: # 그 초밥안에 쿠폰초밥이 없다면
            newgraph.append(c) # 더해줍니다
        newgraph = list(set(newgraph)) # 먹은 초밥중 중복방지용
        result = max(result,len(newgraph)) # 가장 많은 초밥수를 구합니다
    print(result)