A1339. [COCI-2016_2017-contest2]#2 Go
编程题
普及/提高-
知识点
题目描述
Mirko quickly got tired of Jetpack Joyride and started playing Pokémon GO! on his phone.
One of the curiosities of this game is the so-called evolution of Pokémon.
In order to evolve Pokémon of species Pi , Mirko must provide Ki candy intended for a Pokémon of that species. After the evolution of that Pokémon, he gets 2 candies back.
Pokémon can evolve only with the help of candy intended for their species.
Mirko has N species of Pokémon and Mi candy for Pokémon of species Pi and wants to know how many total Pokémon he can evolve.
He also wants to know which Pokémon can evolve the most number of times. If there are multiple such Pokémon, output the one with the smallest Pokédex number. In other words, the one that appears earliest in the input data.
One of the curiosities of this game is the so-called evolution of Pokémon.
In order to evolve Pokémon of species Pi , Mirko must provide Ki candy intended for a Pokémon of that species. After the evolution of that Pokémon, he gets 2 candies back.
Pokémon can evolve only with the help of candy intended for their species.
Mirko has N species of Pokémon and Mi candy for Pokémon of species Pi and wants to know how many total Pokémon he can evolve.
He also wants to know which Pokémon can evolve the most number of times. If there are multiple such Pokémon, output the one with the smallest Pokédex number. In other words, the one that appears earliest in the input data.
输入格式
The first line of input contains the integer N (1 ≤ N ≤ 70), the number of Pokémon species.
The following 2N lines contains N sets of data, wherein it holds:
● line 2i contains string Pi , 20 characters long at most, the name of the i^th Pokémon species;
● line 2i+1 contains integers Ki (12 ≤ Ki ≤ 400) and Mi (1 ≤ Mi ≤ 10^4 ), the number of candy necessary for the evolution of one Pokémon of the i th species and the total number of candy Mirko has for Pokémon of the i^th species
The following 2N lines contains N sets of data, wherein it holds:
● line 2i contains string Pi , 20 characters long at most, the name of the i^th Pokémon species;
● line 2i+1 contains integers Ki (12 ≤ Ki ≤ 400) and Mi (1 ≤ Mi ≤ 10^4 ), the number of candy necessary for the evolution of one Pokémon of the i th species and the total number of candy Mirko has for Pokémon of the i^th species
输出格式
The first line of output must contain the total number of Pokémon that Mirko can evolve.
The second line of output must contain the name of the Pokémon that can evolve the most number of times.
The second line of output must contain the name of the Pokémon that can evolve the most number of times.
输入输出样例
输入 #1
4 Caterpie 12 33 Weedle 12 42 Pidgey 12 47 Rattata 25 71
输出 #1
14 Weedle
输入 #2
7 Bulbasaur 25 74 Ivysaur 100 83 Charmander 25 116 Charmeleon 100 32 Squirtle 25 1 Wartortle 100 173 Pikachu 50 154
输出 #2
11 Charmander
说明/提示
In test cases worth 16 points total, it will hold N = 3.
The first line of output will count towards 50% of points for that test case.
The second line of output will count towards 50% of points for that test case.
Clarification of the first test case: Let’s describe how Mirko evolved Weedles. For Weedles’ first evolution, Mirko spent 12 candy, but got
back 2, so he has 32 candy left (42-12+2). After the second evolution, he is left with 22 candy. After the
third evolution, he had 12 candy, which was enough for just one more evolution. This way, Mirko evolved
4 Weedles.
Similarly, we see that Mirko can evolve at most 3 Caterpies, 4 Pidgeys and 3 Rattatas.
Out of all Pokémon, Weedle and Pidgey evolved the most number of times, but Weedle’s Pokédex
number is smaller (it appears earlier in the input data), so it is the solution of the second part of the task.
The first line of output will count towards 50% of points for that test case.
The second line of output will count towards 50% of points for that test case.
Clarification of the first test case: Let’s describe how Mirko evolved Weedles. For Weedles’ first evolution, Mirko spent 12 candy, but got
back 2, so he has 32 candy left (42-12+2). After the second evolution, he is left with 22 candy. After the
third evolution, he had 12 candy, which was enough for just one more evolution. This way, Mirko evolved
4 Weedles.
Similarly, we see that Mirko can evolve at most 3 Caterpies, 4 Pidgeys and 3 Rattatas.
Out of all Pokémon, Weedle and Pidgey evolved the most number of times, but Weedle’s Pokédex
number is smaller (it appears earlier in the input data), so it is the solution of the second part of the task.