Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 JOI Poster

Category: JOI Tag: implementation

JOI Poster

問題概要


1辺2^nの正方形について, それを4等分して
左上がJ, 右上がO, 左下がIと割り当てて, 右下がまたさらに4等分されてこれを繰り返す.
4等分出来ない最後の1マスはJにする.
このときk行目の状態を答えよ

解法


縦の区間[l,r)をその中心mで区切っていって, 下側にkがあるならk行目の文字列の区間[l,m)はI,
上側にあるなら[l,m)はJ, [m,r)はIになる.
下側に合った場合は更に[m,r)を半分に区切っていけば良い

コード


(Poster.cpp) download
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
#include <bits/stdc++.h>
using namespace std;

int n, k;
string ans;

void rec(int l, int r)
{
        if(r-l==1) {
                ans.push_back('J');
                return;
        }
        int m = (l+r)/2;
        if(k >= m) {
                for (int i = l; i < m; i++) ans.push_back('I');
                rec(m,r);
        }
        else {
                for (int i = l; i < m; i++) ans.push_back('J');
                for (int i = m; i < r; i++) ans.push_back('O');
                return;
        }
}

string solve()
{
        ans = "";
        rec(0,1<<n);
        return ans;
}

void input()
{
        cin >> n >> k;
        k--;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments