fork download
copy 
  1. def solve(input)
  2.   input=~/:/
  3.   n=$`.to_i
  4.   # `串に刺した状態での x座標→y座標リスト のハッシュ
  5.   hsk={}
  6.   $'.tr(?,,"").bytes.map{|c|c-(c<58?48:c<91?55:61)}.each_slice(2){|(x,y)|(hsk[x]||=[])<< y}
  7.   # '面積の最大・最小値、またそもそも条件に合う長方形があるかどうか
  8.   maxv,minv,notfound=0,0,true
  9.   # 端の処理を統一するため、座標 -1 と 62 を追加した x座標一覧
  10.   xvals=[-1]+hsk.keys.sort+[62]
  11.   xlim=xvals.size-2
  12.   # 串の左端に対するループ
  13.   1.upto(xlim) do |il|
  14.     vsk={}
  15.     bsup=0
  16.     # 串の右端に対するループ
  17.     il.upto(xlim) do |ir|
  18.       # 横方向に串を刺し、串毎の黒いマスの個数を更新 ( もはや x 座標は不要 )
  19.       hsk[xvals[ir]].each do |y|
  20.         vsk[y]=(vsk[y]||0)+1
  21.         bsup+=1
  22.       end
  23.       # trivialに黒いマスの個数が足りない場合はスキップ
  24.       next if bsup<n
  25.       # 最大・最小の幅を計算
  26.       w1,w2=xvals[ir+1]-xvals[il-1]-1,xvals[ir]-xvals[il]+1
  27.       yvals=[-1]+vsk.keys.sort+[62]
  28.       ylim=yvals.size-2
  29.       # 横向きの串の選択に関する尺取り法 ( juが串の上端、jdが下端のインデクス )
  30.       ju,jd,bnum=1,0,0
  31.       while ju<=ylim&&jd<=ylim
  32.         # 黒マスの個数が一致した場合に、面積を計算
  33.         if bnum==n
  34.           h1,h2=yvals[jd+1]-yvals[ju-1]-1,yvals[jd]-yvals[ju]+1
  35.           maxc,minc=h1*w1,h2*w2
  36.           if notfound
  37.             maxv,minv=maxc,minc
  38.             notfound=false
  39.           else
  40.             maxv=maxc if maxv<maxc
  41.             minv=minc if minv>minc
  42.           end
  43.         end
  44.         # 尺取り ( 伸長/縮小 ) を選択
  45.         if bnum<n
  46.           bnum+=vsk[yvals[jd+=1]]||0
  47.         else
  48.           bnum-=vsk[yvals[~-ju+=1]]||0
  49.         end
  50.       end
  51.     end
  52.   end
  53.   notfound ? ?-:[minv,maxv]*?,
  54. end
  55.  
  56. allcase=[
  57.  ["3:Oh,Be,AF,in,eG,ir,l5,Q8,mC,7T,Ty,tT", "108,1920"],
  58.  ["3:00,zz,0z,z0", "-"],
  59.  ["1:ho", "1,3844"],
  60.  ["2:am", "-"],
  61.  ["4:00,zz,0z,z0", "3844,3844"],
  62.  ["4:00,11,zz,yy,1y,y1", "3600,3721"],
  63.  ["2:00,01,10,11,yz,zy,yy,zz", "2,3660"],
  64.  ["2:AA,AB,BA,BB,SZ,SY,TZ,TY", "2,2046"],
  65.  ["3:Lw,qw,cw,Ow,2w,fw,yw,ow,Zw,iw", "7,2170"],
  66.  ["4:0o,0s,0x,0C,0L,0k,0V,0y,0m,0S", "9,2852"],
  67.  ["5:Tz,gz,Ez,Pz,3z,Jz,iz,Bz,ez,9z", "17,2604"],
  68.  ["6:mQ,mp,mv,mW,mo,mZ,mC,mc,mt,mH", "23,3100"],
  69.  ["5:a0,a4,aa,ac,ag,aB,aG,aK,aO,aY,az", "19,2480"],
  70.  ["10:Ep,Jx,Qh,M7,Zr,lk,yp,Ya,aW,J3,OJ", "1938,3720"],
  71.  ["5:00,01,10,0y,0z,1z,y0,z0,z1,yz,zz,zy", "3721,3721"],
  72.  ["7:00,01,10,0y,0z,1z,y0,z0,z1,yz,zz,zy", "-"],
  73.  ["8:00,01,10,0y,0z,1z,y0,z0,z1,yz,zz,zy,TE", "-"],
  74.  ["11:bU,cl,d5,Fn,NW,gA,2O,YU,H4,0y,qE,Hd,ZH", "1748,3658"],
  75.  ["12:SM,cf,AD,6P,cm,mo,if,s0,Mt,GJ,9m,Sp,lA,x4,NE", "1806,3186"],
  76.  ["2:00,I0,c0,z0,0I,II,cI,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "19,2520"],
  77.  ["3:00,I0,c0,z0,0I,II,cI,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "39,2562"],
  78.  ["5:00,I0,c0,z0,0I,II,cI,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "-"],
  79.  ["6:00,I0,c0,z0,0I,II,cI,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "741,3660"],
  80.  ["7:00,I0,c0,z0,0I,II,cI,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "-"],
  81.  ["7:00,I0,c0,z0,0I,II,cJ,zI,0c,Ic,cc,zc,0z,Iz,cz,zz", "1178,2623"],
  82.  ["13:Lk,y3,uO,Gk,sF,7y,ED,FP,rK,vw,Lo,kT,ib,MR,sC,Cu,xQ", "1794,3472"],
  83.  ["1:lz,en,81,M2,M1,8p,7m,ND,m0,gd,3v,hr,hA,Yr,XB,x2,AR,5Q,3V,B3", "1,1785"],
  84.  ["2:s1,Dx,yu,H8,c4,6C,95,FK,xV,Q7,h2,Wk,BI,i0,bl,9Q,KF,1q,52,PS,Jh", "6,1824"],
  85.  ["2:0R,20,fz,0a,0X,zp,P0,0b,0S,zw,e0,0G,g0,06,a0,Zz,zW,zn,00,z6,zq,U0", "2,3660"],
  86.  ["3:H5,jF,AT,HH,k7,Ho,Mz,07,Tt,Sq,Zh,Yt,e5,oS,qf,YY,JD,bP,s4,hB,TC,PW", "28,1224"],
  87.  ["4:oe,pg,Np,zP,ho,pe,OV,S0,oM,wO,pM,Ah,Vq,9d,6U,3I,C9,AR,1L,rg,69,as,Nx", "12,1989"],
  88.  ["2:n0,V0,zL,i0,4z,Nz,xz,z0,z1,0f,P0,zw,80,zC,zB,Az,0P,50,k0,rz,0D,jz,qz,E0", "2,2928"],
  89.  ["2:tz,0F,0y,zo,0K,01,qz,zU,gz,Xz,zc,0m,zD,Q0,Yz,zb,0a,zp,zW,z7,0o,h0,1z,0p", "2,3660"],
  90.  ["5:8r,NI,gL,3z,EK,hy,L9,g2,Kh,Gw,Dg,ZB,Sg,LY,ig,sS,I8,U0,DI,cq,Bu,qJ,C4,jP", "143,1520"],
  91.  ["2:7s,z7,so,zw,X2,59,r1,0Q,70,q2,C6,J6,wz,at,2w,Vq,f9,st,sI,rf,wG,zg,f3,L2,4j", "4,2340"],
  92.  ["2:kw,Gz,zp,se,8e,2S,C7,1A,B9,5v,AM,sN,zH,m8,Cx,rG,4w,q2,W0,ta,AC,G5,y0,Vq,3i", "4,2080"],
  93.  ["3:Lr,pX,y7,2Y,qI,6w,t5,R6,e8,57,5f,R1,Up,9q,33,1Z,05,Eu,6S,AW,au,7S,zd,CA,R7", "7,2120"],
  94.  ["3:ut,0C,6p,5w,9M,uj,I6,sq,Yr,Tz,Bp,p7,Rt,JB,6O,Bw,T1,tY,pn,MA,7I,GC,BO,m0,ts", "12,2016"],
  95.  ["4:sE,Wy,Oo,uY,4t,os,B1,xq,4j,ex,s7,y7,54,ud,Cj,0L,S7,fx,11,cs,zc,tn,S6,Zq,2r", "56,2400"],
  96.  ["6:eZ,5V,xT,2x,W7,vy,yT,8R,XT,4c,yX,s9,3E,KZ,tp,Sj,Su,wp,4F,BV,aC,qw,cJ,Gl,aA", "192,1849"],
  97.  ["7:6Q,av,UZ,0c,IV,fo,Vv,mg,no,qM,06,zy,jW,R0,Qo,sK,wQ,1b,De,Iy,zI,cx,rn,ot,cN,45", "250,2303"],
  98.  ["4:0A,15,5k,Bi,mz,0f,vr,EZ,4z,vj,6p,vP,8X,16,x7,S3,2z,zJ,wI,wY,Wv,ky,9K,8u,Eo,4s,y0", "48,2700"],
  99.  ["8:zN,2J,ta,HL,Dg,up,Qn,W8,8K,k4,Is,uL,dT,tA,PN,UQ,DB,gA,OO,lv,4h,Rv,D6,23,Tg,4S,Zb", "418,1763"],
  100.  ["5:px,sp,cr,dB,fz,65,gq,zb,sN,42,o0,y3,iE,pv,sn,Al,RE,48,l0,7X,DE,xL,wC,qQ,w5,C3,P3,i1", "102,2397"],
  101.  ["9:Ic,Dk,Ef,6R,GK,NZ,76,L0,oQ,9f,S3,oL,lX,7v,8d,pX,dZ,z7,zx,fR,pe,w7,aj,U9,lO,kv,wL,s0", "396,2088"],
  102.  ["10:JJ,LR,Xe,kg,LU,lI,3w,ZV,Td,Mu,tA,g8,VC,I7,N8,zN,kY,Ux,3t,mg,4m,FO,Ug,vQ,qY,jl,Ne,Zq,GN", "416,1794"],
  103.  ["11:lQ,EN,vO,tn,qO,F3,9k,K2,UC,P0,XY,DB,QO,ps,hy,fl,Dt,ex,Vc,vF,Pf,Vk,uo,Xc,Sh,KE,9g,3H,l6", "658,1995"]
  104. ]
  105.  
  106. allcase.each_with_index do |(input,ans),cn|
  107.   a=solve(input)
  108.   puts "case #{cn}: "+(a==ans ? "yes":"no")+" ( #{a} )"
  109. end
Success #stdin #stdout 0.1s 10320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
case 0: yes ( 108,1920 )
case 1: yes ( - )
case 2: yes ( 1,3844 )
case 3: yes ( - )
case 4: yes ( 3844,3844 )
case 5: yes ( 3600,3721 )
case 6: yes ( 2,3660 )
case 7: yes ( 2,2046 )
case 8: yes ( 7,2170 )
case 9: yes ( 9,2852 )
case 10: yes ( 17,2604 )
case 11: yes ( 23,3100 )
case 12: yes ( 19,2480 )
case 13: yes ( 1938,3720 )
case 14: yes ( 3721,3721 )
case 15: yes ( - )
case 16: yes ( - )
case 17: yes ( 1748,3658 )
case 18: yes ( 1806,3186 )
case 19: yes ( 19,2520 )
case 20: yes ( 39,2562 )
case 21: yes ( - )
case 22: yes ( 741,3660 )
case 23: yes ( - )
case 24: yes ( 1178,2623 )
case 25: yes ( 1794,3472 )
case 26: yes ( 1,1785 )
case 27: yes ( 6,1824 )
case 28: yes ( 2,3660 )
case 29: yes ( 28,1224 )
case 30: yes ( 12,1989 )
case 31: yes ( 2,2928 )
case 32: yes ( 2,3660 )
case 33: yes ( 143,1520 )
case 34: yes ( 4,2340 )
case 35: yes ( 4,2080 )
case 36: yes ( 7,2120 )
case 37: yes ( 12,2016 )
case 38: yes ( 56,2400 )
case 39: yes ( 192,1849 )
case 40: yes ( 250,2303 )
case 41: yes ( 48,2700 )
case 42: yes ( 418,1763 )
case 43: yes ( 102,2397 )
case 44: yes ( 396,2088 )
case 45: yes ( 416,1794 )
case 46: yes ( 658,1995 )
https://ideone.com/I7MkBY
http://n...content-available-to-author-only...e.jp/hena/orde02pire/ offline-realtime-DOUKAKU E02(2016/03/05) **fixed**
language:
Ruby (ruby 2.5.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!