本文主要是介绍Closest,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
考虑两个n位的十进制正整数A和B,都没有前导0。我们需要找到两个最近的靠近A的n位数(第一个比A大或与A相等,第二个严格比A小),使得它们的十进制表示是B中所有数字的某个排列。
比如说,假如A=3022并且B=1232,用B的数字我们可以获得以下的4位数字:1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212和3221。最小的比A大或者和A相等的数,且用B中的数字组成的是3122,并且最大的严格比A小的数是2321。如果A=1232而且B=3022,可能的数字是2023, 2032, 2203, 2230, 2302, 2320, 3022, 3202和3220。在用B中数字组成的数中,最小的比A大或与A相等的数是2023,没有比A小的数。
对于给定的A和B,写一个程序closest找到这些“最靠近A”的数字,或者判断它们中的一个不存在。
Input
输入文件closest.in包含2行:
第1行为一个正整数A。
第1行为一个正整数B。
(A,B均为n位的正整数)
Output
输出文件closest.out共有2行。
第一行:最小的不比A小的n位数,没有前导0,包含B中的所有字符,以某一顺序排列。如果这样的数不存在,那么输出0。
第二行:最大的比A小的n位数,没有前导0,包含B中的所有字符,以某一顺序排列。如果这样的数不存在,那么输出0。
Sample Input
输入样例1
3075
6604
输入样例2
3000203
4562454
Sample Output
输出样例1
4066
0
输出样例2
4244556
2655444
Hint
【限制】
100%的数据满足:1<=n<=60
程序:
vara,b,p,v:array[0..60] of longint;n,i,j,k,u,min,max:longint;s:char;
beginassign(input,'closest.in');assign(output,'closest.out');reset(input);rewrite(output);while not eoln dobegininc(n);read(s);a[n]:=ord(s)-ord('0');end;readln;for i:=1 to n dobeginread(s);b[i]:=ord(s)-ord('0');end;for i:=1 to n-1 dofor j:=i+1 to n doif b[i]>b[j] thenbeginb[0]:=b[i];b[i]:=b[j];b[j]:=b[0];end;for i:=1 to n dobeginmin:=maxlongint;u:=0;for j:=1 to n doif (b[j]<min)and(v[j]=0)and(b[j]>=a[i]) thenbeginmin:=b[j];u:=j;end;if u>0 thenbeginp[i]:=u;v[u]:=i;end;if (min>a[i])and(u>0) thenbeginfor j:=1 to i dowrite(b[p[j]]);for j:=1 to n doif v[j]=0 then write(b[j]);break;end;if u=0 thenbeginfor j:=i-1 downto 1 dobeginv[p[j]]:=0;min:=maxlongint;u:=0;for k:=1 to n doif (v[k]=0)and(b[k]<min)and(b[k]>a[j]) thenbeginmin:=b[k];u:=k;end;if u>0 thenbeginv[u]:=j;p[j]:=u;for k:=1 to j dowrite(b[p[k]]);for k:=1 to n doif v[k]=0 then write(b[k]);break;end;end;if u=0 then write(0);break;end;if i=n thenfor j:=1 to n dowrite(a[j]);end;writeln;fillchar(v,sizeof(v),0);fillchar(p,sizeof(p),0);for i:=1 to n dobeginmax:=-1;u:=0;for j:=1 to n doif (b[j]>max)and(b[j]<=a[i])and(v[j]=0) thenbeginif (i=1)and(b[j]=0) then continue;max:=b[j];u:=j;end;if u>0 thenbeginp[i]:=u;v[u]:=i;end;if (u>0)and(max<a[i]) thenbeginfor j:=1 to i dowrite(b[p[j]]);for j:=n downto 1 doif v[j]=0 then write(b[j]);break;end;if (u=0)or(i=n) thenbeginfor j:=i downto 1 dobeginv[p[j]]:=0;max:=-1;u:=0;for k:=1 to n doif (b[k]>max)and(b[k]<a[j])and(v[k]=0) thenbeginif (j=1)and(b[k]=0) then continue;max:=b[k];u:=k;end;if u>0 thenbeginv[u]:=j;p[j]:=u;for k:=1 to j dowrite(b[p[k]]);for k:=n downto 1 doif v[k]=0 then write(b[k]);break;end;end;if u=0 then write(0);break;end;end;writeln;close(input);close(output);
end.
这篇关于Closest的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!