diff options
| -rw-r--r-- | 2.2/lamps.c | 139 | ||||
| -rw-r--r-- | 2.2/runround.c | 72 | ||||
| -rw-r--r-- | 2.2/subset.c | 50 |
3 files changed, 261 insertions, 0 deletions
diff --git a/2.2/lamps.c b/2.2/lamps.c new file mode 100644 index 0000000..03422ad --- /dev/null +++ b/2.2/lamps.c @@ -0,0 +1,139 @@ +/* +ID: mytbk921 +LANG: C +TASK: lamps +*/ + +#include <stdio.h> +#include <string.h> + +static int popcount(unsigned int i) +{ + int s = 0; + while (i) { + if (i&1) + s++; + i >>= 1; + } + return s; +} + +int n,c,on[101],off[101],final[101]; +int result[16][100]; +int nres; +int sorted[16]; + +int comp(int i, int j) +{ + int k; + for (k=1; k<=n; k++) { + if (result[i][k] < result[j][k]) + return -1; + if (result[i][k] > result[j][k]) + return 1; + } + return 0; +} + +int main() +{ + FILE *fin = fopen("lamps.in", "r"); + FILE *fout = fopen("lamps.out", "w"); + + int l; + int i,j,k,pc,tmp; + + fscanf(fin, "%d%d", &n, &c); + memset(on, 0, sizeof(on)); + memset(off, 0, sizeof(off)); + while (1) { + fscanf(fin, "%d", &l); + if (l!=-1) + on[l] = 1; + else + break; + } + while (1) { + fscanf(fin, "%d", &l); + if (l!=-1) { + if (on[l]) + goto Impossible; + off[l] = 1; + } else { + break; + } + } + fclose(fin); + + nres = 0; + for (i=0; i<16; i++) { + pc = popcount(i); + if (pc>c || pc%2 != c%2) + continue; + if (i&1) { + for (j=1; j<=n; j++) + final[j] = 0; + } else { + for (j=1; j<=n; j++) + final[j] = 1; + } + if (i&2) { + for (j=1; j<=n; j+=2) + final[j] = 1-final[j]; + } + if (i&4) { + for (j=2; j<=n; j+=2) + final[j] = 1-final[j]; + } + if (i&8) { + for (j=1; j<=n; j+=3) + final[j] = 1-final[j]; + } + for (j=1; j<=n; j++) { + if ((on[j]&&!final[j]) || (off[j]&&final[j])) + break; + } + if (j>n) { + for (j=1; j<=n; j++) + result[nres][j] = final[j]; + nres++; + } + } + + if (nres==0) + goto Impossible; + + for (i=0; i<nres; i++) + sorted[i] = i; + + /* do an insertion sort */ + for (i=1; i<nres; i++) { + for (j=0; j<i; j++) { + tmp = comp(sorted[j], sorted[i]); + if (tmp==0) + sorted[i] = sorted[j]; + if (tmp>=0) { + tmp = sorted[i]; + for (k=i; k>j; k--) + sorted[k] = sorted[k-1]; + sorted[j] = tmp; + break; + } + } + } + + for (i=0; i<nres; i++) { + if (i==0 || sorted[i]!=sorted[i-1]) { + for (j=1; j<=n; j++) + fprintf(fout, "%d", result[sorted[i]][j]); + + fprintf(fout, "\n"); + } + } + fclose(fout); + return 0; +Impossible: + fprintf(fout, "IMPOSSIBLE\n"); + fclose(fout); + return 0; +} diff --git a/2.2/runround.c b/2.2/runround.c new file mode 100644 index 0000000..498b579 --- /dev/null +++ b/2.2/runround.c @@ -0,0 +1,72 @@ +/* +ID: mytbk921 +LANG: C +TASK: runround +*/ + +#include <stdio.h> +#include <stdlib.h> + +int runround(unsigned int x) +{ + unsigned int msd, lsd, last, t; + int next[10]; + int map[10]; + int i; + + for (i=0; i<10; i++) map[i] = 0; + + lsd = x % 10; + if (lsd == 0) return 0; + last = lsd; + map[lsd] = 1; + x /= 10; + while (x>=10) { + t = x % 10; + if (map[t] || t==0) return 0; + map[t] = 1; + next[t] = last; + last = t; + x /= 10; + } + msd = x; + map[msd] = 1; + next[msd] = last; + next[lsd] = msd; + + last = msd; + do { + if (map[last]) + map[last] = 0; + else + return 0; + t = last; + for (i=0; i<t; i++) + last = next[last]; + } while (last != msd); + for (i=0; i<10; i++) { + if (map[i]) + return 0; + } + return 1; +} + +int main() +{ + FILE *fin = fopen("runround.in", "r"); + FILE *fout = fopen("runround.out", "w"); + + unsigned int m; + fscanf(fin, "%u", &m); + fclose(fin); + + while (1) { + m++; + if (runround(m)) { + fprintf(fout, "%u\n", m); + fclose(fout); + return 0; + } + } + return 0; +} diff --git a/2.2/subset.c b/2.2/subset.c new file mode 100644 index 0000000..9f05b2c --- /dev/null +++ b/2.2/subset.c @@ -0,0 +1,50 @@ +/* +ID: mytbk921 +LANG: C +TASK: subset +*/ + +#include <stdio.h> +#include <stdlib.h> + +int main() +{ + FILE *fin = fopen("subset.in", "r"); + FILE *fout = fopen("subset.out", "w"); + + long long dp[40][500]; + int N, sum; + int i, j; + fscanf(fin, "%d", &N); + fclose(fin); + + sum = N*(N+1)/2; + if (sum%2) { + fprintf(fout, "0\n"); + fclose(fout); + return 0; + } + sum /= 2; + + /* dp[x][y]: number of sets that sum of set is y + * with all numbers in the set <=x + * + * dp[k][0] = 1 + * dp[0][k] = 0 for k>0 + */ + for (i=0; i<=N; i++) + dp[i][0] = 1; + for (i=1; i<=sum; i++) + dp[0][i] = 0; + for (i=1; i<=N; i++) { + for (j=1; j<=sum; j++) { + if (j<i) + dp[i][j] = dp[j][j]; + else + dp[i][j] = dp[i-1][j] + dp[i-1][j-i]; + } + } + fprintf(fout, "%lld\n", dp[N][sum]/2); + fclose(fout); + return 0; +} |