Codeforces315-div2C Prime or Palindromes?

http://codeforces.com/contest/569/problem/C

と定義する．比が与えられるので，を満たす最大のnを求めたい．

考察

まず，と，を求める．これをどこまで必要かを自分で判断しなければならない．とあるので，多くでもがの42倍になっているnまででよいと分かる．実際に値を試した所，n = 1500000で十分だとわかった．後は，後ろから見ていき，条件を満たす最大のnを答えた．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool prime[10000000];
void Eratosthenes(int n) {
    rep(i,n) prime[i] = true;
    prime[0] = false;
    prime[1] = false;

    REP(i,2,(int)sqrt(n)) {
        if(prime[i]) {
            for(int j=0;i*(j+2)<n;j++) {
                prime[i*(j+2)] = 0;
            }
        }
    }
}

bool check(string s) {
    rep(i,s.size()/2) {
        if(s[i] != s[s.size()-1-i]) return false;
    }

    return true;
}

int main() {
    double p,q;
    cin >> p >> q;

    int N = 1500000;

    Eratosthenes(N);
    vector<int> pi(N);
    int cnt = 0;

    rep(i,N+5) {
        if(prime[i]) {
            cnt++;
        }

        pi[i] = cnt;
    }


    vector<int> rub(N);
    cnt = 0;
    REP(i,1,N+5) {
        stringstream ss;
        ss << i;

        if(check(ss.str())) {
            cnt++;
        }

        rub[i] = cnt;
    }

    double A = p/q;
    int ans = 0;

    for(int i=N;i>=1;i--) {
        ll a = pi[i];
        ll b = rub[i];

        if(a <=  A * b) {
            cout << i << endl;
            break;
        }
        else {
            continue;
        }
    }

    return 0;
}
Aug 11th, 2015
codeforces, 全探索

Codeforces314-div2D One-Dimensional Battle Ships

http://codeforces.com/contest/567/problem/D
1次元のマス目がある．ここに長さaの船をk個置く．Bobの質問に対して，Aliceが嘘を言った時の番号を答える．

考察

どの質問までかを2分探索する．この探索に対してのvectorを作り，それぞれの区間に船が何個入るかを出す．区間を見たいので，端の0のn+1を追加する．この個数がkをこえるかこえないかで判断する．計算量は，探索でlog(n)，vectorのsortにn*log(n)かかるので，全体でO(n*log(n)2)．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n,k,a;
    cin >> n >> k >> a;

    int m;
    cin >> m;

    vector<int> v(m);
    rep(i,m) {
        cin >> v[i];
    }

    int l = 0,r = m+1;
    while(r - l > 1) {
        int mid = (l+r)/2;
        vector<int> t(v.begin(),v.begin()+mid);

        t.push_back(0);
        t.push_back(n+1);
        sort(t.begin(),t.end());

        int cnt = 0;
        rep(j,t.size()-1) {
            int d = t[j+1] - t[j];
            cnt += d/(a+1);
        }

        if(cnt >= k) {
            l = mid;
        }
        else {
            r = mid;
        }
    }

    if(l == m) cout << -1 << endl;
    else cout << l+1 << endl;

    return 0;
}
Aug 10th, 2015
2分探索, codeforces

Codeforces314-div2c Geometric Progression

http://codeforces.com/contest/567/problem/C
N個の数字と比kが与えられる．比がkである長さ3の部分数列の数を求めたい．

考察

3つの等比数列の真ん中の値に注目する．注目している数をxと置くと，d = x/k，x，u = x*kの数列の数を知ることが出来れば良い．自分の前にあるdの要素数，自分の後ろにあるuの要素数の乗算で，今見ているxを含む部分数列の数が分かる．これをN個に対して全てやった．Nは最大2*105のため，オーバーフローに注意する．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {

    ll n,k;
    cin >> n >> k;

    vector<ll> v(n);
    rep(i,n) {
        cin >> v[i];
    }

    map<ll,ll> mup;
    rep(i,n) {
        mup[v[i]]++;
    }

    map<ll,ll> mdown;

    ll ans = 0;

    rep(i,n) {
        mup[v[i]]--;
        if(v[i] % k == 0) {
            ll d = v[i]/k;
            ll u = v[i]*k;

            ans += mdown[d] * mup[u];
        }
        mdown[v[i]]++;
    }

    cout << ans << endl;

    return 0;
}
Aug 6th, 2015
codeforces

Codeforces313-div2 Gerald's Hexagon

六角形の辺の長さが時計回りの順番で与えられる．長さ1の正三角形がいくつあるかを求めよ．

考察

まずSample1を見る

これは正六角形であるため，この中に正三角形は6個．これのまず大きな三角形としてみる．追加した三角形を青で表すと

