题目大意【这题充当面试题完全没有问题!!】
在你不知道哪个词比哪个词大,但机器人知道答案的情况下,和机器人大战“词语比大小”100回合(每回合胜利可以拿一分),想一个策略能够在随机情况下稳定拿到25分(答对半题)以上,和50分(全部答对)吧!
Problem
Finally, you are face to face with the leader of the alien robots! You have managed to distract it with its favorite word game, while your fellow Resistance members try to shut down the robots’ power supply.
The game uses the robot language, which is made up of 105 words: the set of all five-letter strings made up of uppercase English letters between A and J, inclusive. For example, AAAAA, FGHIJ, and BEIGE are among the valid words.
You know that these words have a rank order, with no ties, such that a higher-ranked word beats any lower-ranked word, with the one exception that the lowest-ranked word beats the highest-ranked word. Unfortunately, you do not know the rank order of the words in the robot language!
The game has the following rules:
Turn 0: You start by naming a word W0.
Turn 1: The robot names a word W1. If W1 beats W0, the robot scores a point.
This continues; on turn i, the active player is you if i is even, or the robot if i is odd. The active player names a word Wi and scores a point if Wi beats Wi-1. (If the two words are the same, no point is scored.) The score is not announced — in particular, you will not know whether each of your words has scored a point!
This continues for a total of 201 turns.
Notice that you get the last turn (naming W200), and that at the end of that turn, each player’s score is between 0 and 100, inclusive.
Thanks to some great work by the Resistance’s spies, you know the strategy that the robot will use for every turn of the game. It only cares about scoring 100 points, so on every turn, it will choose a word uniformly at random from all possible words that will score a point on that turn, and independently of all of its previous word choices. The robot knows the rank order of the language, so it has no trouble choosing words!
If you do not score at least N points, the robot will become bored and stop playing with you, so your plan (and the universe) will be doomed!
Limits
1 ≤ T ≤ 50.
Time limit: 40 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
Wi is five characters long and consists only of characters in the set of uppercase letters ABCDEFGHIJ, for all odd i. (The robot plays valid words.)
Test set 1 (Visible)
N = 25.
Test set 2 (Visible)
N = 50.
//稳定拿25以上的方法
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int T,n;
cin>>T>>n;
string w="AAAAA";
for(int i=0;i<T;i++){
cout<<w<<endl;
string wb,wl;
for(int j=1;j<=100;j++){
if(j%2){
cin>>wb;
cout<<w<<endl;
}else{
cin>>wl;
cout<<wb<<endl;
}
}
}
return 0;
}