#include <stdio.h> #include <stdlib.h> #define SIZE 100000 typedef struct { int nr; int d; int a; int diff; } potwor; static int cmp(const void *a, const void *b) { const potwor *pa = (const potwor*) a; const potwor *pb = (const potwor*) b; if (pa->diff > 0) { if (pb->diff > 0) { return pa->d - pb->d; } else { return -pa->diff; } } if (pa->diff == 0) { if (pb->diff >= 0) { return pb->diff; } else { return -1; } } if (pb->diff >= 0) { return pb->diff+1; } if (pa->d != pb->d) { return pb->d - pa->d; } return pb->diff - pa->diff; } void print_t(potwor *t, int n) { int i; printf("%d", t[0].nr); for(i = 1; i < n; ++i) { printf(" %d", t[i].nr); } printf("\n"); } int check(potwor *t, int n, int life) { int i; for(i = 0; i < n; ++i) { life -= t[i].d; if (life <= 0) { break; } life += t[i].a; } return life; } int main() { int n, z, i; potwor t[SIZE]; scanf("%d %d\n", &n, &z); for(i = 0; i < n; ++i) { scanf("%d %d\n", &t[i].d, &t[i].a); t[i].diff = t[i].a - t[i].d; t[i].nr = i+1; } qsort( &t, n, sizeof(potwor), cmp); if (check(t, n, z) > 0) { printf("TAK\n"); print_t(t, n); } else { printf("NIE\n"); } return 0; }
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 | #include <stdio.h> #include <stdlib.h> #define SIZE 100000 typedef struct { int nr; int d; int a; int diff; } potwor; static int cmp(const void *a, const void *b) { const potwor *pa = (const potwor*) a; const potwor *pb = (const potwor*) b; if (pa->diff > 0) { if (pb->diff > 0) { return pa->d - pb->d; } else { return -pa->diff; } } if (pa->diff == 0) { if (pb->diff >= 0) { return pb->diff; } else { return -1; } } if (pb->diff >= 0) { return pb->diff+1; } if (pa->d != pb->d) { return pb->d - pa->d; } return pb->diff - pa->diff; } void print_t(potwor *t, int n) { int i; printf("%d", t[0].nr); for(i = 1; i < n; ++i) { printf(" %d", t[i].nr); } printf("\n"); } int check(potwor *t, int n, int life) { int i; for(i = 0; i < n; ++i) { life -= t[i].d; if (life <= 0) { break; } life += t[i].a; } return life; } int main() { int n, z, i; potwor t[SIZE]; scanf("%d %d\n", &n, &z); for(i = 0; i < n; ++i) { scanf("%d %d\n", &t[i].d, &t[i].a); t[i].diff = t[i].a - t[i].d; t[i].nr = i+1; } qsort( &t, n, sizeof(potwor), cmp); if (check(t, n, z) > 0) { printf("TAK\n"); print_t(t, n); } else { printf("NIE\n"); } return 0; } |