Advertisement
a53

nano

a53
Aug 19th, 2017
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.13 KB | None | 0 0
  1. #include <cstdio>
  2. #define NMax 101
  3. #define GRUPATE 8
  4. #define BAZA 100000000
  5. using namespace std;
  6. typedef unsigned long long int Huge[NMax];
  7. FILE *f=fopen("nano.in","r");
  8. FILE *g=fopen("nano.out","w");
  9. int n,x;
  10. Huge y,m,S,D,unu,patrat;
  11.  
  12. void Atrib0(Huge H) {
  13. H[0] = 0;
  14. }
  15.  
  16. void AtribHuge(Huge H, Huge X)
  17. // H <- X
  18. {
  19. int i;
  20. for (i = 0; i <= X[0]; ++i) {
  21. H[i] = X[i];
  22. }
  23. }
  24.  
  25. void Add(Huge A, Huge B)
  26. /* A <- A+B */
  27. { int i,T=0;
  28.  
  29. if (B[0]>A[0]) // Daca A<B
  30. { for (i=A[0]+1;i<=B[0];) A[i++]=0; // atunci completez pe A cu zerouri nesemnificative
  31. A[0]=B[0];
  32. }
  33. else for (i=B[0]+1;i<=A[0];) B[i++]=0; // altfel completez pe B cu zerouri nesemnificative
  34. for (i=1;i<=A[0];i++) // Efectuam adunarea tinand cont de transportllu T
  35. { A[i]+=B[i]+T;
  36. T=A[i]/BAZA;
  37. A[i]%=BAZA;
  38. }
  39. if(T) A[++A[0]]=T; // Adaug si llutimllu transport T
  40. }
  41.  
  42. void Subtract(Huge A, Huge B)
  43. /* A <- A-B */
  44. { int i, T=0;
  45.  
  46. for (i=B[0]+1;i<=A[0];) B[i++]=0;
  47. for (i=1;i<=A[0];i++)
  48. A[i]+=(T=(A[i]-=B[i]+T)<0) ? 1 : 0;
  49. /* Adica A[i]=A[i]-(B[i]+T);
  50. if (A[i]<0) T=1; else T=0;
  51. if (T) A[i]+=BAZA; */
  52. while (!A[A[0]]) A[0]--;
  53. }
  54.  
  55. void MllutHuge(Huge A, Huge B, Huge C)
  56. /* C <- A x B */
  57. { int i,j,T=0;
  58.  
  59. C[0]=A[0]+B[0]-1;
  60. for (i=1;i<=A[0]+B[0];) C[i++]=0;
  61. for (i=1;i<=A[0];i++)
  62. for (j=1;j<=B[0];j++)
  63. C[i+j-1]+=A[i]*B[j];
  64. for (i=1;i<=C[0];i++)
  65. { T=(C[i]+=T)/BAZA;
  66. C[i]%=BAZA;
  67. }
  68. if (T) C[++C[0]]=T;
  69. }
  70.  
  71. int Divide(Huge A, int X)
  72. // A <- A/X si intoarce A%X
  73. {
  74. int i;
  75. int R=0;
  76. for(i=A[0];i;i--)
  77. {
  78. A[i]=(R=BAZA*R+A[i])/X;
  79. R%=X;
  80. }
  81. while(A[A[0]]==0&&A[0]>1)
  82. --A[0];
  83. return R;
  84. }
  85.  
  86. int Sgn(Huge H1,Huge H2)
  87. // Elimina zero-urile semnificative, daca exista
  88. {
  89. while(H1[0]&&!H1[H1[0]])
  90. H1[0]--;
  91. while(H2[0]&&!H2[H2[0]])
  92. H2[0]--;
  93. if(H1[0]<H2[0])
  94. return -1;
  95. else
  96. if(H1[0]>H2[0])
  97. return +1;
  98. for(int i=H1[0];i>0;--i)
  99. if (H1[i] < H2[i])
  100. return -1;
  101. else
  102. if(H1[i]>H2[i])
  103. return +1;
  104. return 0;
  105. }
  106.  
  107. void afisez(Huge x)
  108. {
  109. if(x[0]==0)
  110. fprintf(g,"%llu",0);
  111. else
  112. {
  113. fprintf(g,"%llu",x[x[0]]);
  114. for(int i=x[0]-1;i>=1;--i)
  115. {
  116. if(x[i]==0)
  117. fprintf(g,"%s","00000000");
  118. else
  119. if(x[i]<10)
  120. fprintf(g,"%s%llu","0000000",x[i]);
  121. else
  122. if(x[i]<100)
  123. fprintf(g,"%s%llu","000000",x[i]);
  124. else
  125. if(x[i]<1000)
  126. fprintf(g,"%s%llu","00000",x[i]);
  127. else
  128. if(x[i]<10000)
  129. fprintf(g,"%s%llu","0000",x[i]);
  130. else
  131. if(x[i]<100000)
  132. fprintf(g,"%s%llu","000",x[i]);
  133. else
  134. if(x[i]<1000000)
  135. fprintf(g,"%s%llu","00",x[i]);
  136. else
  137. if(x[i]<10000000)
  138. fprintf(g,"%s%llu","0",x[i]);
  139. else
  140. fprintf(g,"%llu",x[i]);
  141. }
  142. }
  143. fprintf(g,"%c",'\n');
  144. }
  145.  
  146. int cautare_binara()
  147. {
  148. int semn;
  149. unu[0]=1,unu[1]=1;
  150. AtribHuge(S,unu);
  151. AtribHuge(D,y);
  152. Add(unu,S);
  153. while(Sgn(S,D)!=1&&Sgn(unu,D)!=0)
  154. {
  155. AtribHuge(m,S);
  156. Add(m,D);
  157. Divide(m,2);
  158. MllutHuge(m,m,patrat);
  159. semn=Sgn(patrat,y);
  160. if (semn==0) // Verific daca mijlocllu la patrat este egal cu numarllu
  161. return 1;
  162. if (semn==1) // patrat<y => caut la stanga
  163. AtribHuge(D,m);
  164. if(semn==-1) // patrat>y => caut la dreapta
  165. AtribHuge(S,m);
  166. unu[0]=1,unu[1]=1;
  167. Add(unu,S);
  168. }
  169. return 0;
  170. }
  171.  
  172. int main()
  173. {
  174. fscanf(f,"%d",&n);
  175. int rest,cat,nr;
  176. for(int i=1;i<=n;++i)
  177. {
  178. fscanf(f,"%d\n",&x);
  179. char s[x+1];
  180. int indice=0;
  181. fscanf(f,"%s",s);
  182. rest=x%GRUPATE,cat=x/GRUPATE;
  183. if(rest)
  184. {
  185. y[0]=cat+1;
  186. nr=0;
  187. for(int k=1;k<=rest;++k)
  188. nr=nr*10+s[indice++]-'0';
  189. y[y[0]]=nr;
  190. for(int j=y[0]-1;j>=1;--j)
  191. {
  192. nr=0;
  193. for(int k=1;k<=GRUPATE;++k)
  194. nr=nr*10+s[indice++]-'0';
  195. y[j]=nr;
  196. }
  197. }
  198. else
  199. {
  200. y[0]=cat;
  201. for(int j=y[0];j>=1;--j)
  202. {
  203. nr=0;
  204. for(int k=1;k<=GRUPATE;++k)
  205. nr=nr*10+s[indice++]-'0';
  206. y[j]=nr;
  207. }
  208. }
  209. if(cautare_binara())
  210. afisez(y);
  211. }
  212. fclose(f);
  213. fclose(g);
  214. return 0;
  215. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement