結果
問題 | No.325 マンハッタン距離2 |
ユーザー | Leonardone |
提出日時 | 2015-12-18 09:20:35 |
言語 | Ruby (3.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,997 bytes |
コンパイル時間 | 45 ms |
コンパイル使用メモリ | 7,808 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-09-16 08:30:32 |
合計ジャッジ時間 | 3,362 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 90 ms
12,288 KB |
testcase_01 | AC | 96 ms
12,160 KB |
testcase_02 | AC | 93 ms
12,160 KB |
testcase_03 | AC | 87 ms
12,160 KB |
testcase_04 | AC | 89 ms
12,032 KB |
testcase_05 | AC | 88 ms
12,032 KB |
testcase_06 | AC | 88 ms
12,160 KB |
testcase_07 | AC | 89 ms
12,160 KB |
testcase_08 | AC | 88 ms
12,288 KB |
testcase_09 | AC | 89 ms
12,032 KB |
testcase_10 | AC | 89 ms
12,160 KB |
testcase_11 | AC | 90 ms
12,288 KB |
testcase_12 | AC | 89 ms
12,032 KB |
testcase_13 | AC | 90 ms
12,032 KB |
testcase_14 | AC | 90 ms
12,160 KB |
testcase_15 | AC | 88 ms
12,160 KB |
testcase_16 | AC | 89 ms
12,160 KB |
testcase_17 | AC | 90 ms
12,160 KB |
testcase_18 | WA | - |
testcase_19 | AC | 88 ms
12,288 KB |
testcase_20 | AC | 89 ms
12,160 KB |
testcase_21 | AC | 89 ms
12,160 KB |
testcase_22 | WA | - |
testcase_23 | AC | 89 ms
12,160 KB |
testcase_24 | AC | 89 ms
12,288 KB |
testcase_25 | AC | 87 ms
12,160 KB |
testcase_26 | AC | 90 ms
12,032 KB |
コンパイルメッセージ
Syntax OK
ソースコード
#! ruby # yukicoder My Practice # author: Leonardone @ NEETSDKASU def gs() gets.chomp end def gi() gets.to_i end def gss() gets.chomp.split end def gis() gss.map(&:to_i) end def nmapf(n,f) n.times.map{ __send__ f } end def arr2d(h,w,v=0) h.times.map{[v] * w} end def ngs(n) nmapf n,:gs end def ngi(n) nmapf n,:gi end def ngss(n) nmapf n,:gss end def ngis(n) nmapf n,:gis end def for2p(hr,wr,&pr) hr.each{|i|wr.each{|j| yield(i,j)}} end def nsum(n) n * (n + 1) / 2 end TEST_RUN = false =begin 1) D範囲に完全内包 1.1: 軸に接しない 3 1 10 9 100 1.2: 軸に接する 3 0 10 8 100 1.3: 軸をまたぐ 3 -1 10 7 100 1.4: 原点を含む -3 -4 10 8 100 2) D範囲を完全内包 -10 -12 15 14 9 3) 一部だけD範囲と重なる 3.1: 三角範囲Dに入る 3.1.1: 軸に接しない 2 3 12 11 10 3.1.2: 片軸にだけ接する 0 3 12 11 10 3.1.3: 両軸に接する 0 0 12 11 10 3.2: 台形範囲Dに入る 3.2.1: 軸に接しない 4 2 15 6 13 3.2.2: 片軸に接する 4 0 15 6 13 3.2.3: 両軸に接する 0 0 15 6 13 3.3: 五角形範囲Dに入る 3.3.1: 軸に接しない 5 2 16 12 24 3.3.2: 片軸に接する 5 0 16 12 24 3.3.3: 両軸に接する 0 0 16 12 24 4) Dの範囲の完全外側 10 13 19 18 11 [1] テストケース -3 -12 8 -1 11 [2] テストケース -13 -8 10 8 12 [3] テストケース 4 7 10 11 11 [4] テストケース 5 3 11 20 30 =end def bruteforce(x1, y1, x2, y2, d) count = 0 (y1..y2).each do |y| (x1..x2).each do |x| count += 1 if x.abs + y.abs <= d end end count end def bunkatsu(z1_,z2_) z1, z2 = [z1_, z2_].minmax zmin, zmax = [z1.abs, z2.abs].minmax case when zmin == 0 [[0, 0], [1, zmax]] when z2 < 0 [[zmin, zmax]] when z1 > 0 [[zmin, zmax]] when z1 < 0 && 0 < z2 [[0, 0], [1, zmin], [1, zmax]] else sleep 10 [] end end # 4) Dの範囲の完全外側 def perfectly_outside?((x1, x2), (y1, y2), d) d < x1 + y1 end # 点 def dot?((x1, x2), (y1, y2), d) x1 == x2 && y1 == y2 && x1 == y1 end def dot_count((x1, x2), (y1, y2), d) count = 0 <= d - (x1 + y1) ? 1 : 0 puts "dot [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 直線 def line?((x1, x2), (y1, y2), d) x1 == x2 || y1 == y2 end def line_count((x1, x2), (y1, y2), d) count = 0 if d < x2 + y2 count = d - (x1 + y1) + 1 else count = (x2 + y2) - (x1 + y1) + 1 end puts "line [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 三角形 def triangle?((x1, x2), (y1, y2), d) return 0 if d <= [x1 + y2, x2 + y1].min end def triangle_count((x1, x2), (y1, y2), d) count = nsum(d - (x1 + y1) + 1) puts "triangle [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end # 台形 def trapezoid?((x1, x2), (y1, y2), d) d <= [x1 + y2, x2 + y1].max end def trapezoid_count((x1, x2), (y1, y2), d) short_end, long_end = [x1 + y2, x2 + y1].minmax short_len = short_end - (x1 + y1) + 1 long_len = [d, long_end].min - (x1 + y1) + 1 count = (short_len * (long_len - short_len)) + nsum(short_len) puts "trapezoid [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN puts "end: [%d, %d], len: [%d, %d]" % [short_end, long_end, short_len, long_len] if TEST_RUN count end # 五角形 def pentagon?((x1, x2), (y1, y2), d) [x1 + y2, x2 + y1].max < D end def pentagon_count((x1, x2), (y1, y2), d) count = (x2 - x1 + 1) * (y2 - y1 + 1) - nsum((x2 + y2) - d) puts "pentagon [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN count end ################################################ X1,Y1,X2,Y2,D = gis puts "X1=%d, Y1=%d, X2=%d, Y2=%d, D=%d" % [X1, Y1, X2, Y2, D] if TEST_RUN bf = bruteforce(X1, Y1, X2, Y2, D) if TEST_RUN puts "bruteforce %d" % [bf] if TEST_RUN # 1) D範囲に完全内包 if [X1.abs, X2.abs].max + [Y1.abs, Y2.abs].max <= D puts "perfectly inside of D range" if TEST_RUN count = (X2 - X1).abs.succ * (Y2 - Y1).abs.succ puts count exit end # 2) D範囲を完全内包 if [X1..X2, Y1..Y2].all?{|r| r.include?(-D) && r.include?(D)} puts "perfectly inside of Square" if TEST_RUN count = nsum(D) * 4 + 1 puts count exit end xs = bunkatsu(X1, X2) ys = bunkatsu(Y1, Y2) puts "xs = %s" % [xs.to_s] if TEST_RUN puts "ys = %s" % [ys.to_s] if TEST_RUN count = 0 for2p(ys,xs) {|yt,xt| args = [xt, yt, D] next if perfectly_outside?(*args) case when dot?(*args) count += dot_count(*args) when line?(*args) count += line_count(*args) when triangle?(*args) count += triangle_count(*args) when trapezoid?(*args) count += trapezoid_count(*args) when pentagon?(*args) count += pentagon_count(*args) end } puts count puts (bf == count ? "" : "in") + "corrct!" if TEST_RUN