The inhabitants of a small Caribbean island in the region known as Bermuda's Triangle love to spend their warm summer nights playing cards. As a tribute to the region where they live, all of their card games have some connection to triangles. One of the most popular games in the island is known as Triples, and has very simple rules.
The game is played between two players, with a set of standard playing cards. Cards are distinguished only by their values, from 1 (Ace) to 13 (King). The cards are shuffled and placed as a pile in the center of the table, face down. This pile is called the stock. The two players take turns at playing. At each turn, a player
●draws the top card from the stock, adding it to her/his hand; and
●decides whether she/he wants to "drop some triples"
Dropping a triple consists of choosing three cards (a triple) from the hand and placing them on the table, face up. The dropped triples stay on the table until the end of the game.
Only some sets of three cards form a valid triple. There are two types of valid triples:
●Perfect triples are made of three cards whose values represent the length of sides of an equilateral triangle;
●Common triples are made by three cards whose values represent the length of sides of any other (not equilateral) triangle.
The figure below shows examples of perfect triples (a), common triples (b), and invalid triples(c).
Only valid triples can be dropped, but a player may drop any number of triples at a given turn. In particular, since players know the number of cards in the stock at every turn, a player may decide to drop all triples in her/his last turn. Some players, however, normally drop some triples during the game, to maintain as few cards in their hands as possible.
The game finishes when the stock is empty. The winner is the player that dropped the largest number of perfect triples. If both players dropped the same number of perfect triples, the winner is the player that dropped the largest number of common triples. If both players dropped the same number of perfect triples and the same number of common triples, the result is a tie.
Given the description of the cards in the stock, write a program that determines the winner of a game of Triples, considering both players play as best as possible.
The input contains several test cases. The first line of a test case contains one integer N representing the number of cards in the stock (6 <= N <= 104). The next line contains N integers Xi, separated by single spaces, representing the cards in the stock (1 <= Xi <= 13, for 1 <= i <= N). The cards are given in the order they are drawn by the players: the first card in the input (X1) is the first card drawn, the second card in the input (X2) is the second card drawn, and so on. Several cards with the same value may be present in the stock, and not necessarily all card values are present in the stock. The end of input is indicated by N = 0.
For each test case your program must output a single line, containing '1'
if the first player to play wins the game, '2' if the second player wins, or '0' if there is a tie.
5 6 5 6 5 6 8
13 13 13 13 13 13 1 3 2 9 3 9
1 2 1 2 1 2 3 1 4 2 5 3
- 博客 大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了
- 博客 在中国程序员是青春饭吗？
- 博客 springboot+jwt实现token登陆权限认证
- 博客 技术大佬：我去，你写的 switch 语句也太老土了吧
- 博客 女程序员，为什么比男程序员少？？？
- 博客 总结了 150 余个神奇网站，你不来瞅瞅吗？
- 博客 副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
- 博客 MySQL数据库面试题（2020最新版）
- 博客 如果你是老板，你会不会踢了这样的员工？
- 博客 我入职阿里后，才知道原来简历这么写
- 博客 程序员写出这样的代码，能不挨骂吗？
- 博客 外包程序员的幸福生活
- 博客 优雅的替换if-else语句
- 博客 离职半年了，老东家又发 offer，回不回？
- 博客 2020阿里全球数学大赛：3万名高手、4道题、2天2夜未交卷
- 博客 为什么你不想学习？只想玩？人是如何一步一步废掉的
- 博客 男生更看重女生的身材脸蛋，还是思想？
- 博客 为什么程序员做外包会被瞧不起？
- 博客 当HR压你价，说你只值7K，你该怎么回答？
- 博客 面试：第十六章：Java中级开发
- 博客 早上躺尸，晚上干活：硅谷科技公司这么流行迟到？
- 博客 面试阿里p7，被按在地上摩擦，鬼知道我经历了什么？
- 博客 终于懂了TCP和UDP协议区别
- 博客 Python爬虫，高清美图我全都要（彼岸桌面壁纸）
- 博客 无代码时代来临，程序员如何保住饭碗？
- 博客 面试了一个 31 岁程序员，让我有所触动，30岁以上的程序员该何去何从？
- 博客 大三实习生，字节跳动面经分享，已拿Offer
- 博客 程序员垃圾简历长什么样？
- 博客 Java岗开发3年，公司临时抽查算法，离职后这几题我记一辈子
- 博客 大胆预测下未来5年的Web开发