ブルーブリッジカップ2013年C++B組9_帯分数
1625 ワード
帯分数
タイトルの説明
100は帯分数の形式として表すことができる:100=3+69258/714、また:100=82+3546/197と表すことができ、注意特徴:帯分数のうち、数字1~9はそれぞれ現れ、1回しか現れない(0を含まない).このような帯分数は,100に11種類の表現がある.タイトル要求:標準入力から正整数N(N<1000*1000)プログラムを読み込んで、この数字をデジタル1~9で繰り返して漏れなく帯分数で表す全種数を出力します.注意:各表示を出力する必要はありません.どれだけの表示方法があるかを統計します.
例
まず思いついた最も素朴なやり方はタイムアウトしてもっと良い方法を探求しています
タイトルの説明
100は帯分数の形式として表すことができる:100=3+69258/714、また:100=82+3546/197と表すことができ、注意特徴:帯分数のうち、数字1~9はそれぞれ現れ、1回しか現れない(0を含まない).このような帯分数は,100に11種類の表現がある.タイトル要求:標準入力から正整数N(N<1000*1000)プログラムを読み込んで、この数字をデジタル1~9で繰り返して漏れなく帯分数で表す全種数を出力します.注意:各表示を出力する必要はありません.どれだけの表示方法があるかを統計します.
例
:100
:11
: :105
:6
まず思いついた最も素朴なやり方はタイムアウトしてもっと良い方法を探求しています
( )
#include
using namespace std;
bool num[10]; //1-9
bool isused(int input,bool copy[])
{
do
{
if (copy[input % 10] == true || input % 10 == 0)
return true;
else
copy[input % 10] = true;
input = input / 10;
} while (input!=0);
return false;
}
int cal(int input)
{
bool copy[10];
long long int upper;
long long int lower;
long long int temp;
long long int flag = 0;
long long int cnt = 0;
for (int lower = 1; lower <= 987654321; lower++)
{
flag = 0;
upper = lower * input;
memcpy(copy, num, sizeof(num));
if (isused(upper, copy))
flag = 1;
if (isused(lower, copy))
flag = 1;
if (flag == 0)
cnt++;
}
return cnt;
}
int main()
{
long long int input;
long long int fen;
long long int temp;
long long int flag;
long long int cnt = 0;
cin >> input;
for (int i = 1; i < input; i++)
{
flag = 0;
fen = input - i; //fen
/* true*/
memset(num, 0, sizeof(num));
if (isused(i, num))
flag = 1;
/* fen num */
if (flag == 0)
{
cnt += cal(fen);
}
//cout << i << " " << fen << endl;
}
cout << cnt;
}