CF293A.Weird Game

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Yaroslav, Andrey and Roman can play cubes for hours and hours. But the game is for three, so when Roman doesn't show up, Yaroslav and Andrey play another game.

Roman leaves a word for each of them. Each word consists of 2·n binary characters "0" or "1". After that the players start moving in turns. Yaroslav moves first. During a move, a player must choose an integer from 1 to 2·n, which hasn't been chosen by anybody up to that moment. Then the player takes a piece of paper and writes out the corresponding character from his string.

Let's represent Yaroslav's word as s = _s_1_s_2... s_2_n. Similarly, let's represent Andrey's word as t = _t_1_t_2... t_2_n. Then, if Yaroslav choose number k during his move, then he is going to write out character s__k on the piece of paper. Similarly, if Andrey choose number r during his move, then he is going to write out character t__r on the piece of paper.

The game finishes when no player can make a move. After the game is over, Yaroslav makes some integer from the characters written on his piece of paper (Yaroslav can arrange these characters as he wants). Andrey does the same. The resulting numbers can contain leading zeroes. The person with the largest number wins. If the numbers are equal, the game ends with a draw.

You are given two strings s and t. Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.

亚罗斯拉夫、安德烈和罗曼可以连续数小时玩积木游戏。但该游戏需要三人参与,因此当罗曼缺席时,亚罗斯拉夫和安德烈便改玩另一个游戏。

罗曼分别为他们留下一个单词。每个单词均由 2⋅n2\cdot n 个二进制字符“0”或“1”组成。随后,两名玩家轮流进行操作,亚罗斯拉夫先手。在每次操作中,玩家必须从 11 到 2⋅n2\cdot n 中选择一个此前尚未被任一玩家选过的整数,然后在一张纸上写下自己字符串中对应位置的字符。

设亚罗斯拉夫的单词为 s=s1s2…s2ns = s_1 s_2 \dots s_{2n},安德烈的单词为 t=t1t2…t2nt = t_1 t_2 \dots t_{2n}。若亚罗斯拉夫在某次操作中选择了数字 kk,则他在纸上写下字符 sks_k;类似地,若安德烈在某次操作中选择了数字 rr,则他在纸上写下字符 trt_r。

当双方均无法再进行操作时,游戏结束。游戏结束后,亚罗斯拉夫可任意排列自己纸上所写的所有字符,构成一个整数;安德烈也做同样的事。所得整数允许包含前导零。数值较大者获胜;若两数相等,则游戏以平局告终。

现给定两个字符串 ss 和 tt,假设亚罗斯拉夫与安德烈均以最优策略进行游戏,请判断游戏结果。

输入格式

The first line contains integer n (1 ≤ n ≤ 106). The second line contains string s — Yaroslav's word. The third line contains string t — Andrey's word.

It is guaranteed that both words consist of 2·n characters "0" and "1".

第一行包含一个整数 nn(1 ≤ n ≤ 1061 \leq n \leq 10^6)。
第二行包含字符串 ss —— 雅罗斯拉夫的单词。
第三行包含字符串 tt —— 安德烈的单词。

保证两个单词均由 2⋅n2\cdot n 个字符“0”和“1”组成。

输出格式

Print "First", if both players play optimally well and Yaroslav wins. If Andrey wins, print "Second" and if the game ends with a draw, print "Draw". Print the words without the quotes.

如果双方玩家都采取最优策略,且雅罗斯拉夫获胜,则输出 “First”;如果安德烈获胜,则输出 “Second”;如果游戏以平局结束,则输出 “Draw”。仅输出单词,不带引号。

输入输出样例

  • 输入#1

    2
    0111
    0001

    输出#1

    First
  • 输入#2

    3
    110110
    001001

    输出#2

    First
  • 输入#3

    3
    111000
    000111

    输出#3

    Draw
  • 输入#4

    4
    01010110
    00101101

    输出#4

    First
  • 输入#5

    4
    01100000
    10010011

    输出#5

    Second

输入解题思路,AI测评打分。不知道怎么写?

首页