当前位置: 代码迷 >> 综合 >> Blah数集
  详细解决方案

Blah数集

热度:52   发布时间:2024-01-15 08:30:39.0

【例2-2】Blah数集


时间限制: 1000 ms        内存限制: 65536 KB
提交数: 287     通过数: 144 

【题目描述】

大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对于以a为基的集合Ba定义如下:

(1)a是集合Ba的基,且a是Ba的第一个元素;

(2)如果x在集合Ba中,则2x+1和3x+1也都在集合Ba中;

(3)没有其他元素在集合Ba中了。

现在小高斯想知道如果将集合Ba中元素按照升序排列,第N个元素会是多少?

【输入】

输入包括很多行,每行输入包括两个数字,集合的基a(1≤a≤50))以及所求元素序号n(1≤n≤1000000)。

【输出】

对于每个输入,输出集合Ba的第n个元素值。

【输入样例】

1 100
28 5437

【输出样例】

418
900585

【来源】


No

【算法分析】

可以用两个队列a和b来存放新产生的数,然后通过比较大小决定是否输出,具体方法如下:

      (1)令fa和fb分别为队列a和队列b的头指针,它们的尾指针分别为ra和rb。初始时,X=1,fa=fb=ra=rb=1;                              

     (2)将2*x+1和3*x+1分别放入队列a和队列b的队尾,尾指针加1。                  即:a[r]←2*x+1,b[r]←3*x+1,r←r+1;

     (3)将队列a和队列b的头结点进行比较,可能有三种情况:

       (A)a[ha]>b[hb]     (B)a[ha]=b[hb]        (C)a[ha]<b[hb]

     将比较的小者取出送入X,取出数的队列的头指针相应加1。

     (4)重复(2),(3)直至取出第N项为止。

 

【代码实现】

 

 

#include<bits/stdc++.h>
using namespace std;
long long int a[1000005],b[1000005],x,fa=1,fb=1,ra=0,rb=0,total=1,n,i;//r头指针,f尾指针
int main()
{while(~scanf("%d%d",&x,&n)){fa=1;fb=1;ra=0;rb=0;total=1;//就是这里,记住第一个对,第二个错,检查清0while (total<n){a[++ra]=(x*2)+1;b[++rb]=3*x+1;if (a[fa]>b[fb])     x=b[fb++];else if (a[fa]<b[fb])  x=a[fa++];else{x=a[fa++];fb++;}total++;}cout<<x<<endl;}return 0;
}

 

  相关解决方案