2531回転寿司
4966 ワード
質問する
回転寿司レストランは回転するベルトの上で、皿の中でいろいろな寿司を盛って、客はその中から自分の好きな寿司を選んで食べます.寿司の種類を数字で表す場合、下図は回転寿司レストランのベルト状態の例を示しています.ベルトには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列目は回転寿司ベルトに乗せた皿の数N、寿司の種類数d、連続して食べる皿の数k、クーポン番号cの間にそれぞれスペースを残します.しかし,2≦N≦30000,2≦d≦3000,2≦k≦3000(k≦N),1≦c≦dであった.2行目からN行目では、ベルトの1つの位置から回転方向に沿って歩くと、寿司の種類を表す1以上d以下の整数が各行に与えられる.
しゅつりょく
与えられた回転寿司ベルトにおいて、食べられる寿司の種類数の最値は整数として出力される.
に答える
(ターンテーブルが1文字で立っていると仮定)
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)
Reference
この問題について(2531回転寿司), 我々は、より多くの情報をここで見つけました https://velog.io/@bbnerino/2531-회전초밥テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol