You and Crossroads

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After hearing about the recent gold discovery in Belgium, you decide to travel to Brussels to make some profits.

Minutes after landing at the Brussels International Airport, you find yourself walking along a lonely road that seems to lead nowhere. Just as you start to reconsider your life choices, you enter a crossroads that separates 4 different areas of land. A sign reads: "You may only explore a single quadrant of land if you're looking for gold." Luckily, you brought your gold map of this exact plot of land. The map has 2N rows and 2N columns, divided evenly into four quadrants. The quadrant order is as follows:

Every character on the gold map consists of either d for dirt and g for gold. Your task is to output the number of the quadrant that has the most gold.

Input

First line consists of a single integer N (1 \le N \le 20). This represents the width and height of a quadrant of the gold map.

The next 2N lines consist of 2N characters each. These are the contents of your gold map.

Output

The number of the quadrant that will bring you the most gold. Break ties by outputting the quadrant that has both the most gold and the lowest number.

Sample Input

3
ddddgg
ddgddd
dddddd
gggddd
ddddgd
gggggg

Sample Output

3

Explanation

The bottom left quadrant, quadrant 3, has 6 gold bars. This is more than any other quadrant.


Comments


  • -2
    Daniel_Weintraub  commented on Jan. 17, 2016, 10:41 a.m. edit 2

    .


    • 0
      odaniel  commented on Jan. 17, 2016, 10:50 a.m.

      Are you currently participating in the VMSS7WC? If so, you can't view your submissions to any problem but the contest.