QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267204#5112. Where Am I?juampiAC ✓231ms53316kbJava83.5kb2023-11-27 01:48:292023-11-27 01:48:29

Judging History

你现在查看的是最新测评结果

  • [2023-11-27 01:48:29]
  • 评测
  • 测评结果:AC
  • 用时:231ms
  • 内存:53316kb
  • [2023-11-27 01:48:29]
  • 提交

answer

// Arup Guha
// 11/11/2022
// Solution to 2021 WF Problem: Where Am I?

import java.util.*;
import java.io.*;

public class l {

	// Dimensions of grid.
	public static int n;
	public static int x;
	public static int y;
	
	public static ArrayList<int[]> pts;
	
	public static void main(String[] args) throws Exception {
	
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		x = Integer.parseInt(tok.nextToken());
		y = Integer.parseInt(tok.nextToken());
		
		pts = new ArrayList<int[]>();
		
		// Read through the y rows.
		for (int i=0; i<y; i++) {
		
			// Go through this row adding each point of interest.
			char[] tmp = stdin.readLine().toCharArray();
			for (int j=0; j<x; j++)
				if (tmp[j] == 'X')
					pts.add(new int[]{j, i});
		}
		
		// # of pts.
		n = pts.size();
		
		// Get all sequences.
		seq[] all = new seq[x*y];
		for (int i=0; i<x*y; i++) 
			all[i] = getSeq(i%x, i/x);
		
		// Sort in lexicographical order.
		Arrays.sort(all);
	
		// Get each difference.
		long tot = 0;
		long[] diff = new long[x*y];
		for (int i=0; i<x*y; i++) {
			long tmp1 = i > 0 ?     all[i].whenDiff(all[i-1]) : 0;
			long tmp2 = i < x*y-1 ? all[i].whenDiff(all[i+1]) : 0;
			diff[i] = Math.max(tmp1, tmp2);
			tot += diff[i];
		}
		
		// Expected Value.
		System.out.println((tot*1.0)/(x*y));
		
		// Max Difference.
		long maxD = 0;
		for (int i=0; i<x*y; i++) maxD = Math.max(diff[i], maxD);
		System.out.println(maxD);
		
		// Get all spots and sort.
		ArrayList<Integer> spots = new ArrayList<Integer>();
		for (int i=0; i<x*y; i++) if (diff[i] == maxD) spots.add(1000*all[i].y + all[i].x);
		Collections.sort(spots);
		
		// Print spots.
		for (int i=0; i<spots.size(); i++) {
			int item = spots.get(i);
			System.out.print("("+(item%1000)+","+(item/1000)+")");
			if (i<spots.size()-1) System.out.print(" ");
		}
		System.out.println();
	}
	
	// Returns the number order of (dx, dy). Note my +y goes down not up.
	public static int getRank(int dx, int dy) {	
		int w = Math.max(Math.abs(dx), Math.abs(dy));
		if (w == 0) return 0;
		if (dx == w)       return 2*w*(2*w-1) + dy + w;
		else if (dy == w)  return (2*w)*(2*w) + w - dx;
		else if (dx == -w) return (2*w)*(2*w)+2*w + w - dy;
		else               return (2*w-1)*(2*w-1) + dx + w - 1;
	}
	
	// Returns the corresponding sequence object if we start at (myx, myy)
	public static seq getSeq(int myx, int myy) {
	
		// Just get the rank of each X and store in array.
		int i = 0;
		int[] res = new int[n];
		for (int[] pt: pts) {
			int dx = pt[0] - myx;
			int dy = pt[1] - myy;
			res[i++] = getRank(dx, dy);
		}
		
		return new seq(res, myx+1, y-myy);
	}
}

class seq implements Comparable<seq> {

	public int[] nums;
	public int x;
	public int y;
	
	public seq(int[] arr, int myx, int myy) {
		Arrays.sort(arr);
		nums = new int[arr.length];
		for (int i=0; i<arr.length; i++) nums[i] = arr[i];
		x = myx;
		y = myy;
	}
	
	// Does lexicographical comparison.
	public int compareTo(seq other) {
		for (int i=0; i<nums.length; i++)
			if (nums[i] != other.nums[i])
				return nums[i] - other.nums[i];
		return 0;
	}
	
	// Returns when we can differentiate this seq from other.
	public int whenDiff(seq other) {
		for (int i=0; i<nums.length; i++) 
			if (nums[i] != other.nums[i]) 
				return Math.min(nums[i],other.nums[i]);		
		return 100; // should never get here.
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 39ms
memory: 37392kb

input:

1 1
X

output:

0.0
0
(1,1)

result:

ok correct!

Test #2:

score: 0
Accepted
time: 43ms
memory: 37780kb

input:

2 1
.X

output:

0.0
0
(1,1) (2,1)

result:

ok correct!

Test #3:

score: 0
Accepted
time: 26ms
memory: 38512kb

input:

2 1
X.

output:

0.0
0
(1,1) (2,1)

result:

ok correct!

Test #4:

score: 0
Accepted
time: 36ms
memory: 37628kb

input:

1 2
.
X

output:

0.0
0
(1,1) (1,2)

result:

ok correct!

Test #5:

score: 0
Accepted
time: 29ms
memory: 37040kb

input:

1 2
X
.

output:

0.0
0
(1,1) (1,2)

result:

ok correct!

Test #6:

score: 0
Accepted
time: 42ms
memory: 37172kb

input:

2 1
XX

output:

3.0
3
(1,1) (2,1)

result:

ok correct!

Test #7:

score: 0
Accepted
time: 36ms
memory: 37340kb

input:

3 3
XXX
X.X
XXX

output:

3.111111111111111
5
(3,1) (3,2)

result:

ok correct!

Test #8:

score: 0
Accepted
time: 192ms
memory: 51228kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4757.9471
9704
(50,1) (50,100)

result:

ok correct!

Test #9:

score: 0
Accepted
time: 74ms
memory: 42988kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.3199
39599
(100,1) (100,2)

result:

ok correct!

Test #10:

score: 0
Accepted
time: 84ms
memory: 43164kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.6699
39500
(100,1) (100,2)

result:

ok correct!

Test #11:

score: 0
Accepted
time: 222ms
memory: 50244kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.6392
39302
(100,99) (99,100)

result:

ok correct!

Test #12:

score: 0
Accepted
time: 231ms
memory: 50204kb

input:

100 100
...................................................................................................X
..................................................................................................X.
.............................................................................................

output:

11854.6098
39104
(1,99) (2,100)

result:

ok correct!

Test #13:

score: 0
Accepted
time: 82ms
memory: 41436kb

input:

20 73
...........X........
.X..................
....................
X.....X........X....
......X........X....
....................
....................
.X..................
....................
...........X........
.X..................
X...................
.......X........X...
.X....X........X....
...

output:

50.097945205479455
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69)

result:

ok correct!

Test #14:

score: 0
Accepted
time: 116ms
memory: 45548kb

input:

65 57
..............X..................................................
.................................................................
.........................................................X.......
........X.........X..............................................
..X.....X........................

output:

100.71120107962213
742
(1,1) (2,1)

result:

ok correct!

Test #15:

score: 0
Accepted
time: 71ms
memory: 40196kb

input:

56 59
........................................................
........................................................
........................................................
........................................................
........................................................
X...........

output:

494.4978813559322
1503
(56,38) (56,39)

result:

ok correct!

Test #16:

score: 0
Accepted
time: 124ms
memory: 43964kb

input:

46 83
..........X...X.................X.............
..............................X...............
...X..........................................
.....................................X........
...X...........................X...X..........
.X............................................
...............

output:

122.54531168150865
387
(1,19) (19,32)

result:

ok correct!

Test #17:

score: 0
Accepted
time: 99ms
memory: 41884kb

input:

51 57
........................X..........................
............................X......................
....................X.............X................
..................................................X
...................................................
.........................X...........

output:

103.48744410044719
334
(10,57) (11,57)

result:

ok correct!

Test #18:

score: 0
Accepted
time: 93ms
memory: 41376kb

input:

64 91
................................................................
................................................................
................................................................
................................................................
.....................................

output:

480.5729739010989
1215
(64,71) (63,91)

result:

ok correct!

Test #19:

score: 0
Accepted
time: 117ms
memory: 42924kb

input:

75 40
.............................................X............X................
....................X..............................X.......................
...........................................X...........X...........X.......
...........................................X.....X......X............

output:

79.14933333333333
319
(1,39) (1,40)

result:

ok correct!

Test #20:

score: 0
Accepted
time: 127ms
memory: 44708kb

input:

97 54
.............X...................................................................................
..................................X..............................................................
....X............................................................................................
...

output:

383.8083237877052
1084
(93,9) (51,51)

result:

ok correct!

Test #21:

score: 0
Accepted
time: 115ms
memory: 44272kb

input:

89 49
...............X...........X.............................................................
.............................................................X..X...........X............
.................................X.......................................................
...........................

output:

161.07016739279982
520
(89,1) (2,41)

result:

ok correct!

Test #22:

score: 0
Accepted
time: 97ms
memory: 44604kb

input:

80 55
.............................................................X..................
................................................................................
.................................................................XX.............
..............................................X.......

output:

176.08318181818183
611
(80,2) (79,37)

result:

ok correct!

Test #23:

score: 0
Accepted
time: 83ms
memory: 42856kb

input:

61 59
...........X.................................................
.............................................................
.......................................................X.....
.............................................................
...............................X.................

output:

291.7060294526257
860
(1,1) (1,50)

result:

ok correct!

Test #24:

score: 0
Accepted
time: 108ms
memory: 44016kb

input:

48 74
....X.X.X.......................................
...............X.....X...X......................
..........................................X.....
................................................
................................................
.......X........................................
...

output:

152.16188063063063
512
(48,9) (48,67)

result:

ok correct!

Test #25:

score: 0
Accepted
time: 220ms
memory: 49904kb

input:

100 96
.................................................................X..................................
.............................X......................................................................
..............................................................................................

output:

212.39625
1031
(1,67) (1,68)

result:

ok correct!

Test #26:

score: 0
Accepted
time: 134ms
memory: 45376kb

input:

94 84
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

357.121327254306
2687
(1,83) (1,84)

result:

ok correct!

Test #27:

score: 0
Accepted
time: 159ms
memory: 47940kb

input:

86 80
...........................................................X..........X...............
......................................................................................
X.....................................................................................
....................................

output:

225.85552325581395
975
(84,1) (85,1)

result:

ok correct!

Test #28:

score: 0
Accepted
time: 151ms
memory: 45872kb

input:

81 57
.X............X..................................................................
.................................................................................
.....................................X.........X.............X...................
...................................................

output:

139.7340264240849
647
(24,1) (81,4)

result:

ok correct!

Test #29:

score: 0
Accepted
time: 122ms
memory: 43876kb

input:

65 85
.................................................................
.................................................................
.................................................................
...................X.............................................
.................................

output:

738.974479638009
3378
(5,45) (5,56)

result:

ok correct!

Test #30:

score: 0
Accepted
time: 89ms
memory: 43044kb

input:

76 98
............................................................................
............................................................................
............................................................................
..................................................................

output:

1550.390977443609
4192
(76,34) (76,96)

result:

ok correct!

Test #31:

score: 0
Accepted
time: 73ms
memory: 42916kb

input:

62 67
..............................................................
..............................................................
.........................X....................................
...................................................X..........
.............................................

output:

648.6502166586423
2420
(16,1) (1,13)

result:

ok correct!

Test #32:

score: 0
Accepted
time: 130ms
memory: 46632kb

input:

50 98
..........................................X.......
.................................X...............X
..................................................
..................................................
.............................................X....
..........................................

output:

207.33775510204083
895
(1,97) (1,98)

result:

ok correct!

Test #33:

score: 0
Accepted
time: 186ms
memory: 48576kb

input:

74 97
....................X.....................................................
..........................................................................
..........................................................................
................................X.......................................

output:

193.03023126219003
1078
(74,70) (71,93)

result:

ok correct!

Test #34:

score: 0
Accepted
time: 74ms
memory: 40408kb

input:

62 77
..............................................................
..............................................................
..............................................................
..............................................................
.............................................

output:

2021.0699622957688
4937
(46,73) (8,77)

result:

ok correct!

Test #35:

score: 0
Accepted
time: 98ms
memory: 43756kb

input:

47 74
...............................................
...............................................
...............................................
.....................X.........................
...............................................
............................................X..
.........

output:

142.15382403680277
673
(1,74) (2,74)

result:

ok correct!

Test #36:

score: 0
Accepted
time: 88ms
memory: 42908kb

input:

47 71
...........X....X..............................
...............................................
...............................................
...........X...................................
.............................................X.
..X...........XX............X..................
.........

output:

102.81420437518729
334
(44,4) (47,37)

result:

ok correct!

Test #37:

score: 0
Accepted
time: 101ms
memory: 45596kb

input:

51 65
.........X..........X..............................
.................................X....X.........X..
................................................X..
...................................................
...................................................
.....................................

output:

81.66998491704373
314
(1,64) (1,65)

result:

ok correct!

Test #38:

score: 0
Accepted
time: 75ms
memory: 42784kb

input:

40 93
.......X................................
........................................
........................................
........................................
.X......................................
..................X.....................
........................................
..........

output:

300.30752688172043
1326
(39,93) (40,93)

result:

ok correct!

Test #39:

score: 0
Accepted
time: 170ms
memory: 47904kb

input:

87 99
.......................................................................................
.......................................................................................
.......................................................................................
.................................

output:

474.0689655172414
2063
(1,1) (49,1)

result:

ok correct!

Test #40:

score: 0
Accepted
time: 61ms
memory: 38472kb

input:

46 94
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
...............

output:

2555.3674838112856
5914
(46,1) (46,2)

result:

ok correct!

Test #41:

score: 0
Accepted
time: 63ms
memory: 42120kb

input:

93 60
.............................................................................................
.............................................................................................
.............................................................................................
...............

output:

2389.200358422939
11288
(21,60) (22,60)

result:

ok correct!

Test #42:

score: 0
Accepted
time: 128ms
memory: 45960kb

input:

98 61
.............................................X................................X...................
...................................................................X.............X................
..................................................................................X................

output:

225.08916025426564
803
(10,61) (11,61)

result:

ok correct!

Test #43:

score: 0
Accepted
time: 222ms
memory: 53316kb

input:

94 95
..............................................................................................
.......................................................X......................................
............X................................................X.......................X........
............

output:

213.68756998880178
941
(33,89) (33,90)

result:

ok correct!

Test #44:

score: 0
Accepted
time: 147ms
memory: 46012kb

input:

94 72
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

1330.0895390070923
4671
(60,71) (38,72)

result:

ok correct!

Test #45:

score: 0
Accepted
time: 98ms
memory: 41780kb

input:

46 44
....X...X..............................X...X..
................................X..X......X...
..............X.........X.....................
......................X...........X...........
......................X.X........X.X...X......
.............X..........X.....................
.X.............

output:

67.35474308300395
645
(1,1) (2,1)

result:

ok correct!

Test #46:

score: 0
Accepted
time: 129ms
memory: 45960kb

input:

65 51
.................................................................
.........................X.......................................
........X..............X.........................................
....X...............X............................................
.................................

output:

80.04102564102564
332
(64,34) (65,34)

result:

ok correct!

Test #47:

score: 0
Accepted
time: 118ms
memory: 44336kb

input:

51 82
...................................................
...............X...........X.........X.............
..............................X....................
...................................................
...................................................
.......................X.............

output:

100.4660449545672
360
(49,3) (51,62)

result:

ok correct!

Test #48:

score: 0
Accepted
time: 106ms
memory: 41992kb

input:

87 60
.......................................................................................
........................................................................X..............
.......................................................................................
.................................

output:

302.789846743295
799
(87,29) (87,58)

result:

ok correct!

Test #49:

score: 0
Accepted
time: 76ms
memory: 41972kb

input:

53 44
...................................X.................
.....................................................
............................X....X...................
...X.................................................
.....................................................
....................X......

output:

150.34691252144083
930
(52,44) (53,44)

result:

ok correct!

Test #50:

score: 0
Accepted
time: 143ms
memory: 46384kb

input:

94 97
..............................................................................................
.......................................X......................X...............................
..............................................................................................
............

output:

690.6464136872121
3826
(1,96) (1,97)

result:

ok correct!

Test #51:

score: 0
Accepted
time: 92ms
memory: 41712kb

input:

70 68
......................................................................
.....................X...........................X....................
........X...........................X...........................X.....
......................................................................
.............

output:

356.9745798319328
1620
(23,68) (51,68)

result:

ok correct!

Test #52:

score: 0
Accepted
time: 109ms
memory: 44748kb

input:

100 91
....................................................................................................
....................................................................................................
..............................................................................................

output:

1705.102197802198
4664
(100,44) (100,90)

result:

ok correct!

Test #53:

score: 0
Accepted
time: 81ms
memory: 42644kb

input:

88 84
........................................................................................
........................................................................................
........................................................................................
..............................

output:

2976.142316017316
8305
(68,1) (69,1)

result:

ok correct!

Test #54:

score: 0
Accepted
time: 80ms
memory: 42336kb

input:

48 44
................................................
................................................
..........X...........X.........................
...X............................................
...........................X....................
.........X......................................
...

output:

140.1879734848485
466
(8,7) (1,20)

result:

ok correct!

Test #55:

score: 0
Accepted
time: 157ms
memory: 47040kb

input:

98 60
......................................X.....X.....................................................
......................................X..............................X............................
............X......................................................X...............................

output:

179.27925170068028
713
(98,56) (98,57)

result:

ok correct!

Test #56:

score: 0
Accepted
time: 91ms
memory: 41768kb

input:

58 41
...............................X...............X..........
..X..................X....X...............................
..........................................................
.....................X.............................X......
..............................X.................X............

output:

75.12952060555088
228
(2,1) (49,27)

result:

ok correct!

Test #57:

score: 0
Accepted
time: 150ms
memory: 45120kb

input:

95 48
....X.......X.......................X..............X........................X...........X......
........X...............................X...............................X......................
........................XX...............................X.....................................
.........

output:

115.9405701754386
390
(15,48) (79,48)

result:

ok correct!

Test #58:

score: 0
Accepted
time: 102ms
memory: 44156kb

input:

51 62
...................................................
..............................X.........X..........
................................................X..
.......................X...........................
..............................................X....
.....................................

output:

127.05028462998102
432
(7,1) (51,6)

result:

ok correct!

Test #59:

score: 0
Accepted
time: 184ms
memory: 47860kb

input:

86 98
.......X......X.......................................................................
......................................................................................
......................................................................................
....................................

output:

215.50094921689606
732
(66,70) (68,72)

result:

ok correct!

Test #60:

score: 0
Accepted
time: 152ms
memory: 46200kb

input:

91 94
...........................................................................................
...........................................................................................
...........................................................................................
.....................

output:

309.110357727379
1541
(78,1) (90,8)

result:

ok correct!

Test #61:

score: 0
Accepted
time: 89ms
memory: 44304kb

input:

74 45
..........................................................................
..........................................................................
....X.............X..........................................X............
.X................X..........................X............X.............

output:

164.8780780780781
772
(1,7) (1,8)

result:

ok correct!

Test #62:

score: 0
Accepted
time: 127ms
memory: 44524kb

input:

54 73
.....X.......X........................................
.............X........................................
...............X......................................
................................X.....................
..............................................X.......
......................

output:

106.01293759512937
560
(1,1) (1,2)

result:

ok correct!

Test #63:

score: 0
Accepted
time: 141ms
memory: 46588kb

input:

91 56
...........................................................................................
..............................X.............................X..............................
.....................................................................X.....................
.....................

output:

423.71487441130296
1455
(63,19) (24,20)

result:

ok correct!

Test #64:

score: 0
Accepted
time: 41ms
memory: 38428kb

input:

1 2
X
X

output:

1.0
1
(1,1) (1,2)

result:

ok correct!

Test #65:

score: 0
Accepted
time: 30ms
memory: 37252kb

input:

1 3
X
.
.

output:

0.6666666666666666
1
(1,1) (1,2)

result:

ok correct!

Test #66:

score: 0
Accepted
time: 38ms
memory: 37012kb

input:

1 3
.
X
.

output:

0.6666666666666666
1
(1,1) (1,3)

result:

ok correct!

Test #67:

score: 0
Accepted
time: 38ms
memory: 37068kb

input:

1 3
X
X
.

output:

0.6666666666666666
1
(1,2) (1,3)

result:

ok correct!

Test #68:

score: 0
Accepted
time: 52ms
memory: 37272kb

input:

1 3
.
.
X

output:

3.3333333333333335
5
(1,2) (1,3)

result:

ok correct!

Test #69:

score: 0
Accepted
time: 40ms
memory: 39716kb

input:

1 3
X
.
X

output:

6.666666666666667
10
(1,1) (1,3)

result:

ok correct!

Test #70:

score: 0
Accepted
time: 45ms
memory: 38304kb

input:

1 3
.
X
X

output:

0.6666666666666666
1
(1,1) (1,2)

result:

ok correct!

Test #71:

score: 0
Accepted
time: 46ms
memory: 37028kb

input:

1 3
X
X
X

output:

3.6666666666666665
5
(1,1) (1,2)

result:

ok correct!

Test #72:

score: 0
Accepted
time: 41ms
memory: 38432kb

input:

1 4
X
.
.
.

output:

5.25
10
(1,1) (1,2)

result:

ok correct!

Test #73:

score: 0
Accepted
time: 36ms
memory: 37016kb

input:

1 4
.
X
.
.

output:

2.75
5
(1,1) (1,4)

result:

ok correct!

Test #74:

score: 0
Accepted
time: 41ms
memory: 39056kb

input:

1 4
X
X
.
.

output:

1.0
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #75:

score: 0
Accepted
time: 43ms
memory: 37832kb

input:

1 4
.
.
X
.

output:

2.75
5
(1,3) (1,4)

result:

ok correct!

Test #76:

score: 0
Accepted
time: 30ms
memory: 38340kb

input:

1 4
X
.
X
.

output:

7.5
10
(1,2) (1,4)

result:

ok correct!

Test #77:

score: 0
Accepted
time: 43ms
memory: 38036kb

input:

1 4
.
X
X
.

output:

1.0
1
(1,1) (1,2) (1,3) (1,4)

result:

ok correct!

Test #78:

score: 0
Accepted
time: 40ms
memory: 37148kb

input:

1 4
X
X
X
.

output:

2.75
5
(1,2) (1,3)

result:

ok correct!

Test #79:

score: 0
Accepted
time: 40ms
memory: 39636kb

input:

1 4
.
.
.
X

output:

10.25
18
(1,3) (1,4)

result:

ok correct!

Test #80:

score: 0
Accepted
time: 40ms
memory: 38368kb

input:

1 4
X
.
.
X

output:

14.0
27
(1,1) (1,4)

result:

ok correct!

Test #81:

score: 0
Accepted
time: 32ms
memory: 37260kb

input:

1 4
.
X
.
X

output:

5.5
10
(1,1) (1,3)

result:

ok correct!

Test #82:

score: 0
Accepted
time: 39ms
memory: 37380kb

input:

1 4
X
X
.
X

output:

2.75
5
(1,1) (1,4)

result:

ok correct!

Test #83:

score: 0
Accepted
time: 32ms
memory: 37256kb

input:

1 4
.
.
X
X

output:

3.0
5
(1,3) (1,4)

result:

ok correct!

Test #84:

score: 0
Accepted
time: 19ms
memory: 37204kb

input:

1 4
X
.
X
X

output:

2.75
5
(1,2) (1,4)

result:

ok correct!

Test #85:

score: 0
Accepted
time: 39ms
memory: 37380kb

input:

1 4
.
X
X
X

output:

2.75
5
(1,1) (1,2)

result:

ok correct!

Test #86:

score: 0
Accepted
time: 45ms
memory: 39648kb

input:

1 4
X
X
X
X

output:

6.5
10
(1,2) (1,3)

result:

ok correct!

Test #87:

score: 0
Accepted
time: 35ms
memory: 37048kb

input:

2 2
X.
..

output:

3.75
7
(2,1) (2,2)

result:

ok correct!

Test #88:

score: 0
Accepted
time: 36ms
memory: 38040kb

input:

2 2
.X
..

output:

1.25
2
(1,1) (1,2)

result:

ok correct!

Test #89:

score: 0
Accepted
time: 41ms
memory: 37208kb

input:

2 2
XX
..

output:

2.5
3
(1,2) (2,2)

result:

ok correct!

Test #90:

score: 0
Accepted
time: 43ms
memory: 38080kb

input:

2 2
..
X.

output:

4.25
6
(2,1) (2,2)

result:

ok correct!

Test #91:

score: 0
Accepted
time: 43ms
memory: 37200kb

input:

2 2
X.
X.

output:

3.5
6
(2,1) (2,2)

result:

ok correct!

Test #92:

score: 0
Accepted
time: 49ms
memory: 37380kb

input:

2 2
.X
X.

output:

1.5
2
(1,1) (2,2)

result:

ok correct!

Test #93:

score: 0
Accepted
time: 38ms
memory: 38568kb

input:

2 2
XX
X.

output:

1.75
3
(1,2) (2,2)

result:

ok correct!

Test #94:

score: 0
Accepted
time: 29ms
memory: 38004kb

input:

2 2
..
.X

output:

2.75
4
(1,2) (2,2)

result:

ok correct!

Test #95:

score: 0
Accepted
time: 45ms
memory: 39196kb

input:

2 2
X.
.X

output:

2.5
4
(2,1) (1,2)

result:

ok correct!

Test #96:

score: 0
Accepted
time: 42ms
memory: 38196kb

input:

2 2
.X
.X

output:

1.5
2
(1,1) (1,2)

result:

ok correct!

Test #97:

score: 0
Accepted
time: 37ms
memory: 36996kb

input:

2 2
XX
.X

output:

1.75
3
(1,2) (2,2)

result:

ok correct!

Test #98:

score: 0
Accepted
time: 36ms
memory: 39608kb

input:

2 2
..
XX

output:

3.5
4
(1,2) (2,2)

result:

ok correct!

Test #99:

score: 0
Accepted
time: 51ms
memory: 37044kb

input:

2 2
X.
XX

output:

2.25
4
(2,1) (1,2)

result:

ok correct!

Test #100:

score: 0
Accepted
time: 45ms
memory: 38024kb

input:

2 2
.X
XX

output:

1.25
2
(1,1) (2,2)

result:

ok correct!

Test #101:

score: 0
Accepted
time: 43ms
memory: 37072kb

input:

2 2
XX
XX

output:

2.5
3
(1,2) (2,2)

result:

ok correct!

Test #102:

score: 0
Accepted
time: 45ms
memory: 38696kb

input:

3 1
X..

output:

4.666666666666667
7
(2,1) (3,1)

result:

ok correct!

Test #103:

score: 0
Accepted
time: 37ms
memory: 38200kb

input:

3 1
.X.

output:

2.0
3
(1,1) (3,1)

result:

ok correct!

Test #104:

score: 0
Accepted
time: 28ms
memory: 37608kb

input:

3 1
XX.

output:

2.0
3
(1,1) (2,1)

result:

ok correct!

Test #105:

score: 0
Accepted
time: 40ms
memory: 37152kb

input:

3 1
..X

output:

2.0
3
(1,1) (2,1)

result:

ok correct!

Test #106:

score: 0
Accepted
time: 44ms
memory: 38576kb

input:

3 1
X.X

output:

9.333333333333334
14
(1,1) (3,1)

result:

ok correct!

Test #107:

score: 0
Accepted
time: 33ms
memory: 37192kb

input:

3 1
.XX

output:

2.0
3
(2,1) (3,1)

result:

ok correct!

Test #108:

score: 0
Accepted
time: 41ms
memory: 38540kb

input:

3 1
XXX

output:

5.666666666666667
7
(1,1) (2,1)

result:

ok correct!

Test #109:

score: 0
Accepted
time: 36ms
memory: 38060kb

input:

4 1
X...

output:

12.75
22
(3,1) (4,1)

result:

ok correct!

Test #110:

score: 0
Accepted
time: 37ms
memory: 38140kb

input:

4 1
.X..

output:

4.25
7
(3,1) (4,1)

result:

ok correct!

Test #111:

score: 0
Accepted
time: 33ms
memory: 39648kb

input:

4 1
XX..

output:

5.0
7
(3,1) (4,1)

result:

ok correct!

Test #112:

score: 0
Accepted
time: 36ms
memory: 39460kb

input:

4 1
..X.

output:

4.25
7
(1,1) (4,1)

result:

ok correct!

Test #113:

score: 0
Accepted
time: 50ms
memory: 37936kb

input:

4 1
X.X.

output:

8.5
14
(1,1) (3,1)

result:

ok correct!

Test #114:

score: 0
Accepted
time: 41ms
memory: 38452kb

input:

4 1
.XX.

output:

3.0
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #115:

score: 0
Accepted
time: 33ms
memory: 38216kb

input:

4 1
XXX.

output:

4.25
7
(1,1) (2,1)

result:

ok correct!

Test #116:

score: 0
Accepted
time: 38ms
memory: 37984kb

input:

4 1
...X

output:

7.75
14
(1,1) (2,1)

result:

ok correct!

Test #117:

score: 0
Accepted
time: 44ms
memory: 37448kb

input:

4 1
X..X

output:

18.0
33
(1,1) (4,1)

result:

ok correct!

Test #118:

score: 0
Accepted
time: 37ms
memory: 36976kb

input:

4 1
.X.X

output:

10.5
14
(2,1) (4,1)

result:

ok correct!

Test #119:

score: 0
Accepted
time: 41ms
memory: 38092kb

input:

4 1
XX.X

output:

4.25
7
(2,1) (4,1)

result:

ok correct!

Test #120:

score: 0
Accepted
time: 46ms
memory: 38252kb

input:

4 1
..XX

output:

3.0
3
(1,1) (2,1) (3,1) (4,1)

result:

ok correct!

Test #121:

score: 0
Accepted
time: 51ms
memory: 38740kb

input:

4 1
X.XX

output:

4.25
7
(1,1) (4,1)

result:

ok correct!

Test #122:

score: 0
Accepted
time: 37ms
memory: 37284kb

input:

4 1
.XXX

output:

4.25
7
(2,1) (3,1)

result:

ok correct!

Test #123:

score: 0
Accepted
time: 50ms
memory: 37332kb

input:

4 1
XXXX

output:

9.5
14
(2,1) (3,1)

result:

ok correct!

Test #124:

score: 0
Accepted
time: 28ms
memory: 37208kb

input:

100 1
X...................................................................................................

output:

13274.59
38710
(99,1) (100,1)

result:

ok correct!

Test #125:

score: 0
Accepted
time: 38ms
memory: 38508kb

input:

100 1
...................................................................................................X

output:

13076.63
38318
(1,1) (2,1)

result:

ok correct!

Test #126:

score: 0
Accepted
time: 39ms
memory: 38540kb

input:

100 1
..................................................X.................................................

output:

3356.01
9751
(1,1) (100,1)

result:

ok correct!

Test #127:

score: 0
Accepted
time: 50ms
memory: 40216kb

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.5
9950
(50,1) (51,1)

result:

ok correct!

Test #128:

score: 0
Accepted
time: 47ms
memory: 40252kb

input:

100 1
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.

output:

3554.94
9950
(49,1) (51,1)

result:

ok correct!

Test #129:

score: 0
Accepted
time: 69ms
memory: 39892kb

input:

100 2
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X

output:

3451.07
9751
(49,1) (51,1)

result:

ok correct!

Test #130:

score: 0
Accepted
time: 41ms
memory: 37232kb

input:

1 100
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

12977.65
38122
(1,1) (1,2)

result:

ok correct!

Test #131:

score: 0
Accepted
time: 38ms
memory: 38464kb

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X

output:

13175.61
38514
(1,99) (1,100)

result:

ok correct!

Test #132:

score: 0
Accepted
time: 42ms
memory: 37332kb

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

3306.03
9653
(1,99) (1,100)

result:

ok correct!

Test #133:

score: 0
Accepted
time: 39ms
memory: 39764kb

input:

1 100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

output:

3406.5
9850
(1,50) (1,51)

result:

ok correct!

Test #134:

score: 0
Accepted
time: 50ms
memory: 39796kb

input:

1 100
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.

output:

3503.02
9850
(1,50) (1,52)

result:

ok correct!

Test #135:

score: 0
Accepted
time: 60ms
memory: 39404kb

input:

2 100
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
...

output:

3401.11
9654
(2,49) (2,51)

result:

ok correct!

Test #136:

score: 0
Accepted
time: 54ms
memory: 38772kb

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

58.08
95
(5,10) (6,10)

result:

ok correct!

Test #137:

score: 0
Accepted
time: 183ms
memory: 50116kb

input:

100 100
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
....................................................................................................
.............................................................................................

output:

13878.9275
38908
(99,1) (100,1)

result:

ok correct!

Test #138:

score: 0
Accepted
time: 186ms
memory: 50840kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

14059.2725
39302
(99,100) (100,100)

result:

ok correct!

Test #139:

score: 0
Accepted
time: 187ms
memory: 51056kb

input:

100 100
X...................................................................................................
X...................................................................................................
X............................................................................................

output:

14132.2825
39500
(100,1) (100,2)

result:

ok correct!

Test #140:

score: 0
Accepted
time: 222ms
memory: 51376kb

input:

100 100
...................................................................................................X
...................................................................................................X
.............................................................................................

output:

13951.4325
39104
(1,99) (1,100)

result:

ok correct!

Test #141:

score: 0
Accepted
time: 81ms
memory: 41832kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19733.3399
39302
(99,100) (100,100)

result:

ok correct!

Test #142:

score: 0
Accepted
time: 67ms
memory: 42456kb

input:

100 100
...................................................................................................X
....................................................................................................
.............................................................................................

output:

19601.0099
39104
(1,99) (1,100)

result:

ok correct!

Test #143:

score: 0
Accepted
time: 70ms
memory: 41904kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

5001.4899
10098
(99,100) (100,100)

result:

ok correct!

Test #144:

score: 0
Accepted
time: 56ms
memory: 41084kb

input:

20 20
.XX......XX.....XXXX
..X.....X..X....X...
.....X..............
X..XX.X..XX......XX.
X..........X........
...X..X............X
.X...X..........XXXX
.X...XX..XX....X....
X.X.XX...X.......X.X
XXXXX....X........X.
.X.XX.X..XX...X.X...
X.......X..XXX.....X
.X..X..X.X......X...
.........X....X...X.
...

output:

12.8125
31
(13,5) (15,18)

result:

ok correct!

Test #145:

score: 0
Accepted
time: 104ms
memory: 41252kb

input:

50 50
..................................................
..................X...............X...............
..................................................
....X...X........................X........X..X....
.................X................................
..........................................

output:

60.8308
195
(28,1) (1,35)

result:

ok correct!

Test #146:

score: 0
Accepted
time: 218ms
memory: 50680kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

227.5349
1062
(96,95) (55,100)

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed