COCI 2016/2017 - Contest 2 - Go

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 32M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mirko nhanh chóng chán trò chơi Jetpack Joyride và bắt đầu chơi trò Pokémon GO! trên điện thoại của mình. Một trong những điểm nhấn của trò chơi này là quá trình cường hóa của Pokémon.

Để cường hóa Pokémon thuộc loài ~P_i~, Mirko phải cung cấp ~K_i~ viên kẹo loại dành cho Pokémon loài này. Sau quá trình cường hóa của Pokémon đó, cậu nhận lại được ~2~ viên kẹo. Pokémon chỉ có thể cường hóa nhờ sự trợ giúp của loại kẹo dành cho loài của chúng.

Mirko có ~N~ loài Pokémon và ~M_i~ viên kẹo cho Pokémon thuộc loài ~P_i~ và cậu muốn biết tổng số Pokémon mà mình có thể cường hóa.

Cậu cũng muốn biết loài Pokémon nào có thể cường hóa nhiều lần nhất. Nếu có nhiều loài Pokémon như vậy, hãy in ra tên loài Pokémon có số Pokédex nhỏ nhất, với Pokédex là thứ tự xuất hiện trong Input của loài Pokémon đó.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 70)~ - số loài Pokémon.
  • ~2N~ dòng sau chứa ~N~ bộ dữ liệu, trong đó:
    • dòng thứ ~2i~ chứa xâu ~P_i~ dài không quá ~20~ ký tự, biểu diễn tên của loài Pokémon thứ ~i~;
    • dòng thứ ~2i + 1~ chứa các số nguyên ~K_i~ ~(12 \le K_i \le 400)~ và ~M_i~ ~(1 \le M_i \le 10^4)~ biểu diễn số kẹo cần thiết cho sự cường hóa của một Pokémon loài thứ ~i~ và tổng số kẹo mà Mirko có cho Pokémon loài này.

Output

  • Dòng đầu tiên in ra tổng số Pokémon mà Mirko có thể cường hóa.
  • Dòng thứ hai in ra tên loài Pokémon có thể cường hóa nhiều lần nhất.

Sample 1

Input
4
Caterpie
12 33
Weedle
12 42
Pidgey
12 47
Rattata
25 71
Output
14
Weedle
Giải thích:

Xét cách Mirko cường hóa Weedles: Đối với lần cường hóa đầu tiên, Mirko đã dùng hết ~12~ viên kẹo, nhưng nhận lại ~2~ viên, vì vậy cậu còn lại ~32~ ~(42-12+2)~ viên kẹo. Sau lần cường hóa thứ hai, cậu còn lại ~22~ viên kẹo. Sau lần cường hóa thứ ba, cậu chỉ còn ~12~ viên kẹo, đủ cho một lần cường hóa nữa. Bằng cách này, Mirko đã cường hóa ~4~ con Weedles.

Tương tự, chúng ta thấy rằng Mirko có thể cường hóa nhiều nhất ~3~ con Caterpies, ~4~ con Pidgeys và ~3~ Rattatas.

Trong số tất cả các loài Pokémon đã cường hóa, Weedle và Pidgey có số lần cường hóa nhiều nhất, nhưng số Pokédex của Weedle nhỏ hơn (nó xuất hiện sớm hơn trong Input), vì vậy đây là đáp án của cho câu hỏi thứ hai của Mirko.

Sample 2

Input
7
Bulbasaur
25 74
Ivysaur
100 83
Charmander
25 116
Charmeleon
100 32
Squirtle
25 1
Wartortle
100 173
Pikachu
50 154
Output
11
Charmander

Scoring

  • ~8~ test đầu có ~N = 3~
  • ~17~ test còn lại không có ràng buộc gì thêm
  • Với tất cả các test, mỗi dòng in ra chính xác sẽ nhận được ~50\%~ số điểm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.