?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Adding some more judges, here and there.
[and.git] / NEERC / garbling / garbling_re.java
blob9f7c246f80746475b40dda08efbbc91308d462a8
1 import java.io.*;
2 import java.util.*;
3 import java.math.BigInteger;
4
5 /**
6 * Solution for NEERC'2009 Problem G: Garbling Game.
7 * This solution checks correctness of the input.
8 * @author Roman Elizarov
9 */
10 public class garbling_re {
11 static final int MODULO = 100000;
12
13 public static void main(String[] args) throws Exception {
14 new garbling_re().go();
15 }
16
17 void go() throws Exception {
18 read();
19 solve();
20 write();
21 }
22
23 static class Field implements Cloneable {
24 int[][] a;
25
26 Field(int r, int c) {
27 a = new int[r][c];
28 int n = 0;
29 for (int i = 0; i < r; i++) {
30 for (int j = 0; j < c; j++) {
31 a[i][j] = n++;
32 }
33 }
34 }
35
36 void garbleLeft(int i, int j) {
37 int t = a[i][j];
38 a[i][j] = a[i][j + 1];
39 a[i][j + 1] = a[i + 1][j + 1];
40 a[i + 1][j + 1] = a[i + 1][j];
41 a[i + 1][j] = t;
42 }
43
44 void garbleRight(int i, int j) {
45 int t = a[i][j];
46 a[i][j] = a[i + 1][j];
47 a[i + 1][j] = a[i + 1][j + 1];
48 a[i + 1][j + 1] = a[i][j + 1];
49 a[i][j + 1] = t;
50 }
51 }
52
53 int r;
54 int c;
55 BigInteger n;
56 char[][] map;
57
58 BigInteger turns = BigInteger.ZERO;
59 int[] writtenModulo;
60 int[] woneModulo;
61
62 void read() throws Exception {
63 Scanner in = new Scanner(new File("garbling.in"));
64 in.useLocale(Locale.US);
65 r = in.nextInt();
66 c = in.nextInt();
67 n = new BigInteger(in.next());
68 in.nextLine();
69 assert r >= 2 && r <= 300;
70 assert c >= 2 && c <= 300;
71 assert n.compareTo(BigInteger.ZERO) >= 0 && n.compareTo(BigInteger.valueOf(10).pow(100)) < 0;
72 map = new char[r - 1][];
73 for (int i = 0; i < r - 1; i++) {
74 map[i] = in.next().toCharArray();
75 in.nextLine();
76 assert map[i].length == c - 1;
77 for (int j = 0; j < c - 1; j++) {
78 assert "RLN".indexOf(map[i][j]) >= 0;
79 }
80 }
81 in.close();
82 }
83
84 void solve() {
85 // garble field once
86 int k = r * c;
87 writtenModulo = new int[k];
88 Field f = new Field(r, c);
89 garbleFieldOnce(f);
90 if (turns.compareTo(n) >= 0)
91 return;
92 // find transposition of one garbling
93 int[] transpose = new int[k];
94 for (int i = 0; i < r; i++) {
95 for (int j = 0; j < c; j++) {
96 transpose[f.a[i][j]] = i * c + j;
97 }
98 }
99 // split transposition into loops
100 int[] lnum = new int[k];
101 int[] llen = new int[k];
102 int[] lidx = new int[k];
103 int[][] lfromidx = new int[k][0];
104 int[][] lwrModulo = new int[k][0];
105 int lc = 0;
106 Arrays.fill(lnum, -1);
107 for (int p = 0; p < k; p++) {
108 if (lnum[p] < 0) {
109 int cnt = 0;
110 do {
111 lnum[p] = lc;
112 lidx[p] = cnt;
113 lfromidx[lc] = grow(lfromidx[lc], cnt + 1);
114 lfromidx[lc][cnt] = p;
115 lwrModulo[lc] = grow(lwrModulo[lc], cnt + 2);
116 lwrModulo[lc][cnt + 1] = addModulo(lwrModulo[lc][cnt], writtenModulo[p]);
117 p = transpose[p];
118 cnt++;
119 } while (lnum[p] < 0);
120 llen[lc++] = cnt;
121 }
122 }
123 woneModulo = writtenModulo.clone();
124 // fast-forward full-field grablings
125 BigInteger times = n.subtract(turns).divide(turns);
126 int[] lrem = new int[k + 1];
127 int[] lfltModulo = new int[k + 1];
128 Arrays.fill(lrem, -1);
129 for (int p = 0; p < k; p++) {
130 int plnum = lnum[p];
131 int pllen = llen[plnum];
132 int plrem;
133 int plfltModulo;
134 if (lrem[pllen] >= 0) {
135 plrem = lrem[pllen];
136 plfltModulo = lfltModulo[pllen];
137 } else {
138 BigInteger pllenBig = BigInteger.valueOf(pllen);
139 BigInteger flt = times.divide(pllenBig);
140 plrem = lrem[pllen] = times.mod(pllenBig).intValue();
141 plfltModulo = lfltModulo[pllen] = flt.mod(BigInteger.valueOf(MODULO)).intValue();
142 }
143 writtenModulo[p] = addModulo(writtenModulo[p], mulModulo(plfltModulo, lwrModulo[plnum][pllen]));
144 int q = transpose[p];
145 int idx1 = lidx[q];
146 int idx2 = (idx1 + plrem) % pllen;
147 q = lfromidx[plnum][idx2];
148 if (idx2 > idx1)
149 writtenModulo[p] = addModulo(writtenModulo[p], lwrModulo[plnum][idx2] - lwrModulo[plnum][idx1] + MODULO);
150 else if (idx2 < idx1)
151 writtenModulo[p] = addModulo(writtenModulo[p],
152 lwrModulo[plnum][pllen] - lwrModulo[plnum][idx1] + MODULO + lwrModulo[plnum][idx2]);
153 f.a[q / c][q % c] = p;
154 }
155 turns = turns.add(times.multiply(turns));
156 // finish remaining garblings
157 garbleFieldOnce(f);
158 assert turns.equals(n);
159 }
160
161 private int[] grow(int[] a, int size) {
162 return a.length >= size ? a : Arrays.copyOf(a, Math.max(size, 2 * a.length));
163 }
164
165 void garbleFieldOnce(Field f) {
166 for (int i = 0; i < r - 1; i++) {
167 for (int j = 0; j < c - 1; j++) {
168 if (turns.compareTo(n) >= 0)
169 return;
170 turns = turns.add(BigInteger.ONE);
171 writtenModulo[f.a[i][j]] = addModulo(writtenModulo[f.a[i][j]], 1);
172 switch (map[i][j]) {
173 case 'L': f.garbleLeft(i, j); break;
174 case 'R': f.garbleRight(i, j); break;
175 }
176 }
177 }
178 }
179
180 static int mulModulo(int a, int b) {
181 return (int)((long)a * b % MODULO);
182 }
183
184 static int addModulo(int a, int b) {
185 return (a + b) % MODULO;
186 }
187
188 void write() throws Exception {
189 PrintWriter out = new PrintWriter("garbling.out");
190 for (int i = 0; i < r * c; i++) {
191 out.println(writtenModulo[i]);
192 }
193 out.close();
194 }
195
196 //----------------- just for validation ------------------
197
198 /**
199 * Strict scanner to verify 100% correspondence between input files and input file format specification.
200 * It is a drop-in replacement for {@link java.util.Scanner} that could be added to a soulution source
201 * (cut-and-paste) without breaking its ability to work with {@link java.util.Scanner}.
202 */
203 public class Scanner {
204 private final BufferedReader in;
205 private String line = "";
206 private int pos;
207 private int lineNo;
208 private boolean localeset;
209
210 public Scanner(File source) throws FileNotFoundException {
211 in = new BufferedReader(new FileReader(source));
212 nextLine();
213 }
214
215 public void close() {
216 assert line == null : "Extra data at the end of file";
217 try {
218 in.close();
219 } catch (IOException e) {
220 throw new AssertionError("Failed to close with " + e);
221 }
222 }
223
224 public void nextLine() {
225 assert line != null : "EOF";
226 assert pos == line.length() : "Extra characters on line " + lineNo;
227 try {
228 line = in.readLine();
229 } catch (IOException e) {
230 throw new AssertionError("Failed to read line with " + e);
231 }
232 pos = 0;
233 lineNo++;
234 }
235
236 public String next() {
237 assert line != null : "EOF";
238 assert line.length() > 0 : "Empty line " + lineNo;
239 if (pos == 0)
240 assert line.charAt(0) > ' ' : "Line " + lineNo + " starts with whitespace";
241 else {
242 assert pos < line.length() : "Line " + lineNo + " is over";
243 assert line.charAt(pos) == ' ' : "Wrong whitespace on line " + lineNo;
244 pos++;
245 assert pos < line.length() : "Line " + lineNo + " is over";
246 assert line.charAt(0) > ' ' : "Line " + lineNo + " has double whitespace";
247 }
248 StringBuilder sb = new StringBuilder();
249 while (pos < line.length() && line.charAt(pos) > ' ')
250 sb.append(line.charAt(pos++));
251 return sb.toString();
252 }
253
254 public int nextInt() {
255 String s = next();
256 assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
257 assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
258 try {
259 return Integer.parseInt(s);
260 } catch (NumberFormatException e) {
261 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
262 }
263 }
264
265 public long nextLong() {
266 String s = next();
267 assert s.length() == 1 || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
268 assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
269 try {
270 return Long.parseLong(s);
271 } catch (NumberFormatException e) {
272 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
273 }
274 }
275
276 public double nextDouble() {
277 assert localeset : "Locale must be set with useLocale(Locale.US)";
278 String s = next();
279 assert s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0' : "Extra leading zero in number " + s + " on line " + lineNo;
280 assert s.charAt(0) != '+' : "Extra leading '+' in number " + s + " on line " + lineNo;
281 try {
282 return Double.parseDouble(s);
283 } catch (NumberFormatException e) {
284 throw new AssertionError("Malformed number " + s + " on line " + lineNo);
285 }
286 }
287
288 public void useLocale(Locale locale) {
289 assert locale == Locale.US;
290 localeset = true;
291 }
292 }
293 }