| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13672 | Fibonacci's soup |
|
| 14481 | Take 6! II |
|
Description
Fibonacci's soup is one of the most well-known recipe in Fibonacci's hometown. Besides making soup, Fibonacci also enjoys seeking weird sequences.
Today, Fibonacci has discovered a new sequence called "DFS", which is the "Double Fibonacci Sequence". The following is the formula for the sequence:
Input
The input contains one line: nonnegative integers a, b, c, d and n.
a, b, c, d ≤ 100, n ≤ 50
Output
Output one line, including fn and gn.
Please remember to print '\n' at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
"Take 6" (also known as "6 Nimmt!") is a card game consisting of 104 cards, each with a number (ranging from 1 to 104) and a certain number of cattle head symbols. The number of cattle headson a card varies, with higher-numbered cards typically carrying more cattle heads. Players aim to finish the game with the fewest cattle heads, as each cattle head counts as a penalty point. The game is played in rounds.
Each card in the game has a certain number of "cattle heads" (penalty points). The distribution of cattle heads across the cards is as follows:
- 1 card with 7 cattle heads—number 55
- 8 cards with 5 cattle heads—multiples of 11 (except 55): 11, 22, 33, 44, 66, 77, 88, 99
- 10 cards with 3 cattle heads—multiples of ten: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
- 9 cards with 2 cattle heads—multiples of five that are not multiples of ten (except 55): 5, 15, 25, 35, 45, 65, 75, 85, 95
- 76 cards with 1 cattle head—the rest of the cards from 1 through 104
After seeing the homework problem, Temmie realized that he had no friends, so he decided to play the game "Take 6!" by himself.
Game Rules
- Temmie has M cards, and the game consists of M rounds.
- The game starts with P rows of cards, each row beginning with a single starting card.
- During each round:
- Temmie selects a card to play.
- Temmie places the card in one of the P rows, choosing a position where the card's value is closest to either the first or the last card in that row (whichever is closer in value). Each row has cards arranged in ascending order. Temmie must place the card in a position such that the row remains in ascending order after placement.
- If there are two possible positions, Temmie places the card at the position towards the end of the row.
- If the row where the card is placed already contains five cards, Temmie must take all five cards from that row (as a penalty) and place the played card as the new first card in that row.
- Although in reality, it might be possible that Temmie's card cannot be placed in any valid position, the problem guarantees that this won't happen.
- The game continues until Temmie has played all of his cards.
Input
The first line contains two integers, M and P, representing the number of cards Temmie holds and the number of rows on the table.
The next P lines each contain one integer Di , representing the initial card of row i .
The next line contains M integers, C1 , C2 , ... , CM , where Ci represents the card Temmie plays in the i -th round.
Constraints
- 1 ≤ M ≤ 100
- 1 ≤ P ≤ 4
- 1 ≤ Di , Ci,j ≤ M + P
- for all (i, j) , Di ≠ Cj
- It is guaranteed that every card Temmie plays has at least one valid position where it can be placed.
Subtasks
- Testcases 1~3: P = 1 , D1 = 1 , and Temmie’s cards are played in a strictly increasing order.
- Testcases 4~6: Each card Temmie plays is guaranteed not to be placed at the front of the row.
- Testcases 7~8: P = 1
- Testcases 9~10: No additional restrictions.
Hint: You only need to modify the code for the homework by setting N = 1, and you will be able to pass Testcases 1 ~ 6.
Output
Output a single integer representing the total number of cattle heads that Temmie ends up with.
Sample explanation (Click to open)
At the beginning, there are 2 rows of cards on the table, with 7 and 12 respectively.
In the first round, Temmie drew the card 6. Among the two rows, the number closest to 6 at the head or tail of each row is 7, and 6 < 7, so 6 is placed in front of 7.
In the second round, Temmie drew the card 5. Among the two rows, the number closest to 5 at the head or tail of each row is 6, and 5 < 6, so 5 is placed in front of 6.
In the third round, Temmie drew the card 4. Among the two rows, the number closest to 4 at the head or tail of each row is 5, and 4 < 5, so 4 is placed in front of 5.
In the fourth round, Temmie drew the card 8. Among the two rows, the number closest to 8 at the head or tail of each row is 7, and 8 > 7, so 8 is placed after 7.
In the fifth round, Temmie drew the card 11. Among the two rows, the number closest to 11 at the head or tail of each row is 12, and 11 < 12, so 11 is placed in front of 12.
In the sixth round, Temmie drew the card 3. Among the two rows, the number closest to 3 at the head or tail of each row is 4, and 3 < 4, so 3 is placed in front of 4.
However, since 3 is the 6th card placed in the first row, as a penalty, Temmie has to take away the first five cards placed in that row, and she gained 6 cattle heads. The 6th card placed, 3, becomes the new beginning of that row.
In the seventh round, Temmie drew the card 2. Among the two rows, the number closest to 2 at the head or tail of each row is 3, and 2 < 3, so 2 is placed in front of 3.
In the eighth round, Temmie drew the card 10. Among the two rows, the number closest to 10 at the head or tail of each row is 11, and 10 < 11, so 10 is placed in front of 11.
In the ninth round, Temmie drew the card 1. Among the two rows, the number closest to 1 at the head or tail of each row is 2, and 1 < 2, so 1 is placed in front of 2.
In the tenth round, Temmie drew the card 9. Among the two rows, the number closest to 9 at the head or tail of each row is 10, and 9 < 10, so 9 is placed in front of 10.
In the end, Temmie gained a total of 6 cattle heads.