Problem A: Radix 3
問題概要 十進数の数値を、変則的な三進数で表す 一般的な三進数 : (2, 1, 0 が使える) 11 = 32×1 + 31×0 + 30×2 = (102)3 変則三進数 (GSC) : (1, 0, -1 が使える) 11 = 32×1 + 31×1 + 30×(-1) = (11-)GSC
ただの三進数なら 11 mod 3 = 2 3 mod 3 = 0 1 mod 3 = 1 11 / 3 = 3 3 / 3 = 1 1 / 3 = 0 ⇒ 終了 A: (1 0 2)3
これでもほとんど同じ 11 mod 3 = 2 4 mod 3 = 1 1 mod 3 = 1 11 / 3 = 3 4 / 3 = 1 1 / 3 = 0 ⇒ 終了 A: (1 1 - )GSC +1
負数のときは? (-11) mod 3 = -2 (-4) mod 3 = -1 (-1) mod 3 = 0 (-11) / 3 = -3 (-4) / 3 = -1 (-1) mod 3 = 0 (-1) / 3 = 0 ⇒ 終了 A: (- - 1 )GSC -1
ただし! 非除数が負の「除算」・「剰余算」の結果は ANSI C では実は不定 (CPU・処理系に依存) 関数 div() #include <stdlib.h> div_t div(int num, int denom); typedef struct div_t { int quot; /* 商 */ int rem; /* 剰余 */ };
負数のときは? (2) ...と、まじめにやってもよいが、 ぶっちゃけ 8 = (1 0 - )GSC -8 = ( - 0 1 )GSC ‘1’ を ‘-’ に ‘-’ を ‘1’ に、するだけ
ただし! (2) 今回の値の範囲は まあ、一般的な符号付整数の範囲ですが... それは実は (-231) ～ (231-1) 負数を整数に直して、 -(-231) = 231 : オーバーフロー! ってなことにはならないように...
出典 South Africa Regional Contest, 2002 Problem 1: Radix 3