QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267204 | #5112. Where Am I? | juampi | AC ✓ | 231ms | 53316kb | Java8 | 3.5kb | 2023-11-27 01:48:29 | 2023-11-27 01:48:29 |
Judging History
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