Problem:


Problem 03: Selecting Teams Advanced to Regional

日本で毎年開催される国際大学対抗プログラミングコンテストのアジア地区予選に出場するためには、厳しい国内予選を突破しなければなりません。

大学対抗とは言っても、１つの学校から複数のチームが参戦します。そこで、できるだけ多くの学校がアジア地区予選に出場できるように、突破チームの選抜には以下の選抜ルールが適用されます：

該当チームを A とし、成績の優秀な順番に次のルールを適用します：

ルール 1：

その時点での選抜チーム数が 10 に満たない場合：

A と同じ所属でその時点で選抜されたチームの数が 3 に満たなければ、A は選抜されます。

ルール 2：

その時点での選抜チーム数が 20 に満たない場合：

A と同じ所属でその時点で選抜されたチームの数が 2 に満たなければ、A は選抜されます。

ルール 3：

その時点での選抜チーム数が 26 に満たない場合：

A と同じ所属でその時点で選抜されたチームがなければ、A は選抜さます。

また、成績の順番は次のルールで決定されます：

より多くの問題を解いたチームが上位となります。

解いた問題数が同じ場合は、ペナルティが小さいチームが上位となります。

各チームのID（整数）、所属（整数）、正解数（整数）、ペナルティ（整数）を入力し、選抜チームのIDを選抜順に出力するプログラムを作成して下さい。
チームは成績順に与えられるとは限らないので、順位付けした後、選抜ルールを適用しなければならないことに注意して下さい。

この問題では、正解数とペナルティが同じチームがあった場合はIDが小さい方を上位とします。

Input

複数のデータセットが入力として与えられます。各データセットは以下の形式で与えられます：

n (チーム数：整数)

I1 U1 A1 P1	 (1番目のチームのID、所属、正解数、ペナルティ：空白区切りの４つの整数)

I2 U2 A2 P2	 (2番目のチームのID、所属、正解数、ペナルティ：空白区切りの４つの整数)

.

.

In Un An Pn  (n番目のチームのID、所属、正解数、ペナルティ：空白区切りの４つの整数)

n は 300 以下であり、Ii, Ui は 1 以上 1000 以下とします。１つのデータセットに、同じ ID のチームは無いと仮定してかまいません。

Ai は 10 以下、Pi は 100,000 以下とします。

n が 0 のとき、入力の終わりとします。

Output

各データセットについて、選抜チームのIDを選抜された順に出力して下さい。1つのIDを1行に出力して下さい。

Sample Input

6
1 1 6 200
2 1 6 300
3 1 6 400
4 2 5 1200
5 1 5 1400
6 3 4 800
3
777 1 5 300
808 2 4 20
123 3 6 500
2
2 1 3 100
1 1 3 100
0

Output for the Sample Input

1
2
3
4
6
123
777
808
1
2



Sample input:
6
1 1 6 200
2 1 6 300
3 1 6 400
4 2 5 1200
5 1 5 1400
6 3 4 800
3
777 1 5 300
808 2 4 20
123 3 6 500
2
2 1 3 100
1 1 3 100
0


Sample output:
1
2
3
4
6
123
777
808
1
2

Submission status: Wrong Answer

Solution code:
def sort_cmp(x, y):
    if x[2] == y[2]:
        return x[3] < y[3]
    else:
        return x[2] > x[2]


def solve(n):
    teams = []
    for i in range(n):
        teams.append(list(map(int, raw_input().split())))

    teams = sorted(teams, key=lambda x: -1e12 * x[2] + x[3] * 1e6 + x[0])

    A = []
    B = []
    threshold = 3
    for team in teams:
        if len(A) == 10:
            threshold = 2
        elif len(A) == 20:
            threshold = 1e8

        if B.count(team[1]) < threshold:
            A.append(team[0])
            B.append(team[1])

        if len(A) == 26:
            break

    for a in A:
        print(a)


while True:
    n = int(raw_input())
    if n == 0:
        break
    solve(n)

Submission status: Wrong Answer

Solution code:
def main():
    while True:
        n = int(input())
        if n == 0: break

        teams = []
        for i in range(n):
            teams.append(list(map(int, input().split())))
       
        def same_len(l):
            return len(list(filter(lambda x: x[1] == e[1], ans))) 

        ans = []
        for e in sorted(sorted(teams, key=lambda x: x[0]), key=lambda x: x[2], reverse=True):
            if len(ans) < 10 and same_len(ans) < 3:
                ans.append(e)
            elif len(ans) < 20 and same_len(ans) < 2:
                ans.append(e)
            elif len(ans) < 26 and same_len(ans) == 0:
                ans.append(e)

        for a in ans:
            print(a[0])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AOJ 1043: Selecting Teams Advanced to Regional
# Python3 2018.7.6 bal4u

def pr(i, u):
	global total
	print(team[i][0])
	total, affi[u] = total+1, affi[u]+1

while True:
	n = int(input())
	if n == 0: break
	team = []
	for i in range(n):
		id, u, a, p = map(int, input().split())
		team.append((id, u, a, p))
	team.sort(key=lambda x:(-x[2],x[3],x[0]))
	total, affi = 0, [0]*1002
	for i in range(n):
		u = team[i][1]
		if   total < 10 and affi[u] < 3: pr(i, u)
		elif total < 20 and affi[u] < 2: pr(i, u)
		elif total < 26 and affi[u] < 1: pr(i, u)

Submission status: Accepted

Solution code:
# AOJ 1043: Selecting Teams Advanced to Regional
# Python3 2018.7.6 bal4u

def pr(i, u):
    global total
    print(team[i][0])
    total, affi[u] = total + 1, affi[u] + 1


while True:
    n = int(input())
    if n == 0: break
    team = [list(map(int, input().split())) for i in range(n)]
    team.sort(key=lambda x: (-x[2], x[3], x[0]))
    total, affi = 0, [0] * 1002
    for i in range(n):
        u = team[i][1]
        if   total < 10 and affi[u] < 3: pr(i, u)
        elif total < 20 and affi[u] < 2: pr(i, u)
        elif total < 26 and affi[u] < 1: pr(i, u)

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        Slist=[]
        Blist=[0 for i in range(1001)]
        ans=[]
        allb=0
        thres=3
        
        for k in range(n):
            S=[int(x) for x in raw_input().split()]
            Slist.append(S)
        Slist.sort(key = lambda x:x[0])
        Slist.sort(key = lambda x:x[3])
        Slist.sort(key = lambda x:x[2],reverse=True)
        
        for i in range(n):
            if allb==10:
                thres=2
            elif allb==20:
                thres=1
            elif allb==26:
                break
            
            bd=Slist[i][1]
            if Blist[bd]<thres:
                ans.append(Slist[i][0])
                Blist[bd]+=1
                allb+=1
        for a in ans:
            print a

Submission status: Accepted

Solution code:
def sort_cmp(x, y):
    if x[2] == y[2]:
        return x[3] < y[3]
    else:
        return x[2] > x[2]


def solve(n):
    teams = []
    for i in range(n):
        teams.append(list(map(int, raw_input().split())))

    teams = sorted(teams, key=lambda x: -1e12 * x[2] + x[3] * 1e6 + x[0])

    A = []
    B = []
    threshold = 3
    for team in teams:
        if len(A) == 10:
            threshold = 2
        elif len(A) == 20:
            threshold = 1

        if B.count(team[1]) < threshold:
            A.append(team[0])
            B.append(team[1])

        if len(A) == 26:
            break

    for a in A:
        print(a)


while True:
    n = int(raw_input())
    if n == 0:
        break
    solve(n)

Submission status: Accepted