大きな三角形は高さをnとすると，n段目の高さは1 + (n-1)*2で計算できる．そして同じ計算方法で追加した3つの三角形を引く．これで計算できる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;

    int len = max(a+b+c,a+e+f);
    int ans = 0;
    int t = 1;

    rep(i,len) {
        ans += t;
        t += 2;
    }

    t = 1;
    rep(i,a) {
        ans -= t;
        t += 2;
    }

    t = 1;
    rep(i,c) {
        ans -= t;
        t += 2;
    }

    t = 1;
    rep(i,e) {
        ans -= t;
        t += 2;
    }

    cout << ans << endl;


    return 0;
}
Jul 25th, 2015
codeforces, 幾何

SRM663 ABBA

ある文字列Iに，2つの操作が出来る．
- 文字列の最後に"A"を足す
- 文字列を反転して，最後に"B"を足す

文字列Iが文字列Tになるかを判定せよ

考察

愚直にIに操作していくと，2T.size()-I.size()で無理．しかしTから減らしていくには，一意しかない．末尾が"A"ならば，一つ前の状態をpreTとすると，T = preT+“A"となる．まと同様に，末尾が"B"ならば，T = reverse(preT) + "B"である．これを繰り返し，Iと同じsizeになった時に，同じかどうかで判定できる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#line 5 "ABBA.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

class ABBA {
  public:
  string canObtain(string I, string T) {

        while(T != I && T.size() > I.size()) {
            if(T[T.size()-1] == 'A') {
                T = T.substr(0,T.size()-1);
            }else {
                T = T.substr(0,T.size()-1);
                reverse(T.begin(),T.end());
            }
        }

        if(T == I) return "Possible";
        return "Impossible";
  }
};

コードを短く，シンプルにかける．本番中は誤読をしていて死んでいた．このある状態を目的の状態にする問題で，逆からやると上手くいく系はすぐ解けるようになりたい．

Jul 24th, 2015
srm, topcoder, 文字列

TCO2015 in Tokyo

TCO2015 Round 2Cが東京で開催された．Tシャツが貰えて非常に嬉しい．

TCO

0完．本当に難しかった．ずっと紙に数字書いてたら終了した．

Hackathon

競技プログラミングの楽しさを伝える，というテーマが多かった(?)．

http://kenkoooo.com/
がめっちゃすごかった．個人的にこのページやAOJのSolved数などは非常にモチベが上がる．どんどん精進していきたい．

交流会

いろんな競技プログラマーをお話したい！，と思っていたら，Ezoeさんとお話出来てしまった．C++の処理系のお話が聞けて非常に嬉しかった．ご飯美味しかった．

Todo

  • easyが解けたらここにコード貼る
  • twitter関連のモノを載せると何でもかんでもFollowボタンが付いてしまって，鬱陶しい(消したい)
Jul 19th, 2015
topcoder

Yukicoder No.245 貫け！

http://yukicoder.me/problems/507

考察

端点のペアを列挙し，その直線とN個の線分が交差しているかを見る．直線ではなく，線分で交差判定をしていたためにWA．

以下の場合を考える．
今見ている．端点のペアは緑の点(a,b)だとする．ここで線分を作り交差判定をすると上の線分がcountされない．よって線分ではなく直線にしたい．

まず(a-b)のベクトルを作る．

aに足す

(b-a)のベクトルを作る．

bに足す

直線とみなせる．

