IPSC 2010 후기

지난 현충일날 열렸던 IPSC 참가 기념으로 후기를 남긴다..

학교 후배들과 같이 팀으로 출전했는데.. 결과는 198 등으로 끝났다.. ㅎㅎ
좀 아쉬움이 남긴하지만 나름 만족스럽다..~

팀이름: IPSC Super Dummy Team
맴버: helloneo, HyoCheol, walsub
기록: 198 등 (링크)

구글 코드잼같은경우 개인전이라서 별로 재미가 없는데..
IPSC 는 팀플레이라서 색다른 재미가 있다..~

내년에는 100등안에 들도록 노력해야겠다..~

참고로 작년에는 참가 못했고 제작년에는
MAD COW GO AWAY :( 라는 팀이름으로 출전하여 159 등을 하기도 하였다.. (링크)


올해 풀었던 문제 솔루션이나 남겨놔야지..~~ (문제 링크)
--


A1, A2 (solved by helloneo)

문제 읽고나서 좀 황당했던 문제..;;;; 그냥 sorting 해놓고 첫번째 원소랑 두번째 원소를 바꿨다.. -_-;;

  1 #include <stdio.h>
  2 #include <string.h>
  3 int num[10000];
  4 int n;
  5 int comp(const void* x, const void* y)
  6 {
  7     int* a = (int*)x;
  8     int* b = (int*)y;
  9     return *a - *b;
 10 }
 11 int main()
 12 {
 13     int tc, cn;
 14     int i, j, k;
 15     scanf("%d", &tc);
 16     printf("%d\n\n", tc);
 17     for (cn = 1; cn <= tc; cn++) {
 18         scanf("%d", &n);
 19         printf("%d\n", n);
 20         for (i = 0; i < n; i++) {
 21             scanf("%d", &num[i]);
 22         }
 23         qsort(num, n, sizeof(int), comp);
 24         k = num[0];
 25         num[0] = num[1];
 26         num[1] = k;
 27         for (i = 0; i < n-1; i++) {
 28             printf("%d ", num[i]);
 29         }
 30         printf("%d\n", num[i]);
 31         printf("\n");
 32     }
 33     return 0;
 34 }

B1, B2 (solved by walsub)

나는 문제 해석에만 약간 기여했음.. -_-;;
대략 직선에 대한 교점 구하고 몇가지 경우를 나눠서 처리한거같은데.. 모르겠음

  1 #include <stdio.h>
  2 #include <math.h>
  3
  4 int main()
  5 {
  6     double P, Q, R, Ax, Ay, Bx, By;
  7     double ans, dis, dis1, dis2;
  8
  9     int t;
 10
 11     FILE *in = fopen("input.txt","rt");
 12     FILE *out = fopen("output.txt","wt");
 13
 14     fscanf(in,"%d",&t);
 15
 16     while( t -- ) {
 17         fscanf(in,"%lf %lf %lf %lf %lf %lf %lf", &Ax, &Ay, &Bx, &By, &P, &Q, &R);
 18         ans = fabs(Ax-Bx) + fabs(Ay-By);
 19
 20         for( int i=0; i<2; i++ ) {
 21
 22             double x1, y1;
 23             if( i == 0 ) { // x ????
 24                 x1 = Ax;
 25                 if( Q == 0.0 ) continue;
 26                 y1 = (R - P * Ax) / Q;
 27             }
 28             else { // y????
 29                 y1 = Ay;
 30                 if( P == 0.0 ) continue;
 31                 x1 = (R - Q * Ay) / P;
 32             }
 33             for( int j=0; j<2; j++ ) {
 34                 double x2, y2;
 35                 if( j == 0 ) { // x ????
 36                     x2 = Bx;
 37                     if( Q == 0.0 ) continue;
 38                     y2 = (R - P * Bx) / Q;
 39                 }
 40                 else { // y????
 41                     y2 = By;
 42                     if( P == 0.0 ) continue;
 43                     x2 = (R - Q * By) / P;
 44                 }
 45
 46                 dis = fabs( Ax - x1 ) + fabs( Ay - y1 ) + fabs( Bx - x2 ) + fabs( By - y2 ) +
 47                     sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
 48
 49                 if( ans > dis ) ans = dis;
 50             }
 51         }
 52
 53         fprintf(out,"%.12lf\n", ans);
 54     }
 55
 56     fclose(in);
 57     fclose(out);
 58     return 0;
 59 }

C1, C2 (solved by helloneo)

recursion 굿!!
그냥 나혼자 푸는 문제였으면 절대 안풀었을 문제.. 더 쉽게 푸는방법 없나..?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <map>
  6 #include <cctype>
  7 using namespace std;
  8 #define NUM 1
  9 #define LB 2
 10 #define RB 3
 11 #define PLUS 4
 12 #define MINUS 5
 13 #define MUL 6
 14 #define DIV 7
 15 #define END 8
 16 #define VAR 9
 17 #define ERR -1
 18
 19 typedef struct _d {
 20     char name[101];
 21     int val;
 22 } DATA;
 23 DATA data[1001];
 24
 25 char buf[1000];
 26 char list[1001][1001];
 27 char name[1001][101];
 28 int res[1001];
 29 char used[1001];
 30 char var[1001];
 31 int n;
 32 map<string, int> to_int;
 33 int len, idx, err, sym;
 34 int val;
 35
 36 int comp(const void* x, const void* y)
 37 {
 38     DATA* a = (DATA*)x;
 39     DATA* b = (DATA*)y;
 40     return strcmp(a->name, b->name);
 41 }
 42
 43
 44 int get_sym()
 45 {
 46     int temp;
 47     int i;
 48
 49     while (buf[idx] == ' ')
 50         idx++;
 51     if (idx == len)
 52         return END;
 53
 54     if (isdigit(buf[idx])) {
 55         val = 0;
 56         while (isdigit(buf[idx])) {
 57             val *= 10;
 58             val += buf[idx]-'0';
 59             idx++;
 60         }
 61         return NUM;
 62     }
 63     else if (isalpha(buf[idx])) {
 64         i = 0;
 65         while (isdigit(buf[idx]) || isalpha(buf[idx]) && idx < len) {
 66             var[i] = buf[idx];
 67             i++;
 68             idx++;
 69         }
 70         var[i] = 0;
 71         return VAR;
 72     }
 73     else if (buf[idx] == '+') {
 74         idx++;
 75         return PLUS;
 76     }
 77     else if (buf[idx] == '-') {
 78         idx++;
 79         return MINUS;
 80     }
 81     else if (buf[idx] == '*') {
 82         idx++;
 83         return MUL;
 84     }
 85     else if (buf[idx] == '/') {
 86         idx++;
 87         return DIV;
 88     }
 89     else if (buf[idx] == '(') {
 90         idx++;
 91         return LB;
 92     }
 93     else if (buf[idx] == ')') {
 94         idx++;
 95         return RB;
 96     }
 97     err = 1;
 98     return ERR;
 99 }
100 int expr();
101 int factor()
102 {
103     int result;
104     int k;
105     char save_buf[1000];
106     int save_len, save_idx, save_sym;
107
108     if (sym == VAR) {
109         k = to_int[var];
110         if (used[k]) {
111             sym = get_sym();
112             return res[k];
113         }
114         save_len = len;
115         save_idx = idx;
116         save_sym = sym;
117         strcpy(save_buf, buf);
118
119         used[k] = 1;
120         idx = 0;
121         strcpy(buf, list[k]);
122         len = strlen(list[k]);
123         sym = get_sym();
124         res[k] = expr();
125
126         len = save_len;
127         idx = save_idx;
128         sym = save_sym;
129         strcpy(buf, save_buf);
130
131         sym = get_sym();
132         return res[k];
133     }
134     else if (sym == NUM) {
135         result = val;
136         sym = get_sym();
137     }
138     else if (sym == LB) {
139         sym = get_sym();
140         result = expr();
141         if (sym != RB)
142             err = 1;
143         sym = get_sym();
144     }
145     else
146         err = 1;
147     return result;
148 }
149 int term()
150 {
151     int op;
152     int result;
153     result = factor();
154     op = sym;
155     while (sym == MUL || sym == DIV) {
156         op = sym;
157         sym = get_sym();
158         if (op == MUL) result *= factor();
159         else result /= factor();
160     }
161     return result;
162 }
163 int expr()
164 {
165     int op;
166     int result;
167     if (sym == PLUS || sym == MINUS) {
168         op = sym;
169         sym = get_sym();
170         result = term();
171         if (op == MINUS)
172             result = -result;
173     }
174     else
175         result = term();
176     while (sym == PLUS || sym == MINUS) {
177         op = sym;
178         sym = get_sym();
179         if (op == PLUS) result += term();
180         else result -= term();
181     }
182     return result;
183 }
184 int main()
185 {
186     int tc;
187     int result;
188     int i, j;
189     scanf("%d", &tc);
190     while (tc--) {
191         to_int.clear();
192         scanf("%d", &n);
193         gets(buf);
194         for (i = 1; i <= n; i++) {
195             gets(buf);
196             for (j = 0; ; j++) {
197                 if (buf[j] == ' ' || buf[j] == '=')
198                     break;
199             }
200             buf[j] = 0;
201             to_int[buf] = i;
202             strcpy(name[i], buf);
203
204             for (j = 0; ; j++) {
205                 if (buf[j] == '=')
206                     break;
207             }
208             strcpy(list[i], &buf[j+1]);
209         }
210         for (i = 1; i <= n; i++) {
211             res[i] = -10000;
212         }
213         memset(used, 0, sizeof(used));
214
215         for (i = 1; i <= n; i++) {
216             if (used[i] == 0) {
217                 used[i] = 1;
218                 len = strlen(list[i]);
219                 strcpy(buf, list[i]);
220                 idx = 0;
221                 sym = get_sym();
222                 res[i] = expr();
223             }
224         }
225         for (i = 1; i <= n; i++) {
226             strcpy(data[i].name, name[i]);
227             data[i].val = res[i];
228         }
229
230         qsort(data+1, n, sizeof(DATA), comp);
231         for (i = 1; i <= n; i++) {
232             printf("%s = %d\n", data[i].name, data[i].val);
233         }
234         if (tc)
235         printf("\n");
236     }
237     return 0;
238 }

F1 (solved by HyoCheol)

문제 뭔지 모름.. (코드도 없는 문제)


J1, J2 (solved by walsub)

문제 뭔지 모름.. 그냥 통밥으로 풀었다고 함.. 대단한데..
음.. 코드를 좀 보니.. 좀 당황스러운데..

  1 #include <stdio.h>
  2
  3 int main()
  4 {
  5     FILE *in = fopen("input.txt","rt");
  6     FILE *out = fopen("output.txt","wt");
  7
  8     int t;
  9
 10     fscanf(in,"%d",&t);
 11
 12     while( t -- ) {
 13         int n ;
 14         fscanf(in,"%d",&n);
 15         if( n % 2 == 0 ) {
 16             fprintf(out, "Impossible\n\n");
 17             continue;
 18         }
 19
 20         for( int i=2; i<=n; i++ ) fprintf(out, "%d ", i);
 21         fprintf(out,"%d\n", 1);
 22
 23         fprintf(out,"%d", n);
 24         for( int i=1; i<n; i++ ) fprintf(out," %d", i);
 25         fprintf(out,"\n\n");
 26     }
 27
 28     fclose(in);
 29     fclose(out);
 30
 31     return 0;
 32 }

L1 (solved by helloneo)

easy input 에 대해서는 중복조합을 이용하여 풀었다.. nHr = choose(n+r-1, r)
조합은 파스칼의 삼각형을 이용하여 구했다..

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define MAXN 2001
  4 int n, m, k, p;
  5 long long combi[MAXN][MAXN];
  6
  7 /* combi[n][r] = n C r */
  8 void get_combi()
  9 {
 10     int i, j;
 11     for (i = 0; i < MAXN; i++) {
 12         combi[i][i] = 1;
 13         combi[i][0] = 1;
 14     }
 15     for (i = 0; i < MAXN; i++) {
 16         for (j = 1; j < i; j++) {
 17             combi[i][j] = (combi[i-1][j-1] % p) + (combi[i-1][j] % p);
 18             combi[i][j] %= p;
 19         }
 20     }
 21 }
 22
 23 int main()
 24 {
 25     int tc;
 26     int i, j;
 27     int a, b;
 28     long long cnt;
 29
 30     scanf("%d", &tc);
 31     while (tc--) {
 32         scanf("%d%d%d%d", &n, &m, &k, &p);
 33         get_combi();
 34         cnt = 0;
 35         if (n == 0 && m == 0) {
 36             printf("0\n");
 37             continue;
 38         }
 39         for (a = 0; a <= k; a++) {
 40             if (((k-a) % 2) != 0) {
 41                 continue;
 42             }
 43             b = (k-a) / 2;
 44
 45             if (n == 0 && a != 0) {
 46                 continue;
 47             }
 48             if (m == 0 && b != 0) {
 49                 continue;
 50             }
 51
 52             if (a == 0) {
 53                 cnt += (combi[m+b-1][b]);
 54                 cnt %= p;
 55             }
 56             else if (b == 0) {
 57                 cnt += (combi[n+a-1][a]);
 58                 cnt %= p;
 59             }
 60             else {
 61                 cnt += (combi[n+a-1][a] * combi[m+b-1][b]);
 62                 cnt %= p;
 63             }
 64         }
 65         printf("%lld\n", cnt);
 66     }
 67     return 0;
 68 }

이거는 공식 에디토리얼:

booklet47.pdf