Problem:


ダーツ  

問題

あなたは以下のルールでダーツゲームをすることになった.

あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ずしも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的は N 個の部分に区切られていて,各々の部分に点数 P1,..., PN が書か   れている.矢が刺さった場所の点数の合計 S があなたの得点の基礎となる.S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.

的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

1 行目には,整数 N (1 ≤ N ≤ 1000) と M (1 ≤ M ≤ 200000000 = 2 &times; 108)がこの順に空白区切りで書かれている.2 行目以降の第 1 + i 行目 (1 ≤  i ≤ N ) には, Pi (1 ≤ Pi ≤ 100000000 = 108 ) が書かれている.

採点用データのうち, 配点の 20% 分は N ≤   100 を満たし,配点の 50% 分はN ≤ 300 を満たす.

N, M がともに 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

データセットごとにあなたが得ることのできる点数の最大値を１行に出力する.

入出力例

入力例

4 50
3
14
15
9
3 21
16
11
2
0 0

出力例

48
20

1つ目の例では,15 点の部分に 3 本,3 点の部分に 1 本の矢が刺さった場合にあなたの得点は最大になり,その得点は 48 点である.

2つ目の例では,16 点の場所に 1 本,2 点の場所に 2 本の矢が刺さった場合にあなたの得点は最大になり,その得点は 20 点である.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4 50
3
14
15
9
3 21
16
11
2
0 0


Sample output:
48
20

Submission status: Accepted

Solution code:
import bisect

while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0 for x in range(N+1)]
    for i in range(N):
        a[i+1]=int(raw_input())
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    #print c
    largest=0
    id=0
    st=len(c)-bisect.bisect(c,M)+1
    #print st
    for i in range(st,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            #print c[-i],c[id],c[-i]+c[id]
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest

Submission status: Accepted

Solution code:
from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    print max(i + p[bisect(p, lmt - i) - 1] for i in p[:s])

Submission status: Accepted

Solution code:
from bisect import bisect_right

while True:
    n, m = map(int, input().split())
    if not n:
        break

    ps = [0] + sorted(int(input()) for _ in range(n))

    p2 = set()
    for i, pi in enumerate(ps):
        for pj in ps[i:]:
            if pi + pj > m:
                break
            p2.add(pi + pj)

    p2 = sorted(p2)

    print(max(pi + p2[bisect_right(p2, m - pi) - 1] for pi in p2))

Submission status: Accepted

Solution code:
from time import perf_counter
from itertools import combinations_with_replacement
from bisect import bisect_right
from functools import lru_cache


def solve1(darts, scores, point, target):
    if darts == 3 or point > target:
        if point > target:
            return 0
        else:
            pos = bisect_right(scores, target-point)
            return point + scores[pos-1]

    max_score = 0
    for s in scores:
        result1 = solve1(darts + 1, scores, point + s, target)  # ???????????´???
        # result2 = solve1(darts + 1, scores, point, target)      # ?????°????????£?????´???
        max_score = max(max_score, result1)
    return max_score


def solve2(darts, scores, point, target):
    """ ???????????? """
    combi = combinations_with_replacement(scores, 4)
    max_score = 0
    max_combi = []
    for s in combi:
        score = sum(s)
        if score <= target and score > max_score:
            max_score = score
            max_combi = s
    print('max_combi: {0}'.format(max_combi))
    return max_score


Target = 0
def solve3(darts, scores, point, target):
    """ ?????£???????????°??????????????¢??? """
    global Target
    Target = target
    return cache_solve3(darts, tuple(scores), point)


@lru_cache(maxsize=None)
def cache_solve3(darts, scores, point):
    if darts == 4 or point > Target:
        if point > Target:
            return 0
        else:
            pos = bisect_right(scores, Target-point)
            return point + scores[pos-1]

    max_score = 0
    for s in scores:
        result1 = cache_solve3(darts + 1, scores, point + s)
        max_score = max(max_score, result1)
    return max_score


def solve4(darts, scores, point, target):
    if darts == 3 or point > target:
        if point > target:
            return 0
        else:
            pos = bisect_right(scores, target-point)
            return point + scores[pos-1]

    max_score = 0
    t = (target - point) // (4 - darts)
    min_lim = bisect_right(scores, t)
    for s in range(min_lim-1, len(scores)):
        result1 = solve4(darts + 1, scores, point + scores[s], target)  # ???????????´???
        max_score = max(max_score, result1)
    return max_score


def solve5(darts, scores, point, target):
    combi = combinations_with_replacement(scores, 2)
    i_scores = [sum(x) for x in combi if sum(x) < target]
    i_scores.sort()

    results = [x + find_le(i_scores, target-x) for x in i_scores]
    return max(results)


def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError


if __name__ == '__main__':
    # ??????????????\???
    while True:
        N, M = [int(x) for x in input().split(' ')]
        scores = [int(input()) for _ in range(N)]

        if N == 0 and M == 0:
            break

        # ???????????????????????????????¨????
        scores.append(0)  # ??????????????????????????????????????¨??????????????¢???????????????????????????=0????????????
        scores.sort()  # ???????????°??????????????????????????????

        # start_time = perf_counter()
        # ans = solve1(0, scores, 0, M)
        # end_time = perf_counter()
        # print('solve1, elapsed: {0}'.format(end_time - start_time))
        # print(ans)

        # start_time = perf_counter()
        # ans = solve2(0, scores, 0, M)
        # end_time = perf_counter()
        # print('solve2, elapsed: {0}'.format(end_time - start_time))
        # print(ans)

        # start_time = perf_counter()
        # ans = solve4(0, scores, 0, M)
        # end_time = perf_counter()
        # print('solve4, elapsed: {0}'.format(end_time - start_time))
        # print(ans)

        #start_time = perf_counter()
        ans = solve5(0, scores, 0, M)
        #end_time = perf_counter()
        #print('solve5, elapsed: {0}'.format(end_time - start_time))
        print(ans)

        # ???????????¨???
        # print(ans)

Submission status: Accepted

Solution code:
import bisect
while 1:
    n,m=map(int,input().split())
    if n==0:break
    s=[]
    a=[0]+sorted([int(input()) for _ in range(n)])
    for i in range(n+1):
        for j in a[i:]:
            if a[i]+j>m:break
            s+=[a[i]+j]
    s.sort()
    print(max(i+s[bisect.bisect_right(s,m-i)-1]for i in s))

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

NM = file_input.readline()

import itertools, bisect

while NM != '0 0\n':
    N, M = map(int, NM.split())
    P = [int(file_input.readline()) for i in range(N)]
    P.append(0)
    scores = map(sum, itertools.combinations_with_replacement(P, 2))
    scores = list(set(scores))
    scores.sort()
    ans = []
    for s1 in scores:
        rest = M - s1
        i = bisect.bisect_right(scores, rest)
        if i:
            ans.append(s1 + scores[i - 1])
    print(max(ans))
    NM = file_input.readline()

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

NM = file_input.readline()

import itertools, bisect

while NM != '0 0\n':
    N, M = map(int, NM.split())
    P = [int(file_input.readline()) for i in range(N)]
    P.append(0)
    scores = map(sum, itertools.combinations_with_replacement(P, 2))
    scores = filter(lambda x: x <= M, scores)
    scores = list(set(scores))
    scores.sort()
    print(max(s + scores[bisect.bisect_right(scores, M - s) - 1] for s in scores))
    NM = file_input.readline()

Submission status: Accepted

Solution code:
import bisect
def main():
	while True:
		n,m=map(int,input().split())
		if n==0 and m==0:
			break
		p=[0]+sorted([int(input()) for i in range(n)])
		s=list()
		for i in range(n+1):
			for j in p[i:]:
				if p[i]+j>m:
					break
				s+=[p[i]+j]
		s.sort()
		print(max(i+s[bisect.bisect_right(s,m-i)-1] for i in s))

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    
    lst = [int(input()) for _ in range(n)]
    lst.append(0)
    lst = sorted(lst)
    lst2 = [i + j for i in lst for j in lst if i <= j]
    lst2 = sorted(lst2)
    A = []
    index = len(lst2) - 1
    for i in lst2:
      if i + lst2[-1] <= m:
        A.append(i + lst2[-1])
      elif i <= m:
        while True:
          if i + lst2[index] <= m:
            break
          index -= 1
        A.append(i + lst2[index])
      else:
        break
    print(max(A))
solve()

Submission status: Accepted

Solution code:
import bisect
def main():
    while True:
        n, m = map(int, input().split())
        if n == 0:
            break
        p = [0] + list(int(input()) for i in range(n))
        point = []
        for i in range(n):
            for j in p[i:]:
                a = p[i] + j
                if a < m:
                    point.append(a)
        point.sort()

        print(max(i + point[bisect.bisect_left(point, m - i) - 1] for i in point))
            
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
# AOJ 0529: Darts
# Python3 2018.7.1 bal4u

import bisect
while True:
	n, m = map(int, input().split())
	if n == 0: break
	p = [int(input()) for i in range(n)]
	p.append(0)
	p.sort()
	s = [i+j for i in p for j in p if i <= j]
	s.sort()
	t = bisect.bisect_left(s, m)
	h = bisect.bisect_left(s, m>>1, 0, t)
	if t < len(s):
		if s[t] == m:
			print(m);
			continue
		s = s[:t]
	ans = 0
	for i in range(h-1, len(s)):
		t = bisect.bisect_left(s, m-s[i])
		if s[i]+s[t-1] > ans: ans = s[i]+s[t-1]
	print(ans)

Submission status: Accepted

Solution code:
import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    t=bisect.bisect(B,M)-1
    maxInt=max(i+B[bisect.bisect(B,M-i)-1] for i in B[:t])
    print maxInt

Submission status: Accepted

Solution code:
from bisect import *
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P = [int(raw_input()) for i in range(N)] + [0]
	P = sorted(set(i+j for i in P for j in P))
	s = bisect(P,M) - 1
	print max(i + P[bisect(P,M-i) - 1] for i in P[:s])

Submission status: Accepted

Solution code:
import bisect

while True:
  N,M = map(int,input().split())
  if N == 0 and M == 0: break
  targets = [0]+[ int(input()) for _ in range(N) ]
  targets.sort()

  cans = [targets[i]+targets[j] for i in range(N+1) for j in range(i,N+1) if targets[i]+targets[j] <= M]
  cans.sort()

  res = 0

  for l in cans:
    y = cans[bisect.bisect_right(cans, M-l)-1]
    res = max(res, l+y)

  print(res)

Submission status: Accepted

Solution code:
import bisect

while True:
    max_S = 0
    p = [0]
    pp = []
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break

    for _ in range(n):
        p.append(int(input())) 

    # 最初にダーツ2本を投げた状態にする
    for i in range(n+1):
        for j in range(i, n+1):
            pp.append(p[i] + p[j])
    
    pp.sort()
    # t: ppの中でm以下の数字の位置
    t = bisect.bisect_left(pp, m)
    # h: ppの中でm/2以下の数字の位置
    h = bisect.bisect_left(pp, m//2, 0, t)

    if t < len(pp):
        if pp[t] == m:
            print(m)
            continue
        pp = pp[:t]
    max_S = 0

    for i in range(len(pp)):
        t = bisect.bisect_left(pp, m-pp[i])
        if pp[i] + pp[t-1] > max_S:
            max_S = pp[i] + pp[t-1]

    print(max_S)

Submission status: Accepted

Solution code:
import bisect

while True:
  max_S = 0
  p = [0]
  pp = []

  n, m = map(int, input().split())
  if n == 0 and m == 0:
    break

  for _ in range(n):
    p.append(int(input()))

  for c in range(n + 1):
    for d in range(c, n + 1):
      pp.append(p[c] + p[d])

  pp.sort()

  # ppの中でm以下の数字の位置
  t = bisect.bisect_left(pp, m)
  ## ppの中でm/2以下の数字の位置
  h = bisect.bisect_left(pp, m//2 , 0, t)

  if t < len(pp):
    if pp[t] == m:
      print(m)
      continue
    pp = pp[:t]
  max_S = 0

  for i in range(0, len(pp)):
    t = bisect.bisect_left(pp, m - pp[i])
    if pp[i] + pp[t - 1] > max_S:
      max_S = pp[i] + pp[t - 1]
  print(max_S)

Submission status: Accepted

Solution code:
from itertools import product
from bisect import bisect_left

def main():
    while True:
        N, M = map(int, input().split())
        if N == M == 0:
            break
        p = [int(input()) for _ in range(N)]
        p.append(0)
        points = []
        for i in range(N + 1):
            for j in range(i, N + 1):
                points.append(p[i] + p[j])
        points.sort()
        ans = 0
        for i in range(len(points)):
            index = bisect_left(points, M - points[i])
            if index != 0:
                ans = max(ans, points[i] + points[index - 1])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def input_score(N):
    score = []  # 的の配点をいれる配列、投げないときの点も入れておく
    score.append(0)
    for i in range(N):
        score.append(int(input()))
    return score


def cal_four_sum_score(two_score, M):
    left = 0
    right = len(two_score) - 1
    max_score = 0
    while left != right:
        now_score = two_score[left] + two_score[right]
        if now_score < M:
            # scoreの和がMより小さい時、解の候補である
            max_score = max(max_score, now_score)
            left += 1
        elif now_score > M:
            # scoreの和がMより大きい時、解の候補ではない
            right -= 1
        else:
            # scoreの和がちょうどMになるとき、解である
            max_score = M
            break

    return max_score


def cal_two_sum_score(score):
    two_score = []  # 二回投げた時に取りうる範囲を入れる配列
    contain_sum = {}  # 二回投げたときにその値はすでに存在するか判断する配列
    for i in range(len(score)):
        for j in range(len(score)):
            now_score = score[i] + score[j]
            if not contain_sum.get(now_score):
                contain_sum[now_score] = True
                two_score.append(now_score)

    two_score.sort()  # 尺取り法を用いるためsortしておく
    return two_score


def main():
    while True:
        N, M = map(int, input().split())
        if N == 0 and M == 0:
            break
        score = input_score(N)  # 的の配点の入力
        two_score = cal_two_sum_score(score)  # 二回投げた時に取りうる点の範囲を計算
        max_score = cal_four_sum_score(two_score, M)  # 四回投げたときに取りうる点の範囲を計算
        print(max_score)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
while 1:
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    s=[int(input())for i in range(n)]
    a=set()
    a.add(0)
    for i in range(n):
        a.add(s[i])
        for j in range(i,n):
            a.add(s[i]+s[j])
    a=sorted(list(a))
    s=0
    for i in a:
        if i<m:
            s=max(s,i+a[bl(a,m-i)-1])
    print(s)

Submission status: Accepted

Solution code:
from bisect import bisect_right

while True:
    N, M = [int(x) for x in input().split()]
    if N == 0 and M == 0:
        break

    _P = [0] * N

    for i in range(N):
        _P[i] = int(input())
    _P.append(0)

    P = list(set(x + y for x in _P for y in _P))
    P.sort()

    ans = 0

    for p in P:
        if p > M // 2:
            break
        i = bisect_right(P, M - p)
        ans = max(ans, p + P[i - 1])

    print(ans)

Submission status: Accepted

Solution code:
import bisect,sys
input = sys.stdin.readline
 
while True :
    n,m = map(int , input().split())
    p = [0]
 
    if (n == 0) : break
     
    for i in range(n):
        pp = int(input())
        p.append(pp)
 
    pt1 = []
    for i,ii in enumerate(p):
        for jj in p[i:]:
            pt1.append(ii+jj)
 
    pt1.sort()
 
    ans = 0
    for i in pt1:
        if (i > m) : break
        amari = m - i
        ans = max(ans , i+ pt1[bisect.bisect_right(pt1,amari)-1])
 
    print(ans)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0529
# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2985387#1

import bisect
while True:
    n, m = map(int, input().split())
    if n == 0: break
    p = [int(input()) for i in range(n)]
    p.append(0)
    p.sort()
    s = [i+j for i in p for j in p if i <= j]
    s.sort()
    t = bisect.bisect_left(s, m)
    h = bisect.bisect_left(s, m>>1, 0, t)
    if t < len(s):
        if s[t] == m:
            print(m);
            continue
        s = s[:t]
    ans = 0
    # for i in range(h-1, len(s)):
    for i in range(h):
        t = bisect.bisect_left(s, m-s[i])
        if s[i]+s[t-1] > ans: ans = s[i]+s[t-1]
    print(ans)

Submission status: Runtime Error

Solution code:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    p=[0]+[int(raw_input()) for _ in xrange(n)]
    com=[None]*((n+1)**2)
    for i in xrange(n+1):
        for j in xrange(n+1):
            com[(n+1)*i+j]=p[i]+p[j]
    com.sort()
    ans=0
    for i in xrange(n+1):
        for j in xrange(n+1):
            tmp=m-com[(n+1)*i+j]
            if tmp<0:continue
            index=bisect.bisect_left(com,tmp)
            if index==(n+1)**2:continue
            if com[index]>tmp:
                if index==0:continue
                else:
                    index-=1
            ans=max(ans,com[(n+1)*i+j]+com[index])
        if ans==m:
            break

Submission status: Runtime Error

Solution code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			String line[] = br.readLine().split(" ");
			int n = Integer.parseInt(line[0]);
			int m = Integer.parseInt(line[1]);
			if (n==0) {break;}

			int[] onelist = new int [n+1];
			for(int i=1; i<=n; i++){
				onelist[i] = Integer.parseInt(br.readLine());
			}

			int[] twolist = new int [(n+2)*(n+1)/2];
			for(int i=0; i<=n; i++){
				for(int j=i; j<=n; j++){
					twolist[i*(n+1)-i*(i+1)/2 + j] = onelist[i] + onelist[j];
				}
			}
			Arrays.sort(twolist);

			int answer = 0;
			int maxi = (n+2)*(n+1)/2-1;
			KOKO: for(int i=0; i<m; i++){
				for(int j=0; j<=maxi; j++){
					while(twolist[j]+twolist[maxi] > m-i ){maxi--;}
					if (twolist[j] + twolist[maxi] == m-i){
						answer = m-i;
						break KOKO;
					}
				}
			}
			System.out.println(answer);
		}
	}
}