Daily Archives: 1 2 月, 2013

fzu_noip 1033 (作业问题-拼最大的2,3,5倍数)

Posted on by

作业问题

时限：1s内存：32M

★问题描述:

小T很喜欢数学，每天老师刚布置完作业，他就开始思考，今天他遇到了困难。

现在有很多的数字，你的任务是找出由这些数字组成的最大的数，并且这个数必须能被2，3，5整除。你可以只用其中一部分的数，但不允许出现前导0。

★数据输入：

输入数据的第一行为一个整数N。(1<=N<=1000)表示给出N个数字，每个数字范围是0—9。接下来一行有N个数，数字由空格隔开。

★结果输出:

输出你找出的最大的数，如果不存在这样的数就输出-1。

输入示例

输出示例

1

0

0

11

3 4 5 4 5 3 5 3 4 4 0

5554443330

8

3 2 5 1 5 2 2 3

-1

 

裸裸的贪心。

满足能被2，5整除，当且仅当数中有0且放在末尾

满足能被3整除，要让sum%3=0.

显然要取尽可能多的位数，先判断是否能全取。

用a[i]表示数字i有几个，b[i]表示%3=i的数字有几个.

若全取后%3=1，则删1个%3=1或2个%3=2.优先删删除数字少的，次优先删数字尽量小的。

若无法全取，也不够删，则无解.

同理%3=2.

若有合法解，数字必从大到小排列。

由于不能有前导0，需特判0，0，0，0……的情况。

var
   a:array[0..9] of longint;
   b:array[0..2] of longint;
   n,i,j,p:longint;
procedure decrease(k:longint);
begin
   if (a[k]>0) then dec(a[k])
   else if (a[k+3]>0) then dec(a[k+3])
   else if (a[k+6]>0) then dec(a[k+6]);
end;
begin
   read(n);
   fillchar(a,sizeof(a),0);
   for i:=1 to n do
   begin
      read(j);
      inc(a[j]);  inc(b[j mod 3]);
   end;
   if (a[0]=0) then
   begin
      writeln('-1');
      halt;
   end;

   p:=b[1] mod 3+(b[2]*2) mod 3;
   if (p=1) then
   begin
      if (b[1]>0) then decrease(1)
      else if (b[2]>1) then begin decrease(2);decrease(2); end
      else
      begin
         writeln('-1');
         halt;
      end;
   end;
   if (p=2) then
   begin
      if (b[2]>0) then decrease(2)
      else if (b[1]>1) then begin decrease(1);decrease(1); end
      else
      begin
         writeln('-1');
         halt;
      end;
   end;

   p:=0;
   for i:=1 to 9 do inc(p,a[i]);
   if (p=0) then
   begin
      writeln('0');
      halt;
   end;


   for i:=9 downto 0 do
      for j:=1 to a[i] do write(i);
   writeln;







end.

fzu_noip 1032 (无穷数-进位判定)

Posted on by

无穷数

时限：1s内存：32M

★问题描述:

我们生成两个无穷大的数，第一个数是把所有的自然数链接起来组成的数字；第二个数是把所有自然数的平方连接起来组成的数。对这两个数求和，如下：

 123456789101112131415161718192021...

+ 149162536496481100121144169196225...

= 272619325597593231536305887388246...

现在给你一个整数k，问和从左往右数第k位的数码是多少？

★数据输入：

输入数据有多组，每组数据输入一行，有一个数k。对于100%的数据，k<=2147483647

★结果输出:

对于每组数据，输出一个整数N，从左往右数第k位的数码。

输入示例

输出示例

5

6

7

8

1

9

3

2
 
先算出第k位的Ai和Bi，然后相加，考虑是否加过头。
接下来用search_fi(k:longint) 判断第k位是否会令前一位进位，则


const
   a:array[1..19,1..2] of int64=((1,3),(4,9),(10,31),(32,99),(100,316),(317,999),(1000,3162),(3163,9999),(10000,31622),(31623,99999),(100000,316227),(316228,999999),(1000000,3162277),(3162278,9999999),(10000000,31622776),(31622777,99999999),
   (100000000,316227766),(316227767,999999999),(1000000000,2147483647));
var
   k:longint;
function search_ai(k:longint):longint;
var
   i,j,d,k2,g:int64;
begin
   d:=1;i:=9;
   while (true) do
   begin
      if (k-d*i>0) then
      begin
         dec(k,d*i);
         i:=i*10;inc(d);
      end
      else break;
   end;
   k2:=i div 9+(k-1) div d;
   g:=(k-1) mod d+1;
   g:=d-g+1;
   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
{
function search_bi(k:longint):longint;
var
   i,j:int64;
   head:longint;
begin
   head:=1;j:=10; i:=1;
   while (i<=2147483647 ) do
   begin
      if ((i*i) div j>0) then
      begin
         write('(',head,',',i-1,')',',');
         head:=i; j:=j*10;
      end;
      inc(i);
   end;
end;      }


function search_bi(k:longint):longint;
var
   i:longint;
   g,k2:int64;
begin
   i:=1;
   while (k>i*(a[i,2]-a[i,1]+1)) do
   begin
      dec(k,i*(a[i,2]-a[i,1]+1));
      inc(i);
   end;

   k2:=(k-1) div i+1;
   k2:=a[i,1]-1+k2;
   k2:=k2*k2;
   g:=(k-1) mod i+1;
   g:=i-g+1;

   while (g>1) do begin k2:=k2 div 10;dec(g); end;
   exit(k2 mod 10);
end;
function search_fi(k:longint):longint;
var
   i:longint;
begin
   i:=search_ai(k)+search_bi(k);
   if (i<=8) then exit(0)
   else if (i>9) then exit(1)
   else exit(search_fi(k+1));

end;
begin
//   assign(output,'dabiao.out');
//   rewrite(output);

   while not eof do
   begin
      readln(k);
      writeln((search_bi(k)+search_ai(k)+search_fi(k+1)) mod 10);


   end;

//   search_bi(1);
//close(output);
end.