ACM(四)—— python自带数据无限大真好

 

Intergalactic Bidding Gym – 101933I 

Today the Intergalactic Council of Pebble Coins (ICPC) conducted an intergalactic auction of the Neutronium Chaos Pebble Coin (NCPC). This coin, which was forged in the Ancient Coin Machine (ACM), is rumored to be the key to ruling the universe.

Due to the extremely competitive nature of the auction, as well as the odd mechanics of the intergalactic currency used (far too advanced for mere mortals to understand), the auction was conducted with the following rules:

  1. only one participant was allowed to make a bid at a time,
  2. each participant was only allowed to make one bid, and
  3. a participant making a bid had to bid at least twice the amount of the highest bid at the time.

The first participant making a bid was allowed to make a bid of any positive amount.

After the auction there were a lot of sore losers – understandably, having just lost their chance at world domination. To make the losers feel a little better and prevent possible rioting, the ICPC has decided to hold a lottery for the participants. The winners of the lottery are determined as follows. The ICPC picks a random number ss. A group of participants is called winning if the sum of their bets from the auction is equal to ss. A participant wins the lottery and receives a prize – a shiny Pebble Coin – if they belong to any winning group of participants.

Given the names of the participants, the bets that they made, and the random number ss chosen by the ICPC, help them determine which participants won the lottery.

Input

The first line of input contains two integers nn and ss, where 1n10001≤n≤1000 is the number of participants, and 1s<1010001≤s<101000 is the random number chosen by the ICPC.

Then follow nn lines describing the participants. Each line contains a string tt and an integer bb, where tt is the name of a participant, and 1b<1010001≤b<101000 is the amount of his bet. The name of each participant is unique and consists of between 11 and 2020 letters from the English alphabet.

Output

Output an integer kk denoting the number of participants that won the lottery. Then output kk lines containing the names of the participants that won the lottery, one per line, in any order.

Examples
Input
5 63
Vader 3
Voldemort 7
BorgQueen 20
Terminator 40
Megatron 101
Output
3
Terminator
BorgQueen
Vader
Input
4 1112
Blorg 10
Glorg 1000
Klorg 1
Zlorg 100
Output
0

 

python实现:

n,s=eval(input().replace(' ',','))
m=[]
for i in range(n):
    m.append(eval('"'+input().replace(' ','",')))
m=sorted(m,key=(lambda x:x[1]))
res=[]
for i in reversed(range(n)):
    if not s:break
    if m[i][1]<=s:
        res.append(m[i])
        s-=m[i][1]
if s:
    print(0)
else:
    print(len(res))
    for each in res:
        print(each[0])

1、本来挺简单的一道题,结果没有看到后面一位出价者的价格一定不小于前者的两倍,然后用暴力搜索就炸了(TLE),其实只要从后往前加,超了就扔掉,最后能恰好就行,不能就输出0.

2、这道题还有就是要大数计算,还有就是记得排序,python实在方便,不用自己写大数运算,关键字排序一行搞定

Leave a Reply

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据