본문 바로가기
Computer Science

Photo

by OKOK 2019. 3. 15.

실행 시간

10 초

메모리

Heap, Global, Stack 등을 모두 합쳐서 최대 256 MB 까지 사용 가능

(단, Stack 은 최대 1 MB 까지 사용 가능)

제출 횟수 제한

10 회


[ 주의 사항 ]


1. 응시자는 User Code 안의 recog() 함수를 구현해야 한다.


2. User Code 내 어떠한 헤더 파일도 추가할 수 없다.

   ( 단, malloc.h 사용 가능 )


3. Input 파일은 사용되지 않는다.


4. Main 은 수정할 수 없으며, 실제 채점 시에도 그대로 사용된다.

   단, seed 값과 dummy1 ~ 3 변수의 크기는 변경된다.


5. 본 검정은 C++ 언어만 지원한다.



▶ Main 을 분석하여 recog() 함수를 구현하라!

     RESULT 값이 클 수록 높은 점수를 부여한다.

 
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
177
#include <stdio.h>
 
static const char alpha[10][8][8] = {
    { // 0
        { 0, 0, 0, 0, 8, 8, 8, 8 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 }
    },
    { // 1
        { 0, 0, 0, 0, 8, 8, 8, 8 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 }
    },
    { // 2
        { 0, 0, 0, 0, 8, 8, 8, 8 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 8, 8, 8 }
    },
    { // 3
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 0, 0, 0 },
        { 0, 0, 0, 0, 8, 8, 8, 8 }
    },
    { // 4
        { 8, 8, 8, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 }
    },
    { // 5
        { 8, 8, 8, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 }
    },
    { // 6
        { 8, 8, 8, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 8, 8, 8, 8, 0, 0, 0, 0 }
    },
    { // 7
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 0, 8, 0, 0, 0, 0 },
        { 8, 8, 8, 8, 0, 0, 0, 0 }
    },
    { // 8
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 8, 8, 8, 8, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 }
    },
    { // 9
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 8, 8, 8, 8, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 8, 0, 0, 8, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0 }
    }
};
 
 
static int dummy1[12];
 
static char photo[16][64];
 
static int dummy2[34];
 
static int seed;
 
static int dummy3[56];
 
static void bitblt(int bx, int by, int n)
{
    for (int y = 0; y < 8; y++)
        for (int x = 0; x < 8; x++)
            photo[by + y][bx + x] = alpha[n][y][x];
}
 
static int pseudo_rand(void)
{
    seed = seed * 214013 + 2531011;
    return (seed >> 16) & 0x7FFF;
}
 
extern int recog(char photo[16][64]);
 
static void shot(int n)
{
    for (int y = 0; y < 16; y++)
        for (int x = 0; x < 64; x++)
            photo[y][x] = 0;
 
    int cursor = 0;
    int pos = 1000;
 
    for (int c = 0; c < 4; c++)
    {
        cursor += pseudo_rand() % 9;
 
        int x = cursor;
        int y = pseudo_rand() % 9;
 
        bitblt(x, y, (n / pos) % 10);
 
        cursor += 8;
        pos /= 10;
    }
 
    for (int y = 0; y < 16; y++)
        for (int x = 0; x < 64; x++)
            if (pseudo_rand() % 10 == 0)
                photo[y][x] = (photo[y][x] == 0) ? 8 : 0;
}
 
 
int main(void)
{
    seed = 3;  // the seed will be changed
 
    printf("---------------\n");
    int RESULT = 0;
    for (int c = 0; c < 2000; c++)
    {
        int number = pseudo_rand() % 10000;
        shot(number);
 
        if (recog(photo) == number)
            RESULT++;
    }
    printf("RESULT : %d\n", RESULT);
    return 0;
}
cs

 
1
2
3
4
int recog(char photo[16][64])
{
    return 0;
}
cs

 

 
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
177
178
179
static const char alpha[10][8][8] = {  
    {  // 0  
        { 0, 0, 0, 0, 8, 8, 8, 8 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 }  
    },  
    {  // 1  
        { 0, 0, 0, 0, 8, 8, 8, 8 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 }  
    },  
    {  // 2  
        { 0, 0, 0, 0, 8, 8, 8, 8 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 8, 8, 8 }  
    },  
    {  // 3  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 0, 0, 0 },  
        { 0, 0, 0, 0, 8, 8, 8, 8 }  
    },  
    {  // 4  
        { 8, 8, 8, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 }  
    },  
    {  // 5  
        { 8, 8, 8, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 }  
    },  
    {  // 6  
        { 8, 8, 8, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 8, 8, 8, 8, 0, 0, 0, 0 }  
    },  
    {  // 7  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 0, 0, 0, 8, 0, 0, 0, 0 },  
        { 8, 8, 8, 8, 0, 0, 0, 0 }  
    },  
    {  // 8  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 8, 8, 8, 8, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 }  
    },  
    {  // 9  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 8, 8, 8, 8, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 8, 0, 0, 8, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 },  
        { 0, 0, 0, 0, 0, 0, 0, 0 }  
    }  
};  
  
char (*myphoto)[64];  
  
int mem[64], rmem[64];  
int dp[5][65], np[5][65];  
  
  
  
  
  
int diff(const char number[8][8], int sx, int sy) {  
    int ret = 0;  
  
    for (register int x = 0; x < 8; ++x)  
        for (register int y = 0; y < 8; ++y)  
            if (number[y][x])  
                ret += !myphoto[sy + y][sx + x] ? -1 : 1;  
  
    return ret;  
}  
  
const int notdefined = 0x7fff;  
  
int dfs(int n, int x) {  
    if (dp[n][x] != notdefined)  
        return dp[n][x];  
    int &ret = dp[n][x];  
    int &nex = np[n][x];  
  
    if (n == 4)  
        return ret = 0;  
  
    ret = -1025;  
    for (int i = 0; i <= 8; ++i) {  
        int can = dfs(n + 1, x + i + 8) + mem[x + i];  
        if (can > ret) {  
            ret = can;  
            nex = x + i;  
        }  
    }  
  
    return ret;  
}  
  
int getnumber() {  
    int ret = 0, x = 0;  
  
    for (int i = 0; i < 4; ++i) {  
        ret = ret * 10 + rmem[np[i][x]];  
        x = np[i][x] + 8;  
    }  
  
    return ret;  
}  
  
int recog(char photo[16][64]) {  
    myphoto = photo;  
  
    for (int x = 56; x >= 0; --x) {  
        mem[x] = -1025;  
        for (int n = 9; n >= 0; --n)  
            for (int y = 8; y >= 0; --y) {  
                int can = diff(alpha[n], x, y);  
                if (can > mem[x])  
                    mem[x] = can, rmem[x] = n;  
            }  
    }  
  
    for (register int n = 4; n >= 0; --n)  
        for (register int x = 56; x >= 0; --x)  
            dp[n][x] = notdefined;  
  
    dfs(0, 0);  
  
    return getnumber();  
}  
 
cs

 


저작자표시

'Computer Science' 카테고리의 다른 글

Table Calculator  (0) 2019.03.15
블록 조립  (0) 2019.03.15
이미지 복원하기2  (0) 2019.03.15
루빅스 큐브  (0) 2019.03.15
expert 제목 및 팁  (0) 2019.03.13

관련글

댓글

티스토리툴바