csuoj 1114: 平方根大搜索

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1114

1114: 平方根大搜索

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 118  Solved: 60
[Submit][Status][Web Board]

Description

在二进制中,2的算术平方根,即sqrt(2),是一个无限小数1.0110101000001001111...

给定一个整数n和一个01串S,你的任务是在sqrt(n)的小数部分(即小数点之后的部分)中找到S第一次出现的位置。如果sqrt(n)是整数,小数部分看作是无限多个0组成的序列。

Input

输入第一行为数据组数T (T<=20)。以下每行为一组数据,仅包含一个整数n (2<=n<=1,000,000)和一个长度不超过20的非空01串S。

Output

对于每组数据,输出S的第一次出现中,第一个字符的位置。小数点后的第一个数字的位置为0。输入保证答案不超过100。

Sample Input

2
2 101
1202 110011

Sample Output

2
58

HINT

Source

湖南省第八届大学生计算机程序设计竞赛

分析;

数字比较大,开始打算用数组模拟,WA啦,后来想到用Java的BigDecimal类实现(可是还是没有实现,因为BigDecimal开根号不能实现,后来看别人用函数模拟了一个)。

AC代码:

C++版:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <sstream>
  5 #include <algorithm>
  6 #include <cmath>
  7 using namespace std;
  8 int a1[10010],a2[10010],b[10000],c[10000],l1,l2,s[110000];
  9 int l3,l4,l5,point,point2,point3,point1;
 10 char ans[1000];
 11 char ss[23];
 12 int chengfa()
 13 {
 14     int pos,i,j;
 15     memset(s,0,sizeof(s));
 16     for (i=1;i<=l4;i++)
 17         for (j=1,pos=i;j<=l4;j++)
 18             s[pos++]+=a2[i]*a2[j];
 19     pos-=1;
 20     for (i=1;i<=pos;i++)
 21     if (s[i]>=10)
 22     {
 23         if (i==pos) pos++;
 24         s[i+1]+=s[i]/10;
 25         s[i]%=10;
 26     }
 27     return pos;
 28 }
 29 void jia()
 30 {
 31     int p=1,i;
 32     if (point > point1)
 33     {
 34         for (i=1;i<=point - point1;i++)
 35             a2[p++]=a1[i];
 36         int tt=1;
 37         for (i=point - point1+1;i<=l1;i++)
 38             a2[p++]=a1[i]+c[tt++];
 39         point2=point;
 40     }
 41     else
 42     {
 43         for (i=1;i<=point1-point;i++)
 44             a2[p++]=c[i];
 45         int tt=i;
 46         for (i=1;i<=l1;i++)
 47             a2[p++]=a1[i]+c[tt++];
 48         point2=point1;
 49     }
 50     int kk=0;
 51     p--;
 52     for (i=1;i<=p;i++)
 53     {
 54         a2[i]+=kk;
 55         kk=a2[i]/10;
 56         a2[i]%=10;
 57     }
 58     if (kk!=0) a2[++p]=kk;
 59     l4=p;
 60 }
 61 int gobj()
 62 {
 63     int sl=l5,bl=l2;
 64     if (sl-point3>bl) return 1;
 65     else if (sl-point3<bl) return -1;
 66     while (sl>0 && bl>0)
 67     {
 68         if (s[sl]>b[bl]) return 1;
 69         if (s[sl]<b[bl]) return -1;
 70         sl--;bl--;
 71     }
 72     if (sl==0) return 0;
 73     else return 1;
 74 }
 75 int main()
 76 {
 77     int T,n;
 78     scanf("%d",&T);
 79     while (T--)
 80     {
 81         memset(ans,0,sizeof(ans));
 82         memset(a1,0,sizeof(a1));
 83         memset(a2,0,sizeof(a2));
 84         memset(c,0,sizeof(c));
 85         memset(b,0,sizeof(b));
 86         scanf("%d",&n);
 87         getchar();
 88         scanf("%s",&ss);
 89         int m=sqrt(n);
 90         int mm=m;
 91         int j=1;
 92         l1=0;
 93         point=0;
 94         while (mm)
 95         {
 96             a1[j++]=mm % 10;
 97             mm/=10;
 98             l1++;
 99         }
100         point=0;
101         mm=n;
102         j=1;l2=0;
103         while (mm)
104         {
105             b[j++]=mm%10;
106             mm/=10;
107             l2++;
108         }
109         c[1]=1;l3=1;
110         int i;
111         for (i=1;i<=130;i++)
112         {
113             for (j=1;j<=l3;j++)
114                 c[j]*=5;
115             int kk=0;
116             for (j=1;j<=l3;j++)
117             {
118                 c[j]+=kk;
119                 kk=c[j]/10;
120                 c[j]=c[j]%10;
121             }
122             if (kk) c[++l3]=kk;
123             point1=i;
124             jia();
125             /*for (j=l4;j>0;j--)
126             {
127                 if (point2==j) cout<<".";
128                 printf("%d",a2[j]);
129             }
130             cout<<endl;*/
131             l5=chengfa(); //平方后长度
132             point3=2*point2; //平方后小数点位置
133             /*for (j=l5;j>0;j--)
134             {
135                 if (point3==j) cout<<".";
136                 printf("%d",s[j]);
137             }
138             cout<<endl;*/
139             int re=gobj();
140             if (re==1) //1:s>b -1:s<b
141                 ans[i-1]=‘0‘;
142             else if (re==-1)
143             {
144                 ans[i-1]=‘1‘;
145                 memset(a1,0,sizeof(a1));
146                 for (j=1;j<=l4;j++)
147                     a1[j]=a2[j];
148                 l1=l4;
149                 point=point2;
150             }
151             else break;
152         }
153         for (j=i;j<=130;j++)
154             ans[i]=‘0‘;
155         ans[130]=‘\0‘;
156         //cout<<ans<<endl;
157         cout<<strstr(ans,ss) - ans << endl;
158     }
159     return 0;
160 }

