結果
| 問題 |
No.438 Cwwプログラミング入門
|
| ユーザー |
 hiromi_ayase
|
| 提出日時 | 2016-10-29 00:27:28 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,087 bytes |
| コンパイル時間 | 5,056 ms |
| コンパイル使用メモリ | 80,408 KB |
| 実行使用メモリ | 50,300 KB |
| 最終ジャッジ日時 | 2024-11-24 22:33:38 |
| 合計ジャッジ時間 | 13,495 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 94 WA * 3 OLE * 1 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.NoSuchElementException;
public class Main {
public static void main(String[] args) {
FastScanner sc = new FastScanner();
long x = sc.nextLong();
long y = sc.nextLong();
long z = sc.nextLong();
System.out.println(solve(x, y, z));
// System.out.println(run(solve(x, y, z), x, y));
// while (true) {
// long x = (long) (10000 * Math.random());
// long y = (long) (10000 * Math.random());
// long z = (long) (10000 * Math.random());
//
// String s = solve(x, y, z);
// if (!s.equals("mourennaihasimasenn")) {
// long rz = run(s, x, y);
//
// if (z != rz) {
// System.out.printf("%d %d %d %s %d\n", x, y, z, s, rz);
// break;
// }
// }
// }
}
private static String solve(long x, long y, long z) {
long[] gcd = exGCD(x, y);
if (z == 0) {
return "ccW";
} else if (y > 0 && z % y == 0) {
long p = z / y;
StringBuilder sb = new StringBuilder();
sb.append("w");
for (int i = 0; i < p - 1; i++) {
sb.append("w");
sb.append("C");
}
return sb.toString();
} else if (x > 0 && z % x == 0) {
long p = z / x;
StringBuilder sb = new StringBuilder();
sb.append("c");
for (int i = 0; i < p - 1; i++) {
sb.append("c");
sb.append("C");
}
return sb.toString();
} else if (gcd == null || z % gcd[0] != 0 || z / Math.max(x, y) >= 10000) {
return "mourennaihasimasenn";
} else {
long a = 0, b = 0;
boolean flg = false;
for (a = -5000; a <= 5000; a++) {
long p = z - a * x;
if (p % y != 0)
continue;
b = p / y;
long size = 2 * (Math.abs(a) + Math.abs(b)) - 1;
if (size <= 10000) {
flg = true;
break;
}
}
if (!flg) {
return "mourennaihasimasenn";
}
ArrayDeque<Character> queue = new ArrayDeque<>();
if (a > 0) {
for (int i = 0; i < a; i++)
queue.add('c');
for (int i = 0; i < a - 1; i++)
queue.add('C');
if (b > 0) {
for (int i = 0; i < b; i++) {
queue.add('w');
queue.add('C');
}
} else if (b < 0) {
for (int i = 0; i < -b; i++) {
queue.addFirst('w');
}
for (int i = 0; i < -b; i++) {
queue.add('W');
}
}
} else {
for (int i = 0; i < b; i++)
queue.add('w');
for (int i = 0; i < b - 1; i++)
queue.add('C');
if (a > 0) {
for (int i = 0; i < a; i++) {
queue.add('c');
queue.add('C');
}
} else if (a < 0) {
for (int i = 0; i < -a; i++) {
queue.addFirst('c');
}
for (int i = 0; i < -a; i++) {
queue.add('W');
}
}
}
StringBuilder sb = new StringBuilder();
for (char c : queue) {
sb.append(c);
}
return sb.toString();
}
}
public static long[] exGCD(long a, long b) {
if (a == 0 || b == 0)
return null;
int as = Long.signum(a);
int bs = Long.signum(b);
a = Math.abs(a);
b = Math.abs(b);
long p = 1, q = 0, r = 0, s = 1;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
d = r;
r = s;
s = d - c * s;
}
return new long[] { a, p * as, r * bs };
}
private static long run(String s, long x, long y) {
long[] stack = new long[100000];
int ptr = 0;
for (int c : s.toCharArray()) {
if (c == 'c') {
stack[ptr++] = x;
} else if (c == 'w') {
stack[ptr++] = y;
} else if (c == 'C') {
ptr--;
stack[ptr - 1] = stack[ptr] + stack[ptr - 1];
} else if (c == 'W') {
ptr--;
stack[ptr - 1] = stack[ptr] - stack[ptr - 1];
}
}
return stack[ptr - 1];
}
}
class FastScanner {
public static String debug = null;
private final InputStream in = System.in;
private int ptr = 0;
private int buflen = 0;
private byte[] buffer = new byte[1024];
private boolean eos = false;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
if (debug != null) {
buflen = debug.length();
buffer = debug.getBytes();
debug = "";
eos = true;
} else {
buflen = in.read(buffer);
}
} catch (IOException e) {
e.printStackTrace();
}
if (buflen < 0) {
eos = true;
return false;
} else if (buflen == 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
}
public boolean isEOS() {
return this.eos;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
return (int) nextLong();
}
public long[] nextLongList(int n) {
return nextLongTable(1, n)[0];
}
public int[] nextIntList(int n) {
return nextIntTable(1, n)[0];
}
public long[][] nextLongTable(int n, int m) {
long[][] ret = new long[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i][j] = nextLong();
}
}
return ret;
}
public int[][] nextIntTable(int n, int m) {
int[][] ret = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i][j] = nextInt();
}
}
return ret;
}
}