結果

問題 No.94 圏外です。(EASY)
ユーザー LEDLED
提出日時 2019-01-28 16:15:42
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,155 bytes
コンパイル時間 85 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 43,264 KB
最終ジャッジ日時 2024-04-15 06:44:49
合計ジャッジ時間 7,078 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 101 ms
43,264 KB
testcase_01 AC 88 ms
12,544 KB
testcase_02 AC 89 ms
12,416 KB
testcase_03 AC 88 ms
12,160 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def max(d,n)
	m = d.flatten.compact.sort{|a,b|b<=>a}[n]
	p1 = nil
	p2 = nil
	d.find.with_index{|r,i|
		p1 = i
		r.find.with_index{|c,j|
			p2 = j
			c == m
		}
	}
	[p1,p2,m]
end
def dfs(d,s,g,di)
	check = Array.new(N,false)
	stack = []
	stack.push(s)
	goal = false
	while stack.size > 0
		nx = stack.pop()
		check[nx] = true
		if nx == g
			goal = true
			break
		end
		cand = d[nx].map.with_index{|e,i|nx==i ? nil : e}
		cand.map.with_index{|e,i| stack.push(i) if !e.nil? && e <= 10.0 && !check[i]}
	end
	return goal
#	cand = d[s].map.with_index{|e,i|f==i ? nil : e}
#	cand.map.with_index{|e,i| !e.nil? && e <= 10.0 && !c[i] ? dfs(d,i,g,e,s,c) : false}.include?(true)
end
N=gets.to_i
pos=[]
N.times{pos.push(gets.split(/\s/).map(&:to_i))}
d=Array.new(pos.size).map{Array.new(pos.size)}
N.times{|i| N.times{|k| d[i][k]=((pos[i][0]-pos[k][0])**2+(pos[i][1]-pos[k][1])**2)**0.5 if i != k}}
case(d.size)
when 0 then
	puts 1
when 1 then
	puts 2
when 2 then
	puts d[0][1] <= 10.0 ? d[0][1]+2 : 2
else
	f = false
	(0..d.flatten.compact.size/2).each{|num|
		s,g,d0 = max(d,num)
		if dfs(d,s,g,d0)
			f = true
			puts d0+2
			break
		end
	}
	puts 1 unless f
end
0