# Game Simulator

问题描述 :

The whole game contains a number of rounds. In each round, one team is called **“Declarers” (CT)**; the other team is called **“Defenders” (FT)**. Each team has a **current rank (CR)**. The goal of the player is to increase his own team’s CR as much as possible.

A certain round has a **Main Suit** (Heart – H, Spade – S, Club – C, Diamond – D, or ** None – no main suit** in this round) and its CR. The CR in this round is the CR of the CT, and Main Suit will be given. The Main Suit and CR will be used to determine the order of the cards.

** Cards ranked 5, 10, King value 5, 10, 10 pts (points) respectively, all other cards value 0 pts**. In one round, we only consider the FT’s pts. The rules of getting pts for FT will be discussed later.

If the FT gets less than 80 pts in one round, they will hold be FT in the next round. This situation is called **“make”**. Otherwise, they become CT in the next round and the original CT become FT instead. This situation is called **“down”**.

If the FT gets 0 pts, the CR of the current CT will be increased by 3, for example, if the CR of the CT is 9, it will become Queen (12). Otherwise, if the FT gets less than 40 pts, the CR of the CT will be increased by 2. Otherwise, if the FT gets less than 80 pts, the CR of the CT will be increased by 1. Otherwise, if the FT gets not less than *80 + k * 40* pts and less than *120 + k * 40* pts, the CR of the current FT will be increased by k. For example, if the FT gets 255 pts in a round, the CR of the current FT will be increased by 4; and if the FT gets 80 pts, both teams’ CR remain unchanged. If a team’s CR becomes ** beyond Ace**, this team is considered the WINNER of the whole game.

During a round, one of the players in CT is called the **dealer**. If “make”, the pard (teammate) of the dealer becomes the next round’s dealer. Otherwise (“down”), the player on dealer’s right-hand side becomes the dealer of the next round. For example, if the dealer of the current round is Alice and her team (CT) is “down”, the dealer of the next round should be Bob (on Alice’s right-hand side).

At the start of a round, each of the players except the dealer gets exactly 25 cards; the dealer gets all the remaining 33 cards. After that, the dealer chooses 8 of his cards and gives them to the judge, and these cards are called **“hidden cards”**.

Now each player has exactly 25 cards. A round consists of several **tricks**. In the first trick, the dealer plays one or more cards (called **“lead”**), then, in clockwise order, players play the same number of cards as the first player one by one (called **“follow”**). The winner of the current trick leads cards during the next trick, and so on. *If the winner of the current trick is a member of FT, then the FT gets the sum of the cards’ pts played in this trick.*

Now we start to describe how to determine the winner of a trick. After the main suit and the CR of the current round are fixed, we can determine the **“trumps”** which are cards with main suit or CR (Current Rank), and the Jokers. All other cards are **“not-trumps”**.

We can have an order among all the cards according the following rules:

- (1) “Trumps” are ordered higher than “not-trumps”.

(2) For the trumps, the order are listed below:

Red Joker

Black Joker

card with main suit and CR (if exists)

other card with CR

other trumps ordered by their ranks(i.e., A, K, Q, J, T, 9, 8, 7, …, 3, 2)

(3) For the “not-trumps”, they are ordered by their ranks.

*Assume in all the description below, in the current round, the CR of the CT is 7.*

Suppose the main suit is H, the cards can be arranged in this order (as an example):

**S2 , C2 , D2< S3 , C3 , D3< S4 , C4 , D4< S5 , C5 , D5< S6 , C6 , D6< S8 , C8 , D8< S9 , C9 , D9< ST , FT , CT (T – 10)< SJ , CJ , DJ (J – Jack)< SQ , CQ , DQ (Q – Queen)< SK , CK , DK (K – King)< SA , CA , DA (A – Ace)**

< H2

< H3

< H4

< H5

< H6

< H8

< H9

< HT

< HJ

< HQ

< HK

< HA

< S7 = C7 = D7

< H7

< BJ (the Black Joker)

< RJ (the Red Joker)

If “None” during this round, then the pokers can be arranged in this order:

**H2 , S2 , C2 , D2< H3 , S3 , C3 , D3< H4 , S4 , C4 , D4< H5 , S5 , C5 , D5< H6 , S6 , C6 , D6< H8 , S8 , C8 , D8< H9 , S9 , C9 , D9< HT , ST , FT , CT< HJ , SJ , CJ , DJ< HQ , SQ , CQ , DQ< HK , SK , CK , DK< HA , SA , CA , DA**

< H7 = S7 = C7 = D7

< BJ

< RJ

In these two tables, ** cards written in italic** are “trumps”, and

**are “not-trumps”.**

*cards written in boldface*In each trick, the **lead cards** (played by the player leading this trick) must be either all “trumps”, or all “not-trumps” with same suit.

The possible **structures** of the cards are listed below (** assume the main suit is H and main rank is 7 for the example**):

**Single**. A single card, such as D9.

**Pair**. Two same cards, such as D9D9. But D7S7 is not a pair although their orders are the same.

**Tractor**. Two or more consecutive-ordered pairs, satisfying the condition that they are all “trumps”, or all “not-trumps” with same suit, such as SJSJSQSQSKSKSASA, H7H7S7S7HAHA or RJRJBJBJ. But, these are not tractors: S7S7C7C7 (their orders are the same), C7C7C6C6 (they are not consecutive-ordered), DADAD2D2 (Ace is not “one”, so they are not consecutive-ordered), H2H2H4H4, or D2D2D3. Be careful: if “None” in this round, H7H7S7S7HAHA is not a tractor (H7 and S7 are same-ordered because of “None”).

**Throw**. The combination of the structures above, satisfying the condition that they are all “trumps”, or all “not-trumps” with same suit. Each of the Single, Pair or Tractor in a Throw is one of the Throw’s component. In the original tractor game, in some situation, the throw will be rejected. But, to keep the rule simple, we assume in this problem all the throws are accepted. For example, RJRJBJBJH7H7HQHQHJHJH9H9H6H6HAH2 contains six components: two tractors, two pairs and two single cards (RJRJBJBJH7H7-HQHQHJHJ-H9H9-H6H6-HA-H2); CACAC8C8CK contains three components: two pairs and one single card(CACA-C8C8-CK).

A throw can be treated as different list of components, for example, H2H2H3H3H4H4H5H5H6H6 can also be treated as H2H2H3H3-H4H4H5H5H6H6, or H2H2-H3H3H4H4H4H5H5-H6H6, and so on. For the lead cards, each time we choose the longest component (choose the one with the highest order to break the tie) to construct a list of components, this list is the structure of the lead cards, also **the structure of the trick**. *So that the structure of the trick is unique.*

After the first player lead his or her cards, other players follow cards one by one in clockwise order, as mentioned above.

An important part of the game is to determine the winner of a trick:

If one’s follow cards contain both “trumps” and “not-trumps”, or all “not-trumps” but with different suits, this player can’t be winner of this trick.

Otherwise, if the lead cards are all “not-trumps” and one’s follow cards contain “not-trumps” with different suit from the lead cards, this follow player can’t be the winner of this trick.

Else, if one’s follow cards can’t be constructed as the same structure of lead cards, this player can’t be the winner of this trick either.

Otherwise, if the structure of this trick is not “throw”, the one who played the highest-ordered card wins this trick. If more than one player played the same highest-ordered card, *the winner of this trick will be the one who plays the highest-ordered card first.*

Now let’s consider the “throw” situation. We construct the follow cards into the structure of the lead cards, so that the order of the highest-ordered card in all the longest components of the “throw” is as high as possible (this card is called **“honor card”**). ** Note that tractor can be treated as several pairs or shorter tractors, and pair can be treated as two single cards.** The winner of this trick is the one who plays the highest-ordered “honor card”. Similarly, if more than one player played the same highest-ordered “honor card” the winner of this trick will be the one who plays the highest-ordered “honor card” first.

