Add others/other/digit.c

2 files changed, 112 insertions, 0 deletions

diff --git a/others/other/README.md b/others/other/README.md
index a61f45a..cb1a9da 100644
--- a/others/other/README.md
+++ b/others/other/README.md
@@ -716,3 +716,51 @@ Số *m* tìm được.
 | MAXNUM.INP | MAXNUM.OUT |
 | :--------: | :--------: |
 |    7 3     |     2      |
+
+## Chữ số
+
+Cho xâu M lập thành từ tập H = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
+và không bắt đầu bằng ký tự 0; xâu S giá trị ban đầu là xâu M.
+
+Người ta thực hiện L lần biến đổi theo các bước sau:
+
+* Đếm số lần xuất hiện các ký tự i thuộc tập H, đặt là K<sub>i</sub>.
+* Nếu K<sub>i</sub> > 0 người ta viết liên tiếp xâu biểu diễn K<sub>i</sub>
+  trong cơ số 16 và ký tự i, thu được giá trị mới của M.
+* Viết tiếp M vào cuối xâu S.
+
+### Yêu cầu
+
+Cho xâu M, số lần biến đổi L và X là một ký tự từ tập H. Hãy đếm số lần xuất
+hiện X trong S thu được sau L lần biến đổi.
+
+### Dữ liệu
+
+* Dòng thứ nhất chứa xâu M;
+* Dòng thứ hai chứa số tự nhiên L;
+* Dòng thứ ba chứa kí tự X.
+
+### Kết quả
+
+Một số nguyên là số lần xuất hiện của X trong S sau L lần biến đổi.
+
+### Giới hạn
+
+* M có độ dài không vượt quá 127 kí tự;
+* L ≤ 10<sup>7</sup>.
+
+### Ví dụ
+
+|   DIGIT.INP    | DIGIT.OUT |
+| -------------- | :-------: |
+| 150A<br>3<br>2 |     1     |
+
+#### Giải thích
+
+| Lần biến đổi |    M     |              S               |
+| :----------: | -------- | ---------------------------- |
+|       0      | 150A     | 150A                         |
+|       1      | 1011151A | 150A1011151A                 |
+|       2      | 1051151A | 150A1011151A1051151A         |
+|       3      | 1041251A | 150A1011151A1051151A1041251A |
+
diff --git a/others/other/digit.c b/others/other/digit.c
new file mode 100644
index 0000000..d59241a
--- /dev/null
+++ b/others/other/digit.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+const char DIGITS[] = "0123456789ABCDEF";
+
+int cmp(const void *x, const void *y)
+{
+	return *(char *) x - *(char *) y;
+}
+
+char idx(char *c)
+{
+	return (char *) bsearch(c, DIGITS, 16, sizeof(char), cmp) - DIGITS;
+}
+
+int main()
+{
+	FILE *f = fopen("DIGIT.INP", "r");
+	char i, x[1], m[128];
+	long l, j;
+	unsigned long long *em, *k, *tmp, s[16];
+
+	em = calloc(16, sizeof(unsigned long long));
+	k = calloc(16, sizeof(unsigned long long));
+	fscanf(f, "%s\n%ld\n%c", m, &l, x);
+	fclose(f);
+
+	for (i = 0; i < strlen(m); em[idx(m + i++)]++);
+	memcpy(s, em, sizeof(unsigned long long) << 4);
+
+	for (j = 1; j < l; j++) {
+		for (i = 0; i < 16; i++)
+			if (em[i]) {
+				k[i]++;
+				do {
+					k[em[i] & 15]++;
+					em[i] >>= 4;
+				} while (em[i]);
+			}
+		tmp = k;
+		k = em;
+		em = tmp;
+		for (i = 0; i < 16; i++)
+			s[i] += em[i];
+		puts("");
+	}
+
+	if (l)
+		for (i = 0; i < 16; i++)
+			if (em[i]) {
+				s[i]++;
+				do {
+					s[em[i] & 15]++;
+					em[i] >>= 4;
+				} while (em[i]);
+			}
+
+	f = fopen("DIGIT.OUT", "w");
+	fprintf(f, "%Ld\n", s[idx(x)]);
+	fclose(f);
+
+	return 0;
+}