Java版:

  1 import java.util.*;
  2 import java.math.*;
  3 public class Main {
  4     static String tob(BigDecimal d)
  5     {
  6         String s=new String();
  7         int n=150;
  8         while(!d.equals(BigDecimal.ZERO)&&n--!=0)
  9         {
 10             d=d.multiply(BigDecimal.valueOf(2));
 11             BigInteger x=d.toBigInteger();
 12             s+=x;
 13             d=d.subtract(BigDecimal.valueOf(x.longValue()));
 14         }
 15         return s;
 16     }
 17     public static BigDecimal culsqrt(int num)
 18     {
 19
 20
 21         return sqrtMathod(num);
 22
 23     }
 24
 25
 26     public static BigDecimal sqrtMathod(int num)
 27     {
 28         BigDecimal sqrtNum = BigDecimal.valueOf(-1);
 29         boolean isFindSqrt = false;
 30
 31
 32         // get int sqrt num
 33         double tempSqrt = 0;
 34         if (num > 0)
 35         {
 36             if (num == 1)
 37             {
 38                 return BigDecimal.valueOf(1);
 39             }
 40             else
 41             {
 42                 for (int j = 0; j <= num / 2 + 1; j++)
 43                 {
 44                     if (j * j == num)
 45                     {
 46                         sqrtNum = BigDecimal.valueOf(j);
 47                         isFindSqrt = true;
 48                         break;
 49                     }
 50                     if (j * j > num)
 51                     {
 52                         tempSqrt = j - 1;
 53                         break;
 54                     }
 55                 }
 56             }
 57         }
 58
 59
 60         if (!isFindSqrt)
 61         {
 62             sqrtNum = recuFindSqrt(num, BigDecimal.valueOf(tempSqrt), isFindSqrt, BigDecimal.valueOf(1));
 63         }
 64
 65
 66         return sqrtNum;
 67     }
 68
 69
 70     private static BigDecimal recuFindSqrt(int num, BigDecimal sqrtValue, boolean isFindSqrt, BigDecimal ac)
 71     {
 72         ac = ac.multiply(BigDecimal.valueOf(10));
 73         BigDecimal tempSqrt = BigDecimal.valueOf(0);
 74         for (int i = 0; i < 10; i++)
 75         {
 76             tempSqrt = sqrtValue .add(BigDecimal.valueOf(i).divide(ac) );
 77             if (tempSqrt .multiply(tempSqrt) .equals(BigDecimal.valueOf(num)))
 78             {
 79                 isFindSqrt = true;
 80                 sqrtValue = tempSqrt;
 81             }
 82             else if (tempSqrt .multiply(tempSqrt) .compareTo(BigDecimal.valueOf(num))==1)
 83             {
 84                 tempSqrt = sqrtValue.add(BigDecimal.valueOf(i - 1) .divide( ac));
 85                 sqrtValue = tempSqrt;
 86                 break;
 87             }
 88         }
 89
 90
 91         BigDecimal temp = tempSqrt;
 92         if (temp.toString().length() <= 150 && !isFindSqrt)
 93         {
 94             sqrtValue = recuFindSqrt(num, tempSqrt, isFindSqrt, ac);
 95         }
 96
 97
 98         return sqrtValue;
 99     }
100
101
102     public static double add(double v1, double v2)
103     {
104         BigDecimal b1 = new BigDecimal(Double.toString(v1));
105         BigDecimal b2 = new BigDecimal(Double.toString(v2));
106         return b1.add(b2).doubleValue();
107     }
108
109     public static void main(String[] args) {
110         Scanner in= new Scanner(System.in);
111         int t;
112         int n;
113         String st;
114         t=in.nextInt();
115         while(t--!=0)
116         {
117             n=in.nextInt();
118             st=in.next();
119             BigDecimal d=culsqrt(n);
120             BigInteger x=d.toBigInteger();
121             d=d.subtract(BigDecimal.valueOf(x.longValue()));
122             String tobs=tob(d);
123             System.out.println(tobs.indexOf(st));
124         }
125     }
126 }

时间: 04-29

csuoj 1114: 平方根大搜索的相关文章

网络空间大搜索技术

