Сүйікті оқушы

Ұпайлар: 1

Уақыт шектеуі: 1.0s

Жад шектеуі: 256M

Author:

Problem type

Спорттық бағдарламалау әлемінде әдетте екі форматтағы жарыстарды ажыратады: IOI (International Olympiad in Informatics) және ICPC (International Collegiate Programming Contest). Мысалы, «ЧРК» жарысы ICPC ережелері бойынша өткізіледі.

ICPC форматы:
- Жарысқа бірнеше адамнан тұратын командалар қатысады.
- Барлық есептер бірдей бағаланады (есеп не шешілген, не шешілмеген).
- Мақсат — шектеулі уақыт ішінде барынша көп есепті шешу.
- Шешілген есептердің саны бірдей болған жағдайда, жазасы (айып уақыты) аз команда жоғары орынға ие болады (дұрыс шешім үшін — контест басталған сәттен бастап саналған минуттар саны + әрбір қате жіберу үшін 20 минут айыппұл).
IOI форматы:
- Әрбір қатысушы жеке өнер көрсетеді.
- Әр есеп 100 баллмен бағаланады, жартылай шешімдер үшін аралық балл алуға болады (мысалы, 30, 70 балл және т.б.).
- Қатысушының қорытынды нәтижесі — әр есеп бойынша алған ең жоғары (максималды) ұпайлардың жиынтығы (есепте барлық жіберілген шешімдер ішінен тек ең үздік нәтиже ескеріледі).
- Жалпы ұпайлары тең болған қатысушылар сол орынды бөліседі.

Мысалы, бір оқу-жаттығу IOI-жарысына $N$ адам қатыссын, олардың нөмірлері $1$ -ден $n$ -ге дейін, ал сіздің нөміріңіз — $1$ . Жаттықтырушыңыз сізді бірінші орынға шығарғысы келеді, өйткені ол сізді ерекше жақсы көреді. Осы мақсатқа жету үшін жаттықтырушы қалаған қатысушының (қаласа — сіздің де) белгілі бір есеп бойынша барлық жіберілімдерін «ескермеуге» (толығымен жоюға) болады, сол жіберілімдер ешқашан болмағандай саналады. Бұл әрекет таңдалған қатысушы мен есеп үшін бір батырманы басу арқылы орындалады.

Жойылған шешімдер қайта есептеу кезінде ескерілмейді.

Сіздің қорытынды ұпайыңыз кез келген өзге қатысушының ұпайынан кем болмас үшін, батырманы неше рет ең аз басу керек?

Енгізу

Бірінші жолда $n$ және $q$ сандары беріледі ( $2 \leq n \leq 100, 1 \leq q \leq 1000$ ) — қатысушылар саны және жіберілімдер (посылок) саны.

Келесі $q$ жолдың әрқайсысында $3$ элемент (токен) бар: $i d$ , $P r o b$ , $s c o r e$ ( $1 \leq i d \leq n$ , $`A' \leq P r o b \leq `F'$ , $1 \leq s c o r e \leq 100$ ). Бұл «Қатысушы $i d$ $P r o b$ есебі үшін $s c o r e$ ұпай алғанын» білдіреді. Әрбір есеп 'A'-дан 'F'-ке дейінгі бас әріппен белгіленеді.

Шығару

Жалғыз санды шығарыңыз — сіз бірінші орынға шығу үшін ескермеуге (жоюға) қажет ең аз жіберілімдердің (посылок) санын көрсетіңіз.

Мысалдар

Енгізу 1

Көшіру

Жауап 1

Көшіру

Ескертпелер

Егер осылай жоюлардан кейін сізде және қарсыласыңызда тең ұпайлар қалатын болса, екеуіңіз де бірінші орынды бөлісесіздер, және бұл ресми түрде «жеңімпаз» болып саналу үшін жеткілікті.

Бірінші тесттік мысалда: $1$ -ші қатысушыда — $88$ ұпай, $2$ -ші қатысушыда — $196$ ұпай, $3$ -ші қатысушыда — $14 + 24 + 71 = 109$ ұпай, $4$ -ші қатысушыда — $88$ ұпай, $5$ -ші қатысушыда — $49$ ұпай. $3$ -ші қатысушының «C» есебін ескермеуге (жоюға), сондай-ақ $2$ -ші қатысушының «E» және «B» есептерін ескермеуге болады.

Пікірлер

from collections import defaultdict

def min_deletions_to_win(N, M, submissions, my_id):

Көшіру

# Қатысушылардың ең жақсы нәтижелерін сақтау
best_scores = defaultdict(lambda: defaultdict(int))

# Әр есептің әр қатысушы үшін ең жоғары ұпайын табу
for participant, problem, score in submissions:
    best_scores[participant][problem] = max(best_scores[participant][problem], score)

# Әр қатысушының жалпы ұпайларын есептеу
total_scores = {p: sum(scores.values()) for p, scores in best_scores.items()}
my_score = total_scores[my_id]

# Бізден жоғары тұрған қатысушыларды анықтау
higher_participants = [(p, total_scores[p]) for p in total_scores if total_scores[p] > my_score]

# Егер ешкім бізден жоғары болмаса, 0 қайтарылады
if not higher_participants:
    return 0

# (Ұпай айырмашылығы, есеп бойынша жіберілімдер) түрінде сақтаймыз
deletions = []
for p, score in higher_participants:
    diff = score - my_score  # Айырмашылық
    problem_scores = sorted(best_scores[p].values(), reverse=True)  # Үлкен ұпайларды бірінші жоямыз
    removed = 0
    for s in problem_scores:
        diff -= s
        removed += 1
        if diff <= 0:
            deletions.append(removed)
            break

return min(deletions)  # Ең аз жоюлар саны

Енгізу

N, M = map(int, input().split()) submissions = [input().split() for _ in range(M)] submissions = [(int(p), prob, int(s)) for p, prob, s in submissions] my_id = 1 # Сіздің қатысушы нөміріңіз

Жауапты шығару

print(min_deletions_to_win(N, M, submissions, my_id))