codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

293A.md (2372B)


      1 Source: https://codeforces.com/problemset/problem/293/A
      2 
      3 A. Weird Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 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.
     22 
     23 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.
     24 
     25 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.
     26 
     27 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.
     28 
     29 You are given two strings *s* and *t*. Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.
     30 
     31 Input
     32 
     33 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.
     34 
     35 It is guaranteed that both words consist of 2·*n* characters "0" and "1".
     36 
     37 Output
     38 
     39 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.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 2  
     47 0111  
     48 0001
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 First
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 3  
     61 110110  
     62 001001
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 First
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 3  
     75 111000  
     76 000111
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 Draw
     83 ```
     84 
     85 Input
     86 
     87 ```
     88 4  
     89 01010110  
     90 00101101
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 First
     97 ```
     98 
     99 Input
    100 
    101 ```
    102 4  
    103 01100000  
    104 10010011
    105 ```
    106 
    107 Output
    108 
    109 ```
    110 Second
    111 ```