あしあと問題
締め切りが 2017/03/09 10:00 AM なので,その 1 分後に投稿されるように予約が
仕様
9x9のマップの中を標準入力の内容に応じて移動します。
移動するとあしあとが残ります。
どのようなあしあとが残ったか標準出力してください。
標準入力
・「^v<>」のどれかの文字を組み合わせた文字列が入力されます
・ ^ は上に移動です
・ v は下に移動です
・ < は左に移動です
・ > は右に移動です
例
>>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^
標準出力
・9文字x9行の文字列を出力してください
・1行目1文字目の位置をスタート地点とします
・スタート地点は必ず「あしあと」が残ります
・同じ場所を2回通った場合は「あしあと」が残ります
・移動した場所は「Y」(半角大文字のワイ)を出力してください。鳥の足跡をイメージしています。
・移動しなかった場所は「x」(半角小文字のエックス)を出力してください
例(標準入力の説明の入力が行われた場合の出力結果)
YYYYYYYYY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YYYYYYYYY
その他の仕様
・標準入力の末尾には改行があります
・標準出力の末尾に改行をつけてください
・移動回数は最大で48回です
・標準入力の仕様で説明した内容以外の入力は行われません(不正入力に対するチェックは不要)
・9x9からはみ出す位置への移動をするような入力は行われません(不正入力に対するチェックは不要)
=============
f = function(S) {
x = y = 1
m = matrix("x", 9, 9)
m[x, y] = "Y"
S = unlist(strsplit(S, ""))
for (s in S) {
if (s == ">") {
x = x+1
} else if (s == "<") # < は半角で
x = x-1
} else if (s == "v") {
y = y+1
} else if (s == "^") {
y = y-1
}
m[x, y] = "Y"
}
for (i in 1:9) {
cat(sprintf("%s\n", paste(m[,i], collapse="")))
}
}
# f(readLines(file("stdin", "r")))
f(">>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^")
f(">>vv>>vv>>vv>>vv")
f(">>>><vvv")
「プライム・ペア」問題
締め切りが 2017/03/09 10:00 AM なので,その 1 分後に投稿されるように予約
設問
自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。
(F(k) はオイラーのΦ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia))
例えば F(12)=4 です。1 から 12 のうち 12 と互いに素なのは 1, 5, 7, 11 の 4 つです。
標準入力から、自然数 n(1 ≦ n ≦ 105)が与えられます。
標準出力に F(n!) を 1000003 で割った余りを出力するプログラムを書いてください。
例えば n=10 のとき、F(10!)=F(3628800)=829440 です。
同様に、F(20!) を 1000003 で割った値は 961998 です。
===================================
F = function(n) {
mx = n # n 以下の素数リストを prime に作る
tbl = 1:mx
tbl[1] = 0
for (i in 2:floor(sqrt(mx))) {
if (tbl[i]) {
mx2 = mx %/% i
tbl[2:mx2*i] = 0
}
}
prime = tbl[tbl > 0]
# F(n!) = n! * Π(1-1/prime[i]) = 1*2*3*…*n × (prime[1]-1)/prime[1] × (prime[2-1)/prime[2] …
# F(20!) = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 * (1-1/2)*(1-1/3)*(1-1/5)*(1-1/7)*(1-1/11)*(1-1/13)*(1-1/17)*(1-1/19)
# = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 * 1/2 * 2/3 * 4/5 * 6/7 * 10/11 * 12/13 * 16/17 * 18/19
# = 1*4*6*8*9*10*12*14*15*16*18*20 * 1*2*4*6*10*12*16*18
# = 416084687585280000
# 416084687585280000 %% 1000003 = 961998
# i = 1 ~ n までの積。ただし,i が素数の場合は「i-1」
x = 1:n
x[prime] = x[prime] - 1
ans = 1
for (a in x) { # 要素の掛算(ただし,毎回 1000003 の剰余を結果とする)
ans = (ans*a) %% 1000003
}
cat(ans)
}
#F(scan(file("stdin", "r")))
F(10) # 829440
F(20) # 961998
F(30) # 845477
F(100) # 145380
F(431) # 945906
F(2017) # 272985
F(81645) # 603326
F(99100) # 799614