Under construction

Still being built. Things may change

Mahjong Tenpai

Interview

Time limit2sMemory limit1024 MB

Summary
Given 13 mahjong tiles, check whether the hand is in tenpai and list every tile kind that completes a valid 14-tile win.
Level

Medium5 of 10

Topics
Brute force, Backtracking, Implementation
Solved
No attempts yet

Problem

The mahjong in this problem may differ from real mahjong.

Mahjong is a game from China. Players repeatedly draw and discard tiles to form a specific shape. There are two kinds of tiles: number tiles and honor tiles. A number tile has a suit and a number. The suit is one of three kinds: sak, tong, or man. The number is from 1 to 9, so there are 27 kinds of number tiles. An honor tile has no number. Its kind is one of seven: East, South, West, North, White, Green, or Red. Each tile kind has 4 copies. So the game uses 136 tiles: 4 copies each of 1 to 9 sak, 1 to 9 tong, 1 to 9 man, East, South, West, North, White, Green, and Red.

At the start, a player holds 13 of the 136 tiles. When the player draws one of the remaining tiles and the 14 tiles form a valid combination, the player declares "tsumo" and wins. If the player cannot declare tsumo, the player discards a tile of choice, draws a new one, and repeats. A hand of 13 tiles is in the "tenpai" state if adding one more tile lets the player declare tsumo.

A valid set of 14 tiles splits into 1 pair and 4 sets. The pair is 2 identical tiles. Each set has 3 tiles and is either a "shuntsu" or a "kotsu". A shuntsu is 3 consecutive number tiles of the same suit. Honor tiles have no numbers, so they cannot form a shuntsu. A kotsu is 3 identical tiles.

There are two special valid combinations. "Chiitoitsu" is 7 pairs among the 14 tiles. A hand with 4 identical tiles does not count as chiitoitsu. "Kokushi musou" is made of 13 tiles: 1 and 9 of sak, 1 and 9 of man, 1 and 9 of tong, and all 7 honor tiles. The 14th tile is a duplicate of one of these 13 tiles.

Given 13 tiles in the tenpai state, find which tile kinds can be the last tile that completes the hand for tsumo.

Input

13 tiles are given, separated by spaces.

Sak tiles are written as s, tong tiles as t, and man tiles as m. The number is written before the letter. East is e, South is s, West is w, North is n, White is h, Green is b, and Red is j.

Output

If the given tiles are in the tenpai state, print tenpai on the first line. On the second line, print the number of tile kinds that complete the hand for tsumo. On the third line, print those tile kinds in lexicographic order, separated by spaces.

If the given tiles are not in the tenpai state, print no tenpai on the first line.

Hint

The lexicographic order is defined as follows.

If two strings have different lengths, append a special character that is smaller than every character to the end of the shorter string until the lengths are equal. If the lengths are equal, compare the characters from the first one. Skip equal characters. At the first different character, the string with the smaller character is smaller in lexicographic order.

Examples4

  1. Example 1

    Input
    1s 2s 3s 6s 7s 5t 6t 7t 7t 7t 7t 9m 9m
    
    Expected output
    tenpai
    2
    5s 8s
    
  2. Example 2

    Input
    w w s s n n h h b b j j 8s
    
    Expected output
    tenpai
    1
    8s
    
  3. Example 3

    Input
    1s 3s 5s 7s b b b j j j 7t 8t 9t
    
    Expected output
    no tenpai
    
  4. Example 4

    Input
    3s 3s 3s 3s 4s 4s 5s 5s 1t 2t 3t 3t 3t
    
    Expected output
    tenpai
    2
    3t 6s