Chengrui's Blog

0%

发表于 分类于 ， ， Disqus：

Code

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
/*
 ID: wcr19961
 PROG: skidesign
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int a[maxn];

int main() {
  freopen("skidesign.in", "r", stdin);
  freopen("skidesign.out", "w", stdout);
  int n, ans = inf, l = 100, r = 0;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    l = min(l, x), r = max(r, x);
    ++a[x];
  }
  for (int i = l; i <= r; ++i) {
    int res = 0;
    for (int j = l; j <= r; ++j) {
      if (a[j] > 0) {
        if (j < i) {
          res += a[j] * (j - i) * (j - i);
        }
        if (j > i + 17) {
          res += a[j] * (j - i - 17) * (j - i - 17);
        }
      }
    }
    ans = min(ans, res);
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
 ID: wcr19961
 PROG: wormhole
 LANG: C++11
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
const int maxn = 15;
int ans, p[maxn];
int r[maxn], st[maxn];
struct Node {
  int x, y;
  bool operator < (const Node& rhs) const {
    return y < rhs.y || (y == rhs.y && x < rhs.x);
  }
} a[maxn];


bool dfs2(int u, int fa, int n) {
  if (r[p[u]] == -1) {
    return false;
  }
  st[u] = true;
  if (st[r[p[u]]] || dfs2(r[p[u]], u, n)) {
    return true;
  }
  st[u] = false;
  return false;
}

bool check(int n) {
  memset(st, 0, sizeof st);
  for (int i = 0; i < n; ++i) {
    if (r[i] == p[i]) {
      return true;
    }
    if (dfs2(i, -2, n)) {
      return true;
    }
  }
  return false;
}

void dfs(int d, int n) {
  if (d == n) {
    if (check(n)) {
      ++ans;
    }
    return;
  }
  if (p[d] == -1) {
    for (int i = d + 1; i < n; ++i) {
      if (p[i] == -1) {
        p[i] = d;
        p[d] = i;
        dfs(d + 1, n);
        p[d] = p[i] = -1;
      }
    }
  } else {
    dfs(d + 1, n);
  }
}

int main() {
  freopen("wormhole.in", "r", stdin);
  freopen("wormhole.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    p[i] = r[i] = -1;
  }
  sort(a, a + n);
  for (int i = 1; i < n; ++i) {
    if (a[i - 1].y == a[i].y) {
      r[i - 1] = i;
    }
  }
  dfs(0, n);
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

Notice that \(n\) may be smaller than 5.

Code

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
/*
ID: wcr19961
PROG: combo
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
const int maxn = 5;
int a[maxn], b[maxn];
set<int> s[maxn];

int main() {
  freopen("combo.in", "r", stdin);
  freopen("combo.out", "w", stdout);
  int n, ans = 1;
  scanf("%d", &n);
  scanf("%d%d%d", &a[0], &a[1], &a[2]);
  scanf("%d%d%d", &b[0], &b[1], &b[2]);
  for (int i = 0; i < 3; ++i) {
    if (a[i] < b[i]) {
      swap(a[i], b[i]);
    }
    ans *= max(0, 5 - min(a[i] - b[i], b[i] - a[i] + n));
  }
  printf("%d\n", n > 5 ? 250 - ans : n * n * n);
 return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: crypt1
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 12;
bool vis[maxn];
int a[maxn], b, ans;

int check(int x) {
  int cnt = 0;
  while (x) {
    if (!vis[x % 10]) {
      return -1;
    }
    x /= 10;
    ++cnt;
  }
  return cnt;
}

void dfs(int d, int n) {
  if (d == n) {
    if (check(b * (a[3] * 10 + a[4])) == 4) {
      ++ans;
    }
    return;
  }
  if (d == 3) {
    b = a[0] * 100 + a[1] * 10 + a[2];
  }
  for (int i = 1; i < 10; ++i) {
    if (vis[i]) {
      if (d >= 3 && check(b * i) != 3) {
        continue;
      }
      a[d] = i;
      dfs(d + 1, n);
    }
  }
}

int main() {
  freopen("crypt1.in", "r", stdin);
  freopen("crypt1.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    vis[x] = true;
  }
  dfs(0, 5);
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: barn1
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 210;
int a[maxn], tmp[maxn];

int main() {
  freopen("barn1.in", "r", stdin);
  freopen("barn1.out", "w", stdout);
  int m, s, c;
  scanf("%d%d%d", &m, &s, &c);
  for (int i = 0; i < c; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + c);
  int cnt = 0;
  for (int i = 1; i < c; ++i) {
    tmp[cnt++] = a[i] - a[i - 1] - 1;
  }
  sort(tmp, tmp + cnt);
  int ans = a[c - 1] - a[0] + 1;
  --m;
  while (m && cnt) {
    ans -= tmp[--cnt];
    --m;
  }
  printf("%d\n", ans);
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: milk
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 5010;
int tmp[maxn];
struct Node {
  int num, v;
  bool operator < (const Node& rhs) const {
    return v < rhs.v;
  }
} a[maxn];

int main() {
  freopen("milk.in", "r", stdin);
  freopen("milk.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a[i].v, &a[i].num);
  }
  sort(a, a + m);
  LL sum = 0;
  for (int i = 0; i < m; ++i) {
    if (n >= 0) {
      if (n > a[i].num) {
        sum += a[i].v * a[i].num;
        n -= a[i].num;
      } else {
        sum += a[i].v * n;
        n = 0;
      }
    } else {
      break;
    }
  }
  printf("%lld\n", sum);
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: dualpal
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 30;
int tmp[maxn];

bool check(int n, int k) {
  int len = 0;
  while (n) {
    tmp[len++] = n % k;
    n /= k;
  }
  int len2 = len >> 1;
  for (int i = 0; i < len2; ++i) {
    if (tmp[i] != tmp[len - 1 - i]) {
      return false;
    }
  }
  return true;
}

int main() {
  freopen("dualpal.in", "r", stdin);
  freopen("dualpal.out", "w", stdout);
  int n, s;
  scanf("%d%d", &n, &s);
  for (int i = s + 1; n != 0; ++i) {
    int cnt = 0;
    for (int j = 2; j <= 10; ++j) {
      if (check(i, j)) {
        ++cnt;
      }
    }
    if (cnt >= 2) {
      printf("%d\n", i);
      --n;
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

Notice the upper bound of maxn.

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
/*
ID: wcr19961
PROG: palsquare
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 30;
int k[maxn], kk[maxn];

int main() {
  freopen("palsquare.in", "r", stdin);
  freopen("palsquare.out", "w", stdout);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= 300; ++i) {
    int sum = i * i, len = 0;
    while (sum) {
      k[len++] = sum % n;
      sum /= n;
    }
    bool ok = true;
    for (int j = 0; j < len; ++j) {
      if (k[j] != k[len - 1 - j]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      int tmp = i, tmplen = 0;
      while (tmp) {
        kk[tmplen++] = tmp % n;
        tmp /= n;
      }
      for (int j = tmplen - 1; j >= 0; --j) {
        putchar(kk[j] < 10 ? kk[j] + '0' : kk[j] + 'A' - 10);
      }
      putchar(' ');
      for (int j = 0; j < len; ++j) {
        putchar(k[j] < 10 ? k[j] + '0' : k[j] + 'A' - 10);
      }
      puts("");
    }
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: namenum
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

typedef long long LL;
const int maxn = 30;
char s[maxn], tmp[maxn];
vector<string> S, ans;

void dfs(int d, int n) {
  if (d == n) {
    tmp[d] = 0;
    if (binary_search(S.begin(), S.end(), string(tmp))) {
      ans.push_back(tmp);
    }
    return;
  }
  for (int i = 0; i < 3; ++i) {
    tmp[d] = 'A' + (s[d] - '2') * 3 + i;
    if (tmp[d] >= 'Q') {
      ++tmp[d];
    }
    dfs(d + 1, n);
  }
}

int main() {
  freopen("namenum.in", "r", stdin);
  freopen("namenum.out", "w", stdout);
  FILE* Dict = fopen("dict.txt", "r");
  while (~fscanf(Dict, "%s", s)) {
    S.push_back(s);
  }
  sort(S.begin(), S.end());
  scanf("%s", s);
  int n = int(strlen(s));
  bool ok = true;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0' || s[i] == '1') {
      ok = false;
      break;
    }
  }
  if (ok) {
   dfs(0, n); 
  }
  if (ok && ans.size()) {
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); ++i) {
      puts(ans[i].c_str());
    }
  } else {
    puts("NONE");
  }
  return 0;
}

发表于 分类于 ， ， Disqus：

Code

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
/*
ID: wcr19961
PROG: transform
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

typedef long long LL;
const int maxn = 12;
char a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];

void rotate(int n, char a[][maxn], char b[][maxn]) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      b[i][j] = a[n - 1 - j][i];
    }
  }
}

bool check(int n, char a[][maxn], char b[][maxn]) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (a[i][j] != b[i][j]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  freopen("transform.in","r",stdin);
  freopen("transform.out","w",stdout);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%s", a[i]);
  }
  for (int i = 0; i < n; ++i) {
    scanf("%s", b[i]);
  }
  rotate(n, a, c);
  if (check(n, b, c)) {
    puts("1");
    return 0;
  }
  rotate(n, c, d);
  if (check(n, b, d)) {
    puts("2");
    return 0;
  }
  rotate(n, d, c);
  if (check(n, b, c)) {
    puts("3");
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      c[i][j] = a[i][n - 1 - j];
    }
  }
  if (check(n, b, c)) {
    puts("4");
    return 0;
  }
  rotate(n, c, d);
  if (check(n, b, d)) {
    puts("5");
    return 0;
  }
  rotate(n, d, c);
  if (check(n, b, c)) {
    puts("5");
    return 0;
  }
  rotate(n, c, d);
  if (check(n, b, d)) {
    puts("5");
    return 0;
  }
  puts(check(n, a, b) ? "6" : "7");
  return 0;
}