今回のInputは-100~100までなので，このベクトルを500倍をとって直線とみなした．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define EPS 1e-8
#define equals(a,b) fabs((a) - (b)) < EPS

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct Point {
    double x, y;

    Point(double x=0, double y=0) : x(x), y(y) {}

    Point operator+(const Point &o) const { return Point(x+o.x, y+o.y); }

    Point operator-(const Point &o) const { return Point(x-o.x, y-o.y); }

    Point operator*(const double m) const { return Point(x*m, y*m); }

    Point operator/(const double d) const { return Point(x/d, y/d); }

    bool operator<(const Point &o) const { return x != o.x ? x < o.x : y < o.y; }

    bool operator==(const Point &o) const { return fabs(x-o.x) < EPS && fabs(y-o.y) < EPS; }

    double cross(const Point &o) const { return x * o.y - y * o.x; }

    double dot(const Point &o) const { return x * o.x + y * o.y; }

    double atan() const { return atan2(y, x); }

    double norm() const { return sqrt(dot(*this)); }

    double distance(const Point &o) const { return (o - (*this)).norm(); }

    double area(const Point &a,const Point &b) {
        Point p = a - (*this), p2 = b - (*this);
        return p.cross(p2);
    }

    double area_abs(const Point &a,const Point &b) const {
        Point p = a - (*this), p2 = b - (*this);
        return fabs(p.cross(p2)) / 2.0;
    }  

    //線分abが自身に含まれているのかどうか判断する
    int between(const Point &a,const Point &b) {
        if(area(a,b) != 0) return 0;

        if(a.x != b.x)  return ((a.x <= x) && (x <= b.x) || (a.x >= x) && (x >= b.x));
        else return ((a.y <= y) && (y <= b.y) || (a.y >= y) && (y >= b.y));
    }

    double distance_seg(const Point& a,const Point& b) {
        if((b-a).dot(*this-a) < EPS) {
            return (*this-a).norm();
        }
        if((a-b).dot(*this-b) < EPS) {
            return (*this-b).norm();
        }
        return abs((b-a).cross(*this-a)) / (b-a).norm();
    }

    bool hitPolygon(const Point& a,const Point& b,const Point& c) {
        double t = (b-a).cross(*this-b);
        double t2 = (c-b).cross(*this-c);
        double t3 = (a-c).cross(*this-a);   

        if((t > 0 && t2 > 0 && t3 > 0) || ( t < 0 && t2 < 0 && t3 < 0)) {
            return true;
        }

        return false;
    }
};

struct Seg {
    Point a,b;

    Seg (Point a, Point b) : a(a),b(b) {}

    bool isOrthogonal(Seg &s) { return equals((b - a).dot(s.b - s.a),0.0); }

    bool isParallel(Seg &s) { return equals((b-a).cross(s.b - s.a),0.0); }

    bool isIntersect(Seg &s) {
        if(s.a.between(a,b) || s.b.between(a,b) || a.between(s.a,s.b) || b.between(s.a,s.b)) {
            return true;
        }
        return ((a-b).cross(s.a-a) * (a-b).cross(s.b-a) < EPS) && ((s.b-s.a).cross(a-s.a)*(s.b-s.a).cross(b-s.a) < EPS);
    }

    bool distance(Seg &s) {
        if((*this).isIntersect(s)) return 0.0;

        return min(min(a.distance_seg(s.a,s.b),b.distance_seg(s.a,s.b)),min(s.a.distance_seg(a,b),s.b.distance_seg(a,b)));
    }

    Point getCrossPoint(Seg &s) {
        Point p = s.b - s.a;
        double d = abs(p.cross(a-s.a));
        double d2 = abs(p.cross(b-s.a));

        double t = d / (d+d2);
        return a + (b-a)*t;
    }

    bool operator<(const Seg &o) const {
        return a == o.a ? a < o.a : b < o.b;
    }

    void print() {
        cout << "(" << a.x << "," << a.y << ") (" << b.x << "," << b.y << ")" << endl;
    }
};

int main() {
    int n;
    cin >> n;

    vector<Seg> segs;
    vector<Point> v;

    rep(i,n) {
        double a,b,c,d;
        cin >> a >> b >> c >> d;

        Point p1(a,b);
        Point p2(c,d);

        v.push_back(p1);
        v.push_back(p2);

        segs.push_back(Seg(p1,p2));
    }

    int ans = 0;
    rep(i,v.size()) {
        rep(j,v.size()) {
            if(i == j) continue;

            Point a = (v[i] - v[j]) * 500;
            Point b = (v[j] - v[i]) * 500;

            Seg seg(v[i]+a,v[j]+b);

            int cnt = 0;
            rep(k,segs.size()) {
                if(seg.isIntersect(segs[k])) {
                    cnt++;
                }
            }

            ans = max(ans,cnt);
        }
    }

    cout << ans << endl;

    return 0;
}
Jul 18th, 2015
yukicoder, 幾何

SRM502 TheLotteryBothDivs

000000000~999999999の109の中で宝くじが当たる確率を求める．また下の桁が一致していれば当たりとなる．

考察

まず同じ数が与えられる可能性もあるので，setに投げて重複を消してから，下の桁が一致している数を消す．桁数が小さいほうが含まれるものが多いので，桁数が大きい方を消す． 後は0.1桁数のsumが答えとなる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <queue>
#include <set>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