Solution code:
def main():
    while True:
        n = int(input())
        if n == 0: break

        teams = []
        for i in range(n):
            teams.append(list(map(int, input().split())))
       
        def same_len(l):
            return len(list(filter(lambda x: x[1] == e[1], ans))) 

        ans = []
        rank = sorted(sorted(sorted(teams, key=lambda x: x[0]), key=lambda x: x[3]), key=lambda x: x[2], reverse=True) 
        for e in rank:
            if len(ans) < 10 and same_len(ans) < 3:
                ans.append(e)
            elif len(ans) < 20 and same_len(ans) < 2:
                ans.append(e)
            elif len(ans) < 26 and same_len(ans) == 0:
                ans.append(e)

        for a in ans:
            print(a[0])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:break
    p = [tuple(map(int, input().split())) for _ in range(n)]
    p.sort()
    p.sort(key = lambda x:x[3])
    p.sort(key = lambda x:x[2], reverse = True)
    s = 0
    sg = {}
    for i in p:
        if s < 10:
            try:
                if sg[i[1]] < 3:
                    print(i[0])
                    s += 1
                    sg[i[1]] += 1
            except:
                sg[i[1]] = 1
                print(i[0])
                s += 1
        elif s < 20:
            try:
                if sg[i[1]] < 2:
                    print(i[0])
                    s += 1
                    sg[i[1]] += 1
            except:
                sg[i[1]] = 1
                print(i[0])
                s += 1
        elif s < 26:
            if i[1] not in sg:
                sg[i[1]] = 1
                print(i[0])
                s += 1

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
    n=input()
    if n==0:break
    L,T=[],[]
    dic=defaultdict(int)
    for i in range(n):
        ID,U,A,P=map(int,raw_input().split())
        L.append((-A,P,ID,U))
    L.sort()

    for A,P,ID,U in L:
        if len(T)<10:
            if dic[U]<3:
                T.append(ID)
                dic[U]+=1
        elif len(T)<20:
            if dic[U]<2:
                T.append(ID)
                dic[U]+=1
        elif len(T)<26:
            if dic[U]<1:
                T.append(ID)
                dic[U]+=1
    print "\n".join(map(str,T))

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if n==0:break
    t=[map(int,raw_input().split()) for i in [1]*n]
    t=sorted(sorted(sorted(t),key=lambda x:x[3])[::-1],key=lambda x:x[2])[::-1]
    u=[0 for i in range(1001)]
    s=0
    for i in t:
    	if (s<10 and u[i[1]]<3) or (s<20 and u[i[1]]<2) or (s<26 and u[i[1]]<1):
    		print i[0]
    		u[i[1]]+=1
    		s+=1

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if n==0:break
    t=[map(int,raw_input().split()) for i in [1]*n]
    t=sorted(sorted(sorted(t),key=lambda x:x[3])[::-1],key=lambda x:x[2])[::-1]
    u=[0]*1001
    s=0
    for i in t:
        if (s<10 and u[i[1]]<3) or (s<20 and u[i[1]]<2) or (s<26 and u[i[1]]<1):
            print i[0]
            u[i[1]]+=1
            s+=1

Submission status: Accepted

Solution code:
while 1:
    in_tmp = input()
    if (in_tmp == "0"):
        break
    list_team = []
    for i in range(int(in_tmp)):
        list_team.append(list(map(int,input().split())))
    list_sorted = sorted(list_team, key=lambda x:(-x[2], x[3], x[0]))
    
    cnt_passed = 0
    dict_passed = {}
    for item in list_sorted:
        if (item[1] not in dict_passed.keys()):
            dict_passed[item[1]] = 0
        if (cnt_passed < 10):
            if(dict_passed[item[1]] < 3):
                print(item[0])
                dict_passed[item[1]] += 1
                cnt_passed += 1
        elif (cnt_passed < 20):
            if(dict_passed[item[1]] < 2):
                print(item[0])
                dict_passed[item[1]] += 1
                cnt_passed += 1
        elif (cnt_passed < 26):
            if(dict_passed[item[1]] < 1):
                print(item[0])
                dict_passed[item[1]] += 1
                cnt_passed += 1
        else:
            break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter

while 1:
  n = int(stdin.readline().rstrip())
  if n == 0:
    break
  teams = []
  #選抜されたチーム
  Selected_team_id = []
  cnt_selected_teams = 0
  #所属ごとのランキング（所属ごとの選抜チーム数）
  dic_shozoku_and_cntSelected = {}

  for i in range(n):
    * t, = map(int, stdin.readline().split())
    teams.append(t)
    if not dic_shozoku_and_cntSelected.__contains__(t[1]):
      dic_shozoku_and_cntSelected[t[1]] = 0

  sorted_teams1 = sorted(teams, key=itemgetter(3, 0))  # ペナルティ、ID
  sorted_teams = sorted(sorted_teams1, key=itemgetter(2), reverse=True)  # 正解数
  for t in sorted_teams:
    cnt_same_shozoku = dic_shozoku_and_cntSelected[t[1]]
    if cnt_selected_teams < 10:
      if cnt_same_shozoku < 3:
        Selected_team_id.append(t[0])
        dic_shozoku_and_cntSelected[t[1]] += 1
        cnt_selected_teams += 1
    elif cnt_selected_teams < 20:
      if cnt_same_shozoku < 2:
        Selected_team_id.append(t[0])
        dic_shozoku_and_cntSelected[t[1]] += 1
        cnt_selected_teams += 1
    elif cnt_selected_teams < 26:
      if cnt_same_shozoku < 1:
        Selected_team_id.append(t[0])
        dic_shozoku_and_cntSelected[t[1]] += 1
        cnt_selected_teams += 1

  print("\n".join(map(str,Selected_team_id)))

