Problem:


Problem C: カードゲーム

ねこのゲイツとジャッキーは、2人で遊ぶカードゲームのルールを考えた。そのルールとは次のようなものである。

まず、1から18の数字が書かれたカードをシャッフルし、それぞれのプレーヤーに9枚ずつ配る。両者は同時に1枚のカードを同時に出し、その値によってスコアを得る。値の大きいカードを出したプレーヤーは、大きい方の値と小さい方の値の和を自分のスコアに加える。その際、値の小さいカードを出したプレーヤーはスコアを得られない。また、一度場に出されたカードは二度と使うことはできない。カードをすべて使い終わった後にスコアが大きかったプレーヤーの勝ちとする。

ゲイツとジャッキーは互いに無作為にカードを選んで出してみることにした。最初に配られたカードが与えられたとき、ゲイツとジャッキーが勝つ確率をそれぞれ求めよ。

Input

ゲイツ、ジャッキーそれぞれの手札は、9個の整数からなる。両プレーヤーの手札は1から18までの互いに異なる整数である。入力の1行目にはゲイツの手札を表す9個の整数が与えられ、2行目にはジャッキーの手札を表す9個の整数が与えられる。整数と整数の間は空白1個で区切られる。

Output

ゲイツ、ジャッキーが勝つ確率をそれぞれ、スペースで区切って小数点以下5桁まで出力せよ。 10-5 以内の誤差は許容されるが、0未満あるいは1を越える値を出力してはならない。

Notes on Submission

上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。

Sample Input

2
1 3 5 7 9 11 13 15 17
2 4 6 8 10 12 14 16 18
1 5 7 9 11 13 15 17 18
2 3 4 6 8 10 12 14 16

Output for the Sample Input

0.30891 0.69109
0.92747 0.07253



Sample input:
2
1 3 5 7 9 11 13 15 17
2 4 6 8 10 12 14 16 18
1 5 7 9 11 13 15 17 18
2 3 4 6 8 10 12 14 16


Sample output:
0.30891 0.69109
0.92747 0.07253

Submission status: Wrong Answer

Solution code:
import math
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(sorted(map(int, input().split()), reverse = True)), tuple(sorted(map(int, input().split())))
    c = 0
    q = {():(0, 0)}
    for i in range(9):
        nq = {}
        for k in q:
            for j in b:
                if j not in k:
                    x = q[k][0] + (a[i] + j) * (a[i] > j)
                    y = q[k][1] + (a[i] + j) * (a[i] < j)
                    if x > 85:c += math.factorial(9 - i - 1)
                    elif y < 85:nq[tuple(list(k) + [j])] = (x, y)
        q = nq
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP)))

Submission status: Wrong Answer

Solution code:
import math
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(sorted(map(int, input().split()), reverse = True)), tuple(sorted(map(int, input().split())))
    c = 0
    q = {():(0, 0)}
    for i in range(9):
        nq = {}
        for k in q:
            for j in b:
                if j not in k:
                    x = q[k][0] + (a[i] + j) * (a[i] > j)
                    y = q[k][1] + (a[i] + j) * (a[i] < j)
                    if x > 85:c += math.factorial(9 - i - 1)
                    elif y < 85:nq[tuple(list(k) + [j])] = (x, y)
        q = nq
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP)))

Submission status: Accepted

Solution code:
from itertools import permutations as pm

def main():
  t = int(input())
  fact9 = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2
  for _ in range(t):
    l1 = list(map(int, input().split()))
    l2 = list(map(int, input().split()))
    ans1 = 0
    ans2 = 0
    for hand in pm(l2, 9):
      score1 = 0
      score2 = 0
      for i, j in zip(l1, hand):
        if i < j:
          score2 += (i + j)
        else:
          score1 += (i + j)
      if score1 < score2:
        ans2 += 1
      elif score1 > score2:
        ans1 += 1
    print(ans1 / fact9, ans2 / fact9)

main()

Submission status: Accepted

Solution code:
import math
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(sorted(map(int, input().split()), reverse = True)), tuple(sorted(map(int, input().split())))
    c = 0
    q = {():(0, 0)}
    for i in range(9):
        nq = {}
        for k in q:
            for j in b:
                if j not in k:
                    x = q[k][0] + (a[i] + j) * (a[i] > j)
                    y = q[k][1] + (a[i] + j) * (a[i] < j)
                    if x > 85:c += math.factorial(9 - i - 1)
                    elif y < 86:nq[tuple(list(k) + [j])] = (x, y)
        q = nq
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.000001'), rounding=ROUND_HALF_UP)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
for loop in range(n):
    A = map(int, raw_input().split())
    B = map(int, raw_input().split())
    cnt = 0
    for p in it.permutations(A):
        cnt += sum(p[i] + B[i] for i in range(9) if p[i] > B[i]) > 85
    ans = float(cnt) / 362880
    print "%.5f %.5f" % (ans, 1 - ans)

Submission status: Runtime Error

Solution code:
import itertools
from decimal import Decimal, ROUND_HALF_UP
for _ in range(int(input())):
    a, b = tuple(map(int, input().split())), tuple(map(int, input().split()))
    c = 0
    for i in itertools.permutations(b):
        s = 0
        for j in range(9):s += (a[j] + i[j]) * (a[j] > i[j])
        if s > 85:c += 1
    c /= 362880
    print("{} {}".format(Decimal(c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP), Decimal(1 - c).quantize(Decimal('0.00001'), rounding=ROUND_HALF_UP)))