class TheLotteryBothDivs {
  public:
  double find(vector <string> goodSuffixes) {
        set<string> st;
        rep(i,goodSuffixes.size()) {
            st.insert(goodSuffixes[i]);
        }

        vector<string> v;
        set<string>::iterator ite;
        for(ite = st.begin();ite != st.end(); ite++) {
            v.push_back(*ite);
        }

        vector<string> res;
        rep(i,v.size()) {
            bool flag = false;
            rep(j,v.size()) {
                if(v[i].size() > v[j].size()) {
                    bool ch = true;
                    rep(k,v[j].size()) {
                        if(v[i][v[i].size()-1-k] == v[j][v[j].size()-1-k]) continue;
                        ch = false;
                    }

                    if(ch) flag = true;
                }
            }
            if(!flag) res.push_back(v[i]);
        }

        double ans = 0;
        rep(i,res.size()) {
            double t = 1.0;

            rep(j,res[i].size()) {
                t *= 0.1;
            }

            ans += t;
        }
        return ans;
  }
};
Jul 17th, 2015
srm, topcoder

SRM501 FoxPlayingGame

scoreAをnA回足す，scoreBをnB回掛ける．この操作による最大値を求める．また

として与えられる．

考察

掛ける場合は最初の0の状態に掛けることができるので，回数を調整できるが，足す場合はそのようなことができない．よって，まずscoreAをnA回足す．また，この値が+か-かによって場合分けをする

  • +の場合かつscoreBが1以上の場合は，全て掛ける．
  • +の場合かつscoreBが-1以下の場合は，(scoreB)2は正なので偶数回掛けるのが最大
  • +の場合かつscoreBがそれ以外の場合は，減少するため，最初の0に掛けて消す
  • -の場合かつscoreBが1以上の場合は，負の値が増加してしまうので掛けない
  • -の場合かつscoreBが-1以下の場合は，奇数回掛けることによって値を正にすることができる
  • -の場合かつscoreBが0より大きく1以下の場合は，負の値を小さくすることができるので全部掛ける
  • -の場合かつscoreBが-1以上0より小さい場合は，一度だけ掛けて値を正することが最大

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

class FoxPlayingGame {
  public:
  double theMax(int nA, int nB, int paramA, int paramB) {
        double A = paramA / 1000.0;
        double B = paramB / 1000.0;

        double res = nA * A;
        if(res > 0) {
            if(B <= -1) {
                nB -= nB%2;
                rep(i,nB) {
                    res *= B;
                }
            }else if(B >= 1) {
                rep(i,nB) {
                    res *= B;
                }
            }
        }else {
            if(0 <= B && B < 1.0) {
                rep(i,nB) {
                    res *= B;
                }
            }
            else if(-1.0 < B && B < 0) {
                if(nB != 0) res *= B;
            }
            else if(B <= -1) {
                if(nB%2 == 0) nB--;
                rep(i,nB) {
                    res *= B;
                }
            }
        }

        return res;

  }
};

SystemTestに落ちまくり．特にscoreAが負，scoreBが負の時に，一度だけscoreBを掛ければよかったが，ここでnBが0の時の処理を加えればいいことに全く気づけなかった．

Jul 16th, 2015
srm, topcoder

Codeforces312-div2C Amr and Chemistry

http://codeforces.com/contest/558/problem/C
N個のデータが与えられる．それぞれの値には*2，/2することが出来る．全ての要素を揃えるための最小手数を求めよ

考察

この操作による状態数はそんなに多くない(log(n)の何倍か(?))．各値を動かした時にカウントして最後にカウントがn個となっている最小値を答える．動かすのは幅で見て，コストを足していった．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int d[100005];
bool used[100005];
int cnt[100005];

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    rep(i,n) cin >> v[i];

    rep(i,100005) d[i] = INF;
    memset(cnt,0,sizeof(cnt));

    rep(i,n) {
        memset(used,0,sizeof(used));
        used[v[i]] = true;
        if(d[v[i]] == INF) d[v[i]] = 0;
        cnt[v[i]]++;

        queue<pair<int,int> > que;
        que.push(mp(v[i],0));

        while(que.size()) {
            pair<int,int> p = que.front();
            que.pop();

            int f = p.first;
            int cost = p.second;

            int t = f/2;
            int t2 = f*2;

            if(0 < t && t < 100005 && !used[t]) {
                used[t] = true;
                cnt[t]++;
                if(d[t] == INF) d[t] = cost+1;
                else d[t] += cost+1;
                que.push(make_pair(t,cost+1));
            }

            if(0 < t2 && t2 < 100005 && !used[t2]) {
                used[t2] = true;
                cnt[t2]++;
                if(d[t2] == INF) d[t2] = cost+1;
                else d[t2] += cost+1;
                que.push(make_pair(t2,cost+1));
            }
        }

    }

    int ans = INF;
    rep(i,100005) {
        if(cnt[i] == n) ans = min(ans,d[i]);
    }

    cout << ans << endl;

    return 0;
}

コンテスト中，最後のほうでこの解法を思いついた．t，t2やその範囲でバグらせてしまい，時間内に提出できなかった．非常に悔しい(実力が足りない)．

Jul 15th, 2015
codeforces