There are many hair-raising rules about lead and follow cards; fortunately, they’re not related to this problem, the only thing we care about is: when someone leads a “not-trump” “throw” the only possible way to beat it is to “throw” the same structure of “trumps”. And it’s impossible to beat a leading “trump” “throw”.

** Special attention on the examples below**. In these examples, Alice always leads cards. And assume in all the following examples, the CR is 7, and the main suit is H.

There is a special rule about “hidden cards”: if the winner of the last trick of a certain round is a member of FT, then, in addition, the FT gets the sum of the hidden cards’ pts, multiplied by 2

^{w}(2 to the power of

**w**).

*When the structure of the final trick is not “throw”, then***w**

*is the number of lead cards of the last trick of this round. If the structure is “throw” instead,***w**

**in the example RJRJBJBJH7H7HQHQHJHJH6H6HA, the**

*is the length of the longest components,***w**is 6 because the length of RJRJBJBJH7H7 (the longest components of the “throw”) is 6.

To make the problem easier, you are only to write a single-round tractor game simulator.

输入:

**T**is given in the very first line.

For each test case:

The first line contains the main suit of this round (H, S, C, D, O; O denotes “None” in this round), the dealer of this round, the CR of team 1, the CR of team 2, separated by single spaces. Each of the rest lines contains 4 strings: the lead cards and the cards played by the second, third and last player. In one string, the cards can be given in any order. Each player will play exactly 25 cards in one round.

You may assume the input is always valid.

There is a blank line between consecutive test cases, and a blank line also appears between **T** and the first test case.

输出:

**T**is given in the very first line.

For each test case:

The first line contains the main suit of this round (H, S, C, D, O; O denotes “None” in this round), the dealer of this round, the CR of team 1, the CR of team 2, separated by single spaces. Each of the rest lines contains 4 strings: the lead cards and the cards played by the second, third and last player. In one string, the cards can be given in any order. Each player will play exactly 25 cards in one round.

You may assume the input is always valid.

There is a blank line between consecutive test cases, and a blank line also appears between **T** and the first test case.

样例输入:

1 O Charles 2 2 S6S6S7S7 SASKSJST STS8S4S4 S3S5SJSQ S9S9 H3D3 S3DT SAD3 DA DQ DK D4 SKS8S5S3 RJC2D2H2 C6C8CJD9 H3CKDTD5 H7H7 H6H4 HJHQ H9H9 DJDJ DKH5 D5D4 D6D6 D8D8 C4C3 HTH5 D9D7 C5C5 C6CT H8HQ C7C4 H8 C7 HA HA H2 RJ BJ CK DA BJ C8 HK S2S2C2 CQCAD2 HTHJHK C9CQCA

样例输出:

Case #1: 50 3 2 Alice

很好，找的就是这一题

#include <cstdio>

int main() {

//answer must be odd

int n, u, d;

while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {

if(n<=u) { puts("1"); continue; }

n-=u; u-=d; n+=u-1; n/=u;

n<<=1, ++n;

printf("%dn",n);

}

return 0;

}

很好的题，还是能做出几道的，嘿嘿

算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

不错，赞一个！

约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

不错，再多来的CF上面的题

还是有些难度的！

刚开始学习，为啥会报错了

网站不错，支持一个

文章写得挺好，就是最后的斐波那契那个没有看明白

第一种方法怎么会是O(log(m+n))呢？没有二分的话直接遍历应该就是O(m+n)吧？

这个分析相当全面，经典！

第二个方法挺不错。NewHead代表新的头节点，通过递归找到最后一个节点之后，就把这个节点赋给NewHead，然后一直返回返回，中途这个值是没有变化的，一边返回一边把相应的指针方向颠倒，最后结束时返回新的头节点到主函数。