hdu4814 Golden Radio Base
3233 ワード
2013年長春フィールド試合のB題.当時、問題提示の式をよく見なかったので、残念ながらこの実は水の問題を見逃してしまった.
10進数を入力し、出力を要求するφ進数で表すこの数は、φ黄金比例数1.61803399・・・です.
サンプル入出力では、次のように入力されます.
Sample Input 1 2 3 6 10 Sample Output 1 10.01 100.01 1010.0001 10100.0101
タイトルhintには2つの式が与えられています.φ + 1 = φ ^ 2および2*φ ^ 2 = φ ^ 3 + 1”
両式を左右に乗せればφ ^ n-2で、「φ ^ (n - 1) + φ ^ (n - 2) = φ ^ n」と「2*φ ^ n = φ ^ (n + 1) + φ ^ (n - 2)”
最初の式はφ進数は任意の2桁で連続した1,すなわち11に遭遇し,いずれも100に変換できる.
例えば例の2のφ進数表示は10.01で、3は11.01で、問題は出力に連続する1がないことを要求するので、以上の法則によって100.01に変換します.
2番目の式はφ進数の任意のビットの2は、1001に変換できます.
例えば4のφ進数は101.01、5は102.01と表すことができ、その2つの式に従って変換した後に1000.1001を得る.
このように6のφ進数表現は1001.101であり、変換は1010.001を得る.
もちろん、タイトルが与えるデータ範囲は10^9で、1から1つずつ推算することはできませんので、データ範囲によって2^0から2^29のφ進数表示で計算すればいいです.
例6:6=4+2
2のφ進数表示:10.01
4のφ進数表示:101.01
では6は10.01+101.01=111.02です
111.02 -> 1001.02 -> 1001.1001 -> 1010.0001
現場では問題の意味をよく理解していない一方で、ヒントの2つの式をどう使うかをよく考えていないので、浮動小数点演算を使うと思っていたが、実は考えを整理すれば単純なシミュレーションだった.
私のソースコードを添付します.
10進数を入力し、出力を要求するφ進数で表すこの数は、φ黄金比例数1.61803399・・・です.
サンプル入出力では、次のように入力されます.
Sample Input 1 2 3 6 10 Sample Output 1 10.01 100.01 1010.0001 10100.0101
タイトルhintには2つの式が与えられています.φ + 1 = φ ^ 2および2*φ ^ 2 = φ ^ 3 + 1”
両式を左右に乗せればφ ^ n-2で、「φ ^ (n - 1) + φ ^ (n - 2) = φ ^ n」と「2*φ ^ n = φ ^ (n + 1) + φ ^ (n - 2)”
最初の式はφ進数は任意の2桁で連続した1,すなわち11に遭遇し,いずれも100に変換できる.
例えば例の2のφ進数表示は10.01で、3は11.01で、問題は出力に連続する1がないことを要求するので、以上の法則によって100.01に変換します.
2番目の式はφ進数の任意のビットの2は、1001に変換できます.
例えば4のφ進数は101.01、5は102.01と表すことができ、その2つの式に従って変換した後に1000.1001を得る.
このように6のφ進数表現は1001.101であり、変換は1010.001を得る.
もちろん、タイトルが与えるデータ範囲は10^9で、1から1つずつ推算することはできませんので、データ範囲によって2^0から2^29のφ進数表示で計算すればいいです.
例6:6=4+2
2のφ進数表示:10.01
4のφ進数表示:101.01
では6は10.01+101.01=111.02です
111.02 -> 1001.02 -> 1001.1001 -> 1010.0001
現場では問題の意味をよく理解していない一方で、ヒントの2つの式をどう使うかをよく考えていないので、浮動小数点演算を使うと思っていたが、実は考えを整理すれば単純なシミュレーションだった.
私のソースコードを添付します.
#include <cstdio>
#include <cstring>
#define LEN 100
#define HLE 50
using namespace std;
typedef struct fbn {
int a[LEN];
int pn;
void init() {
memset(a, 0, sizeof(a));
pn = 0;
}
void print() {
bool b = false;
for (int i = 0; i < HLE; i++) {
if (a[i] != 0) b = true;
if (b == true) printf("%d", a[i]);
}
if (pn != 0) {
printf(".");
for (int i = 0; i < pn; i++)
printf("%d", a[i + HLE]);
}
printf("
");
}
}FBN;
bool check(FBN a)
{
bool t = true;
for (int i = 0; i < LEN; i++) {
if (a.a[i] > 1) {t = false; break;}
if ((i != LEN - 1) && a.a[i] == 1 && a.a[i + 1] == 1) {t = false; break;}
}
return t;
}
FBN normalize(FBN a)
{
int t;
do {
for (int i = 0; i < LEN; i++) {
if (a.a[i] > 1) {
t = a.a[i] / 2;
a.a[i] %= 2;
a.a[i - 1] += 1;
a.a[i + 2] += 1;
}
if ((i != LEN - 1) && a.a[i] == 1 && a.a[i + 1] == 1) {
a.a[i - 1] += 1;
a.a[i] = 0;
a.a[i + 1] = 0;
}
}
} while (!check(a));
for (int i = LEN - 1; i >= HLE; i--) {
if (a.a[i] != 0) {
a.pn = i - HLE + 1;
break;
}
}
return a;
}
FBN add(FBN a, FBN b)
{
FBN ans;
ans.init();
for (int i = 0; i < LEN; i++) {
ans.a[i] = a.a[i] + b.a[i];
}
ans = normalize(ans);
return ans;
}
int main()
{
int n, i;
FBN twob[30], ans;
for (i = 0; i < 30; i++) twob[i].init();
twob[0].a[HLE - 1] = 1;
twob[0].pn = 0;
for (i = 1; i < 30; i++) {
twob[i] = add(twob[i - 1], twob[i - 1]);
}
while (scanf("%d", &n) != EOF) {
i = 0;
ans.init();
while (n > 0) {
if ((n & 1) == 1) ans = add(ans, twob[i]);
n >>= 1;
i++;
}
ans.print();
}
return 0;
}