由于泛在网络空间.网络应用模式和大数据的发展,国内研究人员对网络空间搜索技术有了新的认识,逐渐形成了网络空间智慧搜索暨网络空间大搜索技术. 国家自然科学基金委员会第120期双清论坛于9月28日-29日在北京召开.本次论坛主题为网络空间智慧搜索基础研究,共邀请了国内外25所大学和科研机构的41位著名专家参会.本次论坛由信息科学部.管理科学部.地球科学部.数理科学部和政策局联合主办,论坛主席由方滨兴院士.吴曼青院士.贾焰教授和陈熙霖研究员共同担任. 论坛开幕式由信息二处刘克处长主持,信息科学部常务副

UVa 12505 Searching in sqrt(n)

传送门 一开始在vjudge上看到这题时,标的来源是CSU 1120,第八届湖南省赛D题“平方根大搜索”.今天交题时CSU突然跪了,后来查了一下看哪家OJ还挂了这道题,竟然发现这题是出自UVA的,而且用的原题. ------------------------------------------------------------------------------------------------------------------ time limit 5s In binary, the

详谈京东的商品搜索系统架构设计

京东商品搜索引擎是搜索推荐部自主研发的商品搜索引擎,主要功能是为海量京东用户提供精准.快速的购物体验.虽然只有短短几年的时间,我们的搜索引擎已经经过了多次618店庆和双11的考验,目前已经能够与人们日常使用的如谷歌.百度等全文搜索引擎相比,我们的产品与其有相通之处,比如涵盖亿级别商品的海量数据.支持短时超高并发查询.又有自己的业务特点: 海量的数据,亿级别的商品量: 高并发查询,日PV过亿: 请求需要快速响应. 搜索已经成为我们日常不可或缺的应用,很难想象没有了Google.百度等搜索引擎,互联

solr入门教程

Solr 本文介绍solr的功能使用及相关注意事项;主要包括以下内容:环境搭建及调试;两个核心配置文件介绍;维护索引;查询索引,和在查询中可以应用的高亮显示.拼写检查.搜索建议.分组统计.拼音检索等功能的使用方法. 1. Solr 是什么? Solr它是一种开放源码的.基于 Lucene Java 的搜索服务器,易于加入到 Web 应用程序中.Solr 提供了层面搜索(就是统计).命中醒目显示并且支持多种输出格式(包括XML/XSLT 和JSON等格式).它易于安装和配置,而且附带了一个基于HT

Solr调研总结(转)

Solr调研总结 开发类型 全文检索相关开发 Solr版本 4.2 文件内容 本文介绍solr的功能使用及相关注意事项;主要包括以下内容:环境搭建及调试.两个核心配置文件介绍.中文分词器配置.维护索引.查询索引,高亮显示.拼写检查.搜索建议.分组统计.自动聚类.相似匹配.拼音检索等功能的使用方法. 在代码文本框中如有显示不全的,请在文本框中按Ctrl+A再复制. 版本 作者/修改人 日期 V1.0 gzk 2013-06-04 1. Solr 是什么? Solr它是一种开放源码的.基于 Luce

形状匹配

1.       Shape-Based matching的基本流程 HALCON提 供的基于形状匹配的算法主要是针对感兴趣的小区域来建立模板,对整个图像建立模板也可以,但这样除非是对象在整个图像中所占比例很大,比如像视频会议中人 体上半身这样的图像,我在后面的视频对象跟踪实验中就是针对整个图像的,这往往也是要牺牲匹配速度的,这个后面再讲.基本流程是这样的,如下所示: ⑴ 首先确定出ROI的矩形区域,这里只需要确定矩形的左上点和右下点的坐标即可,gen_rectangle1()这个函数就会帮助你

优秀的 Android 开源项目

摘要  转载http://www.trinea.cn/android/android-open-source-projects-view/,方便大家找到自己合适的资料 目录[-] 一.ListView 二.ActionBar 三.Menu 四.ViewPager .Gallery 五.GridView 六.ImageView 七.ProgressBar 八.其他 GitHub上优秀Android开源项目 3. Android开发神器 1.Xabber客户端 2.oschina客户端 3.手机安全

全文检索技术---Lucene

1       Lucene介绍 1.1   什么是Lucene Lucene是apache下的一个开源的全文检索引擎工具包.它为软件开发人员提供一个简单易用的工具包(类库),以方便的在目标系统中实现全文检索的功能. 1.2   全文检索的应用场景 1.2.1  搜索引擎 ©注意: Lucene和搜索引擎是不同的,Lucene是一套用java或其它语言写的全文检索的工具包.它为应用程序提供了很多个api接口去调用,可以简单理解为是一套实现全文检索的类库.搜索引擎是一个全文检索系统,它是一个单独运

Docker实践9:备份方案

1 两个文件系统 先提一下两个重要的文件系统概念,一个是aufs,一个是vfs. aufs是一个类似于Unionfs的可堆叠联合文件系统.它将多个目录整合成单一的目录.ubuntu对其有良好的支持,因此docker的镜像就存储在aufs文件系统下. vfs是linux的内核中一个重要概念,这个虚拟文件系统可以让open().read().write()等系统调用不用关心底层的存储介质和文件系统类型就可以工作的粘合层. 2 docker镜像与容器的存储 docker的层次结构如上图. docker