スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Unknown Language Round #1

2011/02/22 1:00~3:30 (JST)
Codeforces Unknown Language Round #1 の参加記録。

コンテストの要旨とかはここから。
ようするに、みんなが知らないマイナー言語でコンテストしませんか? みたいな。
使える言語は開始 5 分前まで秘密。

第 1 回の今回は Tcl だった。
Tcl は Perl と Ruby と Python の次くらいに有名なスクリプト言語。(主観
私は以前に Tcl をちょっとだけ触ったことがあったので、やや有利。

Tags : プログラミング Codeforces

結果

A. AC
B. AC
C. AC
D. AC
E. AC
F. AC
G. AC
H. -
I. -
Standing : 19/681

問題

問題セットの原文はここを参照。

A. Factorial
n (≦10) に対して n ! を求めよ。

B. Expression
a+b または a-b という数式が与えられるので、計算結果を答えよ。

C. Table
m 行 n 列の表に次の例の順番で数を埋める。
(m=2, n=4 の例)
1 2 3 4
5 6 7 8

この表を 1 5 2 6 3 7 4 8 の順で読むとき、k 番目の数は何かを答える。

D. Presents
3 つの整数 a b c を大きいものから順に番号付けせよ。

E. Prime Segment
与えられる n (≦10000) について、n 以下の最大の素数と n 以上の最小の素数を求める。

F. Domain
与えられる文字列が domain かどうかを判定せよ。

domain の定義
・ 文字列はアルファベット小文字, 数字, ドットのみからなる
・ ドットは文字列の先頭に現れない
・ ドットは文字列の末尾に現れない
・ ドットで区切られた最後のパートは長さ 2 以上 3 以下である

G. Path Canonization
UNIX 形式のファイルパスが与えられる。
パスを . や .. を含まない形式に変換せよ。
変換過程でルートディレクトリより上にアクセスしてしまうときは -1 と答えよ。

H. Table Bowling
名前と得点の組が n (≦100) 個与えられる。
得点の高い順に順位付けせよ。同点の人に対しては、Sample test にある形式で出力すること。

I. Sort the Table
サイズ m × n の表と、各列の名前、ソーティングの規則が与えられる。
規則にしたがって表をソートせよ。
規則から順序が特定できない場合は、入力されたときの順序を保つこと。

解答

いつも使ってる C/C++ から HTML に変換するフリーソフトが Tcl に対応していないので、見にくいけど色づけはなし。
競技中に書いたコードはやっつけ感ありありだったので、多少修正して掲載している。

A.
scan [gets stdin] "%d" n
set ans 1
for {set i $n} {$i>1} {incr i -1} {set ans [expr $ans * $i]}
puts $ans


B.
puts [expr [gets stdin]]


C.
scan [gets stdin] "%d%d%d" m n k

set row [expr $k % $m]; if {$row==0} {set row $m}
set col [expr ($k + $m - 1) / $m]

puts [expr ($row - 1) * $n + $col]


D.
scan [gets stdin] "%d%d%d" a b c

if {$a>=$b && $a>=$c && $b>=$c} {puts "1 2 3"} \
elseif {$a>=$b && $a>=$c && $c>=$b} {puts "1 3 2"} \
elseif {$b>=$a && $b>=$c && $a>=$c} {puts "2 1 3"} \
elseif {$c>=$a && $c>=$b && $a>=$b} {puts "2 3 1"} \
elseif {$b>=$a && $b>=$c && $c>=$a} {puts "3 1 2"} \
else {puts "3 2 1"}

naive に。

E.
set prime {}
for {set i 2} {$i<10008} {incr i} {
set b 1
foreach p $prime {
if {[expr $p * $p]>$i} break
if {[expr $i % $p]==0} {set b 0; break}
}
if {$b==1} {lappend prime $i}
}

scan [gets stdin] "%d" n

foreach p $prime {if {$n<=$p} {set r $p; break}}
set prime [lsort -integer -decreasing $prime]
foreach p $prime {if {$n>=$p} {set l $p; break}}

puts "$l $r"

あらかじめ、試し割りで 10000 くらいまでの素数を作っておいた。

F.
if [regexp {^([0-9a-z]+\.)*[0-9a-z]{2,3}$} [gets stdin]] {puts YES} else {puts NO}

Viva 正規表現

G.
set ans {}
foreach tok [split [gets stdin] /] {
if {$tok eq {.}} {
# nop
} elseif {$tok eq {..}} {
if {$ans=={}} {puts -1; return}
set ans [lreplace $ans end end]
} else {
lappend ans $tok
}
}

set ans [join $ans /]; if {$ans eq {}} {set ans /}
puts $ans

シミュレーション

H. (時間外)
scan [gets stdin] "%d" n

for {set pt 0} {$pt<=1000} {incr pt} {set arr($pt) [list]}

for {set i 0} {$i<$n} {incr i} {
scan [gets stdin] "%s%d" name pt
lappend arr($pt) $name
}

set rank 1
for {set pt 1000} {$pt>=0} {incr pt -1} {
set len [llength $arr($pt)]
if $len==0 {
continue
} elseif $len==1 {
puts "$rank $arr($pt)"
incr rank
} else {
set arr($pt) [lsort $arr($pt)]
for {set i 0} {$i<$len} {incr i} {
puts "$rank-[expr $rank+$len-1] [lindex $arr($pt) $i]"
}
set rank [expr $rank+$len]
}
}


I. (時間外)
# input column names
set keys [gets stdin]
for {set i 0} {$i<[llength $keys]} {incr i} {set key([lindex $keys $i]) $i}

# input sorting rules
set rule [split [gets stdin] ,]
set rulenum [llength $rule]
for {set i 1} {$i<$rulenum} {incr i} { # trim leading whitespace
lset rule $i [string trimleft [lindex $rule $i]]
}

# input table data
while {1} {
set s [gets stdin]; if {$s eq {}} break
lappend tbl $s
}

# sorting
for {set k [expr $rulenum-1]} {$k>=0} {incr k -1} {
set kthrule [lindex $rule $k]
set rowid $key([lindex $kthrule 0])
if {[lindex $kthrule 1] eq {ASC}} {set ord increasing} else {set ord decreasing}
set tbl [lsort -index $rowid -$ord $tbl]
}

foreach row $tbl {puts $row}

優先度の低いルールから順に、ルールの個数回だけソートする。
lsort は安定ソートだからこれで OK.
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。