整数対(hdu 1271)法則を探す
6943 ワード
整数ペア
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2127 Accepted Submission(s): 844
Problem Description
Gardonと希ちゃんはゲームをしていて、Gardonは勝手にAを数えて(トップは0にできない)、それを1つの数字を消してからもう1つの数Bを得て、彼はAとBの和Nを希ちゃんに教えて、希ちゃんに彼の思っていた数字を推測させました.しかし公平のため、希ちゃんが答えた数はAではないが、同じようにその条件(その中の1つを除いてB、AとBの和はN)に達することができて、同じように希ちゃんの勝利です.また、希ちゃんは条件に合った数字を複数回答できれば、追加のキャンディを手に入れることができます.
だから今、希ちゃんはあなたがプログラムを書いて、彼女ができるだけ多くの解を見つけるのを助けてほしいと思っています.
例えば、Gardonが考えているのはA=31、B=3がヒヒN=34に伝え、
希ちゃんは31以外に27(27+7=34)と答えることができるので、希ちゃんは追加のキャンディを手に入れることができます.
Input
入力には複数のデータが含まれ、各データの1行に1つの数N(1<=N<=10^9)が含まれ、ファイルは0で終わる.
Output
各入力のNについて、要求に合致するすべての解を出力する(サイズ順に並べている)このような解がなければ、「No solution.」を出力する.
Sample Input
Sample Output
2回目はこの問題を見て、今考えをまとめてみましょう...
まずこのような問題を手に入れて、第一の感じは通常の方法ですることができなくて、タイムアウトは必然です!
では、考えてみましょう.
Aから削除された数bがk位であると仮定すると,Aを3つの部分,a低位,b削除位,c高位に分けることができる.
A == a + b * 10^k + c * 10^(k+1)
B == a + c * 10^k
N == A + B == 2 * a + b * 10^k +11 * c * 10^k
このうちbは1桁で、b*10^kは進位しません.Nに対して、10^kでNを除いて整頓すればb+11 cが得られ、11で除算すれば、商と残数はそれぞれcとbになります.
しかし、ここで問題があるaは10^k未満の数で間違いないが、2 aがキャリーを生じる可能性があり、さっき求めたb+11 cを汚染している.
しかし大丈夫です.進位は最大1、つまりbは実際にb+1、bはもともと最大9なので、今では10でも、
11を除いて求めたcにも影響しない.従ってcの値は信頼できる.そして、2 aのキャリーと非キャリーの2つのケースに基づいて、bが-1であるか否かをそれぞれ考慮し、
もう一度aを求めて、試算すればいいです.
反復kは最低位から最高位まで1回やれば,可能なすべてのAを見つけることができる.
最後にソート!忘れないで!
ps:
http://acm.hdu.edu.cn/showproblem.php?pid=1271
詳細は、コードを参照してください.
やはりもっと問題を作って、もっとまとめましょう.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2127 Accepted Submission(s): 844
Problem Description
Gardonと希ちゃんはゲームをしていて、Gardonは勝手にAを数えて(トップは0にできない)、それを1つの数字を消してからもう1つの数Bを得て、彼はAとBの和Nを希ちゃんに教えて、希ちゃんに彼の思っていた数字を推測させました.しかし公平のため、希ちゃんが答えた数はAではないが、同じようにその条件(その中の1つを除いてB、AとBの和はN)に達することができて、同じように希ちゃんの勝利です.また、希ちゃんは条件に合った数字を複数回答できれば、追加のキャンディを手に入れることができます.
だから今、希ちゃんはあなたがプログラムを書いて、彼女ができるだけ多くの解を見つけるのを助けてほしいと思っています.
例えば、Gardonが考えているのはA=31、B=3がヒヒN=34に伝え、
希ちゃんは31以外に27(27+7=34)と答えることができるので、希ちゃんは追加のキャンディを手に入れることができます.
Input
入力には複数のデータが含まれ、各データの1行に1つの数N(1<=N<=10^9)が含まれ、ファイルは0で終わる.
Output
各入力のNについて、要求に合致するすべての解を出力する(サイズ順に並べている)このような解がなければ、「No solution.」を出力する.
Sample Input
34
152
21
0Sample Output
27 31 32
126 136 139 141
No solution.
2回目はこの問題を見て、今考えをまとめてみましょう...
まずこのような問題を手に入れて、第一の感じは通常の方法ですることができなくて、タイムアウトは必然です!
では、考えてみましょう.
Aから削除された数bがk位であると仮定すると,Aを3つの部分,a低位,b削除位,c高位に分けることができる.
A == a + b * 10^k + c * 10^(k+1)
B == a + c * 10^k
N == A + B == 2 * a + b * 10^k +11 * c * 10^k
このうちbは1桁で、b*10^kは進位しません.Nに対して、10^kでNを除いて整頓すればb+11 cが得られ、11で除算すれば、商と残数はそれぞれcとbになります.
しかし、ここで問題があるaは10^k未満の数で間違いないが、2 aがキャリーを生じる可能性があり、さっき求めたb+11 cを汚染している.
しかし大丈夫です.進位は最大1、つまりbは実際にb+1、bはもともと最大9なので、今では10でも、
11を除いて求めたcにも影響しない.従ってcの値は信頼できる.そして、2 aのキャリーと非キャリーの2つのケースに基づいて、bが-1であるか否かをそれぞれ考慮し、
もう一度aを求めて、試算すればいいです.
反復kは最低位から最高位まで1回やれば,可能なすべてのAを見つけることができる.
最後にソート!忘れないで!
ps:
http://acm.hdu.edu.cn/showproblem.php?pid=1271
詳細は、コードを参照してください.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
/*
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
*/
int cmp(int a,int b)
{
return a<b;
}
int main()
{
int n,i,k,a,b,c,x[20];//c ，b ，a
while(scanf("%d",&n)&&n)
{
i=0;
for(k=1;k<=n;k*=10)//k k
{
c=(n/k)/11;
b=n/k-c*11;
if((b!=0||c!=0)&&b<10)//
{
a=(n-b*k-c*11*k)/2;
if(2*a+b*k+c*11*k==n)
x[i++]=a+b*k+c*10*k;
}
b--;// （ ， ， 1）
if((b!=0||c!=0)&&b>=0)
{
a=(n-b*k-c*11*k)/2;
if(2*a+b*k+c*11*k==n)
x[i++]=a+b*k+c*10*k;
}
}
if(i)
{
// qsort(x,i,sizeof(x[0]),cmp);
sort(x,x+i,cmp);
printf("%d",x[0]);
for(k=1;k<i;++k)
{
if(x[k]!=x[k-1]) printf(" %d",x[k]);
}
puts("");
}
else
printf("No solution.
");
}
return 0;
}やはりもっと問題を作って、もっとまとめましょう.