Submission status: Accepted

Solution code:
while True :
    n = int(input())
    if n == 0 :
        break
    
    Team = [list(map(int, input().split())) for i in range(n)]
    Team.sort(key=lambda x: (-x[2], x[3], x[0]))
    
    Senbatsu_Syozoku = [0] * 1001
    Senbatsu_amount = 0
    for i in range(n) :
        if Senbatsu_amount < 10 and Senbatsu_Syozoku[Team[i][1]] < 3 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])
        elif Senbatsu_amount < 20 and Senbatsu_Syozoku[Team[i][1]] < 2 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])
        elif Senbatsu_amount < 26 and Senbatsu_Syozoku[Team[i][1]] == 0 :
            Senbatsu_amount += 1
            Senbatsu_Syozoku[Team[i][1]] += 1
            print(Team[i][0])

Submission status: Accepted

Solution code:
def team_sort(teams, n):
    for i in range(n - 1):
        #print(i)
        for j in range(n - i - 1):
            #print(i, j, teams[j][2], teams[j+1][2])
            if (teams[j][2] < teams[j + 1][2]):
                tmp = teams[j]
                teams[j] = teams[j+1]
                teams[j+1] = tmp
            elif (teams[j][2] == teams[j + 1][2]):
                if (teams[j][3] > teams[j + 1][3]):
                    tmp = teams[j]
                    teams[j] = teams[j+1]
                    teams[j+1] = tmp
                elif (teams[j][3] == teams[j + 1][3]) and (teams[j][0] > teams[j + 1][0]):
                    tmp = teams[j]
                    teams[j] = teams[j+1]
                    teams[j+1] = tmp

def select(teams):
    selection = []
    count = {}
    for t in teams:
        g = str(t[1])
        count.setdefault(g, 0)
        #print(t)
            
        if len(selection) < 10:
            if (count[g] < 3):
                selection.append(t)
                count[g] += 1
        
        elif len(selection) < 20:
            if (count[g] < 2):
                selection.append(t)
                count[g] += 1
        
        elif len(selection) < 26:
            if (count[g] < 1):
                selection.append(t)
                count[g] += 1
    #print('selection', selection)
    
    for t in selection:
        print(t[0])

while True:
    n = int(input())
    
    if (n == 0):
        break
    
    teams = []
    
    for i in range(n):
         t = [int(x) for x in input().split()]
         teams.append(t)
    #print(teams)
    team_sort(teams, n)
    #print('sorted', teams)
    select(teams)

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    data = []
    for _ in range(n):
        i, u, a, p = map(int, input().split())
        data.append([i, u, a, p])

    data = sorted(data, key=lambda x: (-x[2], x[3], x[0]))
    union = [0] * 1001

    cnt = 0
    for d in data:
        i, u, a, p = d
        if cnt < 10 and union[u] < 3:
            print(i)
            cnt += 1
            union[u] += 1
        elif cnt < 20 and union[u] < 2:
            print(i)
            cnt += 1
            union[u] += 1
        elif cnt < 26 and union[u] < 1:
            print(i)
            cnt += 1
            union[u] += 1

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
  n = int(input())
  if n == 0:
    break
  teams = []
  for _ in range(n):
    i, u, a, p = map(int, input().split())
    teams.append((-a, p, i, u))
  teams.sort()
  
  u_counter = defaultdict(int)
  all_counter = 0
  selected = []
  for _, _, i, u in teams:
    if all_counter < 10 and u_counter[u] < 3 or\
       all_counter < 20 and u_counter[u] < 2 or\
       all_counter < 26 and u_counter[u] < 1:
       u_counter[u] += 1
       all_counter += 1
       selected.append(i)
  
  [print(s) for s in selected]

Submission status: Runtime Error

Solution code:
def sort_cmp(x, y):
    if x[2] == y[2]:
        return x[3] < y[3]
    else:
        return x[2] > x[2]


def solve(n):
    teams = []
    for i in range(n):
        teams.append(list(map(int, input().split())))

    teams = sorted(teams, key=lambda x: -1e12 * x[2] + x[3] * 1e6 + x[0])

    A = []
    B = []
    threshold = 3
    for team in teams:
        if len(A) == 10:
            threshold = 2
        elif len(A) == 20:
            threshold = 1e8

        if B.count(team[1]) < threshold:
            A.append(team[0])
            B.append(team[1])

        if len(A) == 26:
            break

    for a in A:
        print(a)


while True:
    n = int(input())
    if n == 0:
        break
    solve(n)