競技プログラムについて 教えていただけませんか
Posted: 2016年5月20日(金) 05:43
by double-clutch.
[uri]http://judge.u-aizu.ac.jp/onlinejudge/d ... =ITP1_11_A
以上の競技プログラミングにチャレンジしたのですが、間違っているらしいのです。
visual studio 2010 で、ビルドは通って、デバックでも 下の仕様は満たしていると思うのですが、次の判定が返って来ます。
[hr]
WA: Presentation Error
提出されたプログラムは、ほぼ受理される出力を行っていますが、余計な空白や改行を行っていたり、あるいは必要な空白や改行を出力していません。
[hr]
どなたか、教えていただけないでしょうか
自分なりに考えた仕様...
*/
仕様を実装してみたものです。
以上の競技プログラミングにチャレンジしたのですが、間違っているらしいのです。
visual studio 2010 で、ビルドは通って、デバックでも 下の仕様は満たしていると思うのですが、次の判定が返って来ます。
[hr]
WA: Presentation Error
提出されたプログラムは、ほぼ受理される出力を行っていますが、余計な空白や改行を行っていたり、あるいは必要な空白や改行を出力していません。
[hr]
どなたか、教えていただけないでしょうか
自分なりに考えた仕様...
► スポイラーを表示
[wave=blue]/*...分析編
操作が N, E, S, W の四種ある
参照 ITP1_11_A イラスト
操作が「N」「N」と続いた時を考える...
結果サイコロは反転している。
同じ操作が二度続いた場合、サイコロは反転する。
....四度続いた場合、サイコロは一周し操作前の状態に戻る。
操作の順番に注目してみる...
操作 ::操作後の上面
case_1 N ::2, E ::4, W ::2
case_2 N ::2, W ::3, E ::2
case_3 E ::4, N ::2, W ::1
case_4 E ::4, W ::1, N ::2
case_5 W ::3, N ::2, E ::1
case_6 W ::3, E ::1, N ::2
....操作はN, E, Wの三種類、順番を総当りで入れ替えたら６通りの結果となった。
....case_3, case_5 は「1」、その他は「2」となった。
....何故か!?
....操作W, E を『左右操作』、S, Nを『上下操作』と考える。その上で再検証..
....『左右操作』のE, W の間に『上下操作』たるN が割って入ったcase_3, case_5 の結果が「1」で、
....『左右操作』の一対たるW, E が連続している 他のcaseの結果が「2」だった。
....何故か!?
....『左右操作』の一対たるW, E が連続している とは、相殺され無かったことになる為である。
....操作が複数要求された場合、それらの操作を『左右操作』、『上下操作』に分類する。
....例「E,E,W,N,N,S,W,N」の場合
....『左右操作』、『上下操作』、『左右操作』、『上下操作』となります。
....上記の二項目で、それぞれ「ペアが揃ったら、その操作を消す」必要があります。
....その結果、例「E,E,W,N,N,S,W,N」が「E,N,W,N」となる。
....case_1,2,4,6 はいずれも『左右操作』の一対たるW, E が連続している 為に、
....操作か゜「N」だけになる...それが故に結果が等しい。
*/
/* ...実装計画編
実装どうしよう
central // 中央
on // 上側面
under // 下側面
right // 右側面
left // 左側面
rear // 背面
....上記の英単語を構造体のメンバ変数名に使いたい。
struct dice {
unsind char central,
unsind char under,
unsind char right,
unsind char left,
unsind char on,
unsind char rear,
};
各操作を次のように考えたい...
『図』
[上側面]
[左側面][中央面][右側面]
[下側面]
[背面]
『左右操作』の場合...
for W
[背面]←[左側面]←[中央面]←[右側面]←[背面]
for E
[背面]→[左側面]→[中央面]→[右側面]→[背面]
『上下操作』
for N
[背面]←[上側面]←[中央面]←[下側面]←[背面]
for S
[背面]→[上側面]→[中央面]→[下側面]→[背面]
入力された命令文字列を加工したい...
入力された文字列を一旦 str にバッファする。
『左右操作』または『上下操作』が連続している限り
str より文字を一文字ずつstr_b に読み込む。
str_b に『左右操作』が連続していた場合
「W」と「E」の個数を数える。
...「W」の個数をcou_A に代入し、cou_B に[code strlen(str_b) - cau_A]を代入しこれを「E」の個数とする。
[コード]
if (cou_A < cou_B) [操作 E を cou_A - cou_B 回 実行する。
else if (cou_A > cou_B) [操作 W を cou_B - cou_A回 実行する。
else 個数が一致した。
再び、str より文字列をstr_b に読み込み 処理を繰り返す。
操作が N, E, S, W の四種ある
参照 ITP1_11_A イラスト
操作が「N」「N」と続いた時を考える...
結果サイコロは反転している。
同じ操作が二度続いた場合、サイコロは反転する。
....四度続いた場合、サイコロは一周し操作前の状態に戻る。
操作の順番に注目してみる...
操作 ::操作後の上面
case_1 N ::2, E ::4, W ::2
case_2 N ::2, W ::3, E ::2
case_3 E ::4, N ::2, W ::1
case_4 E ::4, W ::1, N ::2
case_5 W ::3, N ::2, E ::1
case_6 W ::3, E ::1, N ::2
....操作はN, E, Wの三種類、順番を総当りで入れ替えたら６通りの結果となった。
....case_3, case_5 は「1」、その他は「2」となった。
....何故か!?
....操作W, E を『左右操作』、S, Nを『上下操作』と考える。その上で再検証..
....『左右操作』のE, W の間に『上下操作』たるN が割って入ったcase_3, case_5 の結果が「1」で、
....『左右操作』の一対たるW, E が連続している 他のcaseの結果が「2」だった。
....何故か!?
....『左右操作』の一対たるW, E が連続している とは、相殺され無かったことになる為である。
....操作が複数要求された場合、それらの操作を『左右操作』、『上下操作』に分類する。
....例「E,E,W,N,N,S,W,N」の場合
....『左右操作』、『上下操作』、『左右操作』、『上下操作』となります。
....上記の二項目で、それぞれ「ペアが揃ったら、その操作を消す」必要があります。
....その結果、例「E,E,W,N,N,S,W,N」が「E,N,W,N」となる。
....case_1,2,4,6 はいずれも『左右操作』の一対たるW, E が連続している 為に、
....操作か゜「N」だけになる...それが故に結果が等しい。
*/
/* ...実装計画編
実装どうしよう
central // 中央
on // 上側面
under // 下側面
right // 右側面
left // 左側面
rear // 背面
....上記の英単語を構造体のメンバ変数名に使いたい。
struct dice {
unsind char central,
unsind char under,
unsind char right,
unsind char left,
unsind char on,
unsind char rear,
};
各操作を次のように考えたい...
『図』
[上側面]
[左側面][中央面][右側面]
[下側面]
[背面]
『左右操作』の場合...
for W
[背面]←[左側面]←[中央面]←[右側面]←[背面]
for E
[背面]→[左側面]→[中央面]→[右側面]→[背面]
『上下操作』
for N
[背面]←[上側面]←[中央面]←[下側面]←[背面]
for S
[背面]→[上側面]→[中央面]→[下側面]→[背面]
入力された命令文字列を加工したい...
入力された文字列を一旦 str にバッファする。
『左右操作』または『上下操作』が連続している限り
str より文字を一文字ずつstr_b に読み込む。
str_b に『左右操作』が連続していた場合
「W」と「E」の個数を数える。
...「W」の個数をcou_A に代入し、cou_B に[code strlen(str_b) - cau_A]を代入しこれを「E」の個数とする。
[コード]
if (cou_A < cou_B) [操作 E を cou_A - cou_B 回 実行する。
else if (cou_A > cou_B) [操作 W を cou_B - cou_A回 実行する。
else 個数が一致した。
再び、str より文字列をstr_b に読み込み 処理を繰り返す。
*/
仕様を実装してみたものです。
► スポイラーを表示
#include <stdio.h>
#define SIZE_MAX 101
struct dice {
unsigned char central;
unsigned char under;
unsigned char right;
unsigned char left;
unsigned char on;
unsigned char rear;
} dice_1;
char str[SIZE_MAX],
str_b[SIZE_MAX];
int i, j,
cou_A,
cou_B,
work;
int main(void) {
fscanf(stdin, "%u %u %u %u %u %u", &dice_1.central,
&dice_1.under,
&dice_1.right,
&dice_1.left,
&dice_1.on,
&dice_1.rear);
fscanf(stdin, "%100s", str);
i = 0;
while (str[i]) {
j = 0;
if ((str_b[j] = str[i]) == 'W' || str_b[i] == 'E') {
while ((str_b[++j] = str[++i]) == 'W' || str_b[j] == 'E');
str_b[j] = '\0';
cou_A = cou_B = 0;
while (-1 < --j) {
if (str_b[j] == 'W') cou_A++;
else cou_B++;
}
if (cou_A < cou_B) { // E の方が多い
cou_B -= cou_A;
// 操作 E を cou_B回繰り返す。
while (cou_B--) {
work = dice_1.rear;
dice_1.rear = dice_1.right;
dice_1.right = dice_1.central;
dice_1.central = dice_1.left;
dice_1.left = work;
}
}
else if (cou_A > cou_B) { // W の方が多い
cou_A -= cou_B;
while (cou_A--) {
work = dice_1.rear;
dice_1.rear = dice_1.left;
dice_1.left = dice_1.central;
dice_1.central = dice_1.right;
dice_1.right = work;
}
}
} else { // str[j]が、'W','E'のいずれでも無い...つまり、'N','S'の場合
while ((str_b[++j] = str[++i]) == 'N' || str_b[j] == 'S');
str_b[j] = '\0';
cou_A = cou_B = 0;
while (-1 < --j) {
if (str_b[j] == 'N') cou_A++;
else cou_B++;
}
if (cou_A < cou_B) { // S の方が多い
cou_B -= cou_A;
// 操作 S を cou_B回繰り返す。
while (cou_B--) {
work = dice_1.rear;
dice_1.rear = dice_1.under;
dice_1.under = dice_1.central;
dice_1.central = dice_1.on;
dice_1.on = work;
}
}
else if (cou_A > cou_B) { // N の方が多い
cou_A -= cou_B;
while (cou_A--) {
work = dice_1.rear;
dice_1.rear = dice_1.on;
dice_1.on = dice_1.central;
dice_1.central = dice_1.under;
dice_1.under = work;
}
}
}
}
fprintf(stdout, "%d", dice_1.central);
return 0;
}