토요일의 대회에 대비해 조금 연습해 보자. 첫 서너 시간 정도만..
이렇게 써놓고 5시간 다 돌았다. -_-; 결과는 20/1345. 당시 스탠딩 에 비춰 보면, 15등 성적. Single-person team 중에서는 1등 성적 (2006년의 페사마에게 이겼다 -_ -;). 이거 포스팅 하면서 L1 소스코드 L2 에 돌려보니 그냥 나오네 -_-;; 이거 냈었으면 탑 텐이구만. ㅋㅋㅋ
계속 성장하고 있다는 생각이 들어서 다행이다.
거의 다 파이썬으로 풀었는데 C++ 만큼은 아니지만 코딩이 자연스러워지고 있어서 좋다. 소스보기
A
so simple.
lang:py
#!/usr/bin/python
import sys
def read():
while True:
line = sys.stdin.readline().strip()
if line != "": break
return line
cases = int(read())
for cc in range(cases):
n = int(read())
sum = 0
for i in range(n):
sum += int(read())
print "YES" if sum % n == 0 else "NO"
B
/greedy 좀 늦게 푼 편이다.
lang:py
#!/usr/bin/python
import sys
from collections import defaultdict
def read():
while True:
line = sys.stdin.readline().strip()
if line != "": break
return line
cases = int(read())
for cc in range(cases):
n = int(read())
req = [0] * n
for i in range(n):
a, b = sys.stdin.readline().strip().split()
req[i] = int(b) - 1
req.sort()
ret = 0
for i in range(n):
ret += abs(req[i] - i)
print ret
C
Partial Sum 을 써서 푸는 것이 좋다. 'ㅅ'
lang:py
#!/usr/bin/python
import sys
from collections import defaultdict
def read():
while True:
line = sys.stdin.readline().strip()
if line != "": break
return line
cases = int(read())
for cc in range(cases):
n = int(read())
q = []
sum = 0
ret = 0
seq = map(int, sys.stdin.readline().split())
psum = [0] * n
psum[0] = seq[0]
for i in range(1,n):
psum[i] = psum[i-1] + seq[i]
cnt = defaultdict(lambda: 0)
cnt[0] += 1
for i in range(n):
ret += cnt[psum[i] - 47]
cnt[psum[i]] += 1
print ret
D1
D1 만 팩토리얼 직접 계산해서 풀었다. Stirling's Formula 이런거 어떻게 알고 쓰나여 ㅜㅜ
lang:py
#!/usr/bin/python
import sys
from collections import defaultdict
def read():
while True:
line = sys.stdin.readline().strip()
if line != "": break
return line
cases = int(read())
for cc in range(cases):
n, k, l = map(int, read().split())
f = 1
for i in range(2,n+1): f *= i
s = str(f)
print "%s %s" % (s[:k], s[-l:])
F1
F2 를 열심히 코딩했지만 구현 못하고 결국 지지. 아이디어는 그래도 할만했는데.
lang:cpp
struct point
{
double y, x;
point(double y = 0, double x = 0) : y(y), x(x) {}
double norm() const { return hypot(y, x); }
point operator + (const point& rhs) const { return point(y + rhs.y, x + rhs.x); }
point operator - (const point& rhs) const { return point(y - rhs.y, x - rhs.x); }
point operator * (double f) const { return point(y * f, x * f); }
bool operator < (const point& rhs) const
{
if(y != rhs.y) return y < rhs.y;
return x < rhs.x;
}
point rotate(double theta) const
{
double s = sin(theta), c = cos(theta);
return point(s * x + c * y, c * x - s * y);
}
};
const double PI = 2.0 * acos(0.0);
void grow(const string& gene, vector<point>& p)
{
point here;
p.clear();
p.push_back(here);
point unit(0, 1);
double theta = 0.5 * PI;
int i = 0;
while(i < gene.size())
{
switch(gene[i])
{
case 'l': theta += PI / 6; ++i; break;
case 'r': theta -= PI / 6; ++i; break;
case 'f': here = here + unit.rotate(theta); p.push_back(here); ++i; break;
case '@':
{
double ratio = atof(gene.c_str() + i + 2);
unit.x *= ratio;
while(gene[i] != '}') ++i;
++i;
break;
}
default:
++i;
break;
}
}
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
string w0;
map<char, string> rep;
int k, l;
cin >> k >> l >> w0;
for(int i = 0; i < l; ++i)
{
string inst;
cin >> inst;
rep[inst[0]] = inst.substr(2);
}
for(int i = 0; i < k; ++i)
{
string next;
for(int j = 0; j < w0.size(); ++j)
if(rep.count(w0[j]))
next += rep[w0[j]];
else
next += w0[j];
w0 = next;
if(w0.size() >= 1000000)
{
printf("stopped: k %d i %d length %d\n", k, i, w0.size());
break;
}
}
fprintf(stderr, "length %d\n", w0.size());
/*
vector<point> p;
grow(w0, p);
point center;
double length = 0;
for(int i = 0; i < p.size()-1; ++i)
{
double seg = (p[i] - p[i+1]).norm();
center = center + (p[i] + p[i+1]) * (seg * 0.5);
length += seg;
}
printf("%.9lf %.9lf\n", center.x / length, center.y / length);*/
}
}
G
백트래킹 짜서 돌려보니 규칙성이 너무 뻔했다. ㅠ.ㅠ 이런 걸 못 풀었다니.
J1
BFS 로 생각하고 풀면 쉽다. ~_~
lang:py
#!/usr/bin/python
actual = [x.strip() for x in open("actual").readlines()]
intended = [x.strip() for x in open("intended").readlines()]
def pre(a, b):
if len(a) > len(b):
a, b = b, a
return b[0:len(a)] == a
def cut(a, b):
m = min(len(a), len(b))
return a[m:], b[m:]
def solve(seed):
act, prg = actual[seed], intended[seed]
if not pre(act, prg): return False
act, prg = cut(act, prg)
q = []
q.append((act, prg))
seen = {}
seen[(act, prg)] = -1
while len(q) > 0:
act, prg = q[-1]
q = q[:-1]
print "[%s] [%s]" % (act, prg)
for next in range(334):
nact = act + actual[next]
nprg = prg + intended[next]
if not pre(nact, nprg): continue
nact, nprg = cut(nact, nprg)
if (nact, nprg) in seen: continue
seen[(nact, nprg)] = (next, act, prg)
q.append((nact, nprg))
if ("", "") in seen:
print "SOLVED"
moves = []
act, prg = "", ""
while seen[(act, prg)] != -1:
a,nact,nprg = seen[(act, prg)]
act = nact
prg = nprg
print a, "[%s]" % act, "[%s]" % prg
moves.append(a)
moves.append(seed)
return list(reversed(moves))
return False
for i in range(334):
res = solve(i)
if res:
print len(res)
print "\n".join(map(lambda x: str(x+1), res)) + "\n"
p = "".join([actual[x] for x in res])
q = "".join([intended[x] for x in res])
if p != q:
print "Oops"
break
K
소수를 만들 수 있는데 안 만들고 지나치는 일이 없다는 것을 알면, 가장 가까운 소수까지의 거리만 찾아서 일반적인 NIM game 으로 만들 수 있다. 시작할 때 이미 소수가 있는 것은 문제가 될 수 있음.
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
bool isPrime(long long u)
{
if(u == 2) return true;
if(u % 2 == 0) return false;
for(long long i = 3; i*i <= u; i += 2)
if(u % i == 0)
return false;
return true;
}
int primeGap(long long N)
{
assert(N >= 2);
long long M = N;
while(!isPrime(M)) --M;
return N - M;
}
int n, k;
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
cin >> n >> k;
VI nimber(1000);
for(int i = 1; i < 1000; ++i)
{
set<int> seen;
for(int j = 1; j <= k; ++j)
seen.insert(nimber[i-j]);
int k = 0;
while(seen.count(k)) ++k;
nimber[i] = k;
}
VI state;
vector<long long> original;
for(int i = 0; i < n; ++i)
{
long long num;
cin >> num;
assert(num >= 3);
original.push_back(num);
}
for(int i = 0; i < n; ++i)
{
state.push_back(primeGap(original[i]));
assert(state.back() < 1000);
}
fprintf(stderr, "max state %d\n", *max_element(all(state)));
int zeroes = count(all(state), 0);
if(zeroes > 1)
cout << "YES" << endl;
else if(zeroes == 1)
{
if(state.size() == 1)
{
state[0] = primeGap(original[0] - 1) + 1;
cout << (nimber[state[0]] ? "YES" : "NO") << endl;
}
else
cout << "YES" << endl;
}
else
{
int nim = 0;
for(int i = 0; i < state.size(); ++i)
nim ^= nimber[state[i]];
cout << (nim ? "YES": "NO") << endl;
}
}
}
L
LRU 알고리즘에서 캐시 사이즈 N 보다 N+1 이 비효율적인 케이스 찾기. 랜덤 시뮬레이션 rules! 1초안에 답을 찾아준다. --;
lang:cpp
int add(vector<int>& d, int size, int book)
{
if(find(all(d), book) != d.end()) return 0;
if(d.size() == size)
d.erase(d.begin());
d.push_back(book);
return 1;
}
int go(int size, VI& sce)
{
int ret = 0;
VI books;
for(int i = 0; i < sce.size(); ++i)
{
int book = sce[i];
if(count(all(books), book) > 0) continue;
++ret;
if(books.size() == size)
books.erase(books.begin());
books.push_back(book);
}
return ret;
}
int main()
{
int n = 10, m = 30;
int t = 0 ;
while(true)
{
++t;
if(t % 1000 == 0) printf("Simulation %d..\n", t);
int length = 100;
vector<int> scenario(length);
for(int i = 0; i < length; ++i)
scenario[i] = rand() % m;
vector<int> books[4];
VI costs(4);
for(int i = 0; i < length; ++i)
{
int book = scenario[i];
for(int j = 0; j < 4; ++j)
costs[j] += add(books[j], n+j, book);
if(costs[0] < costs[1] && costs[0] < costs[2] && costs[0] < costs[3])
{
printf("%d %d\n", n, i+1);
for(int j = 0; j <= i; ++j)
printf("%d ", scenario[j]);
printf("\n");
throw 1;
}
}
}
M
모르스 부호 디코더만..
lang:py
#!/usr/bin/python
lang="- .... .- - .-- .- ... - --- --- . .- ... -.-- - .-. -.-- .... .- .-. -.. --- -. .".split()
dict="""A .-
J .---
S ...
1 .----
B -...
K -.-
T -
2 ..---
C -.-.
L .-..
U ..-
3 ...--
D -..
M --
V ...-
4 ....-
E .
N -.
W .--
5 .....
F ..-.
O ---
X -..-
6 -....
G --.
P .--.
Y -.--
7 --...
H ....
Q --.-
Z --..
8 ---..
I ..
R .-.
0 -----
9 ----."""
d = {}
for line in dict.split("\n"):
a, b = line.split()
print b, a
d[b] = a
for w in lang: print d[w],
