diff options
35 files changed, 1196 insertions, 0 deletions
diff --git a/usth/MATH2.3/1/README.pdf b/usth/MATH2.3/1/README.pdf new file mode 100644 index 0000000..2458e44 --- /dev/null +++ b/usth/MATH2.3/1/README.pdf Binary files differdiff --git a/usth/MATH2.3/1/README.tex b/usth/MATH2.3/1/README.tex new file mode 100644 index 0000000..73916bf --- /dev/null +++ b/usth/MATH2.3/1/README.tex @@ -0,0 +1,50 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[english,vietnamese]{babel} +\usepackage{amsmath} +\usepackage{hyperref} +\usepackage{lmodern} +\usepackage{mathtools} + +\title{Discrete Mathematics: Algorithm} +\author{Nguyễn Gia Phong---BI9-184} +\date{\dateenglish\today} + +\begin{document} +\maketitle +\section{Problem 3} +The program \verb|coin.c| takes an integer $n$ from \verb|stdin| and print +the least coin exchange of $n$ cents to \verb|stdout|. + +\section{Problem 4} +The program \verb|schedule.c| take an integer $n$ and $n$ integral +time intervals from \verb|stdin| and print to \verb|stdout| the chosen talks +intervals in chronological order. + +\section{Problem 5} +\verb|search.c| contains two searching implementations, linear search +(\verb|lsearch|) and binary search (\verb|bsearch|). + +It is trivial that \verb|lsearch| has \verb|nmemb| or $\Theta(n)$ +time complexity. + +For \verb|binary_search| (which is wrapped by \verb|bsearch|), +the time complexity (in term of number of comparisons) is can be seen as +\begin{align*} + T(n) &= T\left(\frac{n}{2}\right) + \Theta(1)\\ + &= T\left(\frac{n}{2}\right) + \Theta\left(n^{\log_2 1}\right) +\end{align*} +since \verb|mid = (lo + high) / 2)|. +\pagebreak + +By the master theorem\footnote{Let $a \ge 1$ and $b > 1$ be constants, +and let $T(n)$ be defined on the nonnegative integers by the recurrence +\[T(n) = aT\left(\frac{n}{b}\right) + \Theta\left(n^{\log_b a}\right)\] +where $n/b$ is interpreted as either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$, +then \[T(n) = \Theta\left(n^{\log_b a}\lg n\right)\]}, +\[T(n) = \Theta\left(n^{\log_2 1}\lg n\right) = \Theta(\lg n)\] + +\section{Copying} +This report along with the source files are licensed under a +\href{https://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons +Attribution-ShareAlike 4.0 International License}. +\end{document} diff --git a/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf b/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf new file mode 100644 index 0000000..057ee0b --- /dev/null +++ b/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/1/coin.c b/usth/MATH2.3/1/coin.c new file mode 100644 index 0000000..d4fe339 --- /dev/null +++ b/usth/MATH2.3/1/coin.c @@ -0,0 +1,17 @@ +#include <stdio.h> + +int main() +{ + int pennies; + scanf("%d", &pennies); + int quarters = pennies / 25; + pennies %= 25; + int dimes = pennies / 10; + pennies %= 10; + int nickels = pennies / 5; + pennies %= 5; + + printf("%d quarters, %d dimes, %d nickels and %d pennies\n", + quarters, dimes, nickels, pennies); + return 0; +} diff --git a/usth/MATH2.3/1/schedule.c b/usth/MATH2.3/1/schedule.c new file mode 100644 index 0000000..6b70ca7 --- /dev/null +++ b/usth/MATH2.3/1/schedule.c @@ -0,0 +1,30 @@ +#include <stdio.h> +#include <stdlib.h> + +struct talk { + int start, end; +}; + +int cmp(const void *x, const void *y) +{ + return ((struct talk *) x)->end - ((struct talk *) y)->end; +} + +int main() +{ + size_t n; + scanf("%zu", &n); + struct talk *a = malloc(n * sizeof(struct talk)); + for (size_t i = 0; i < n; ++i) + scanf("%d %d", &a[i].start, &a[i].end); + + qsort(a, n, sizeof(struct talk), cmp); + int start = a->start; + for (size_t i = 0; i < n; ++i) + if (a[i].start >= start) { + printf("%d %d\n", a[i].start, a[i].end); + start = a[i].end; + } + + return 0; +} diff --git a/usth/MATH2.3/1/search.c b/usth/MATH2.3/1/search.c new file mode 100644 index 0000000..c9dd06d --- /dev/null +++ b/usth/MATH2.3/1/search.c @@ -0,0 +1,50 @@ +#include <stdio.h> + +void *lsearch(const void *key, const void *base, + size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + for (const char *p = base; nmemb--;) + if (compar(key, p)) + p += size; + else + return (void *) p; + return NULL; +} + +void *binary_search(const void *key, const void *base, + int lo, int hi, size_t size, + int (*compar)(const void *, const void *)) +{ + if (lo > hi) + return NULL; + + int mid = (lo + hi) >> 1; + int c = compar(key, (char *) base + mid * size); + if (c > 0) + return binary_search(key, base, mid + 1, hi, size, compar); + if (c < 0) + return binary_search(key, base, lo, mid - 1, size, compar); + return (char *) base + mid * size; +} + +void *bsearch(const void *key, const void *base, + size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + return binary_search(key, base, 0, nmemb, size, compar); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +int main() +{ + int a[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88}; + int *l = lsearch(a + 7, a, sizeof(a) / sizeof(int), sizeof(int), cmp); + int *b = bsearch(a + 7, a, sizeof(a) / sizeof(int), sizeof(int), cmp); + printf("%zu %zu\n", l - a, b - a); + return 0; +} diff --git a/usth/MATH2.3/2/README.md b/usth/MATH2.3/2/README.md new file mode 100644 index 0000000..df599a5 --- /dev/null +++ b/usth/MATH2.3/2/README.md @@ -0,0 +1,59 @@ +# Graphs +## Problem 1 +`bipartite.cc` (C++17) takes an natural number `n` of edges and `n` lines +of pairs of connected vertices from stdin and print either `yes` or `no` to +stdout if the given graph is or is not bipartite respectively. + +## Problem 2 +`adjmat2edges.cc` takes an natural number `n` and a `n`-by-`n` adjacent matrix +of natural numbers from stdin and print triplets (`u`, `v`, `m`) separated by +spaces to stdout, where `u`, `v` are vertices and `m > 0` is the number of edges +connecting these two. + +## Problem 3 +`incidentmat2edges.cc` take 2 natural numbers `v`, `e` and a `v`-by-`e` +incidental matrix from stdin and print each edge along with number of its +appearance to stdout, e.g. + +### Input + 2 2 + 1 1 + 1 1 + +### Output + 0 1 2 + +## Problem 4 +`dijkstra.cc` (C++17) takes a natural number `n` of edges, 2 positive numbers +`s` and `e` (starting and ending of path), then `n` pairs of connected vertices +(both in `1..1023`) and the edge's weight. The output to stdout is the path +and the length, e.g. + +### Input + 9 1 6 + 1 2 4 + 1 3 2 + 2 3 1 + 2 4 5 + 3 5 10 + 3 4 8 + 4 5 2 + 4 6 6 + 5 6 3' + +### Output + 1 3 2 4 5 6 (length of 13) + +## Problem 5 +`connected.cc` (C++17) takes a natural number `n` and `n` pairs of connected +vertices from stdin and print the number of connected components of the given +undirected graph to stdout, e.g. + +### Input + 3 + 1 2 + 3 4 + 4 5 + +### Output + 2 diff --git a/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf new file mode 100644 index 0000000..3ac3407 --- /dev/null +++ b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/2/adjmat2edges.cc b/usth/MATH2.3/2/adjmat2edges.cc new file mode 100644 index 0000000..d9cf14f --- /dev/null +++ b/usth/MATH2.3/2/adjmat2edges.cc @@ -0,0 +1,18 @@ +#include <iostream> + +using namespace std; + +int +main () +{ + size_t n; + int b; + cin >> n; + for (size_t i = 0; i < n; ++i) + for (size_t j = 0; j < n; ++j) + { + cin >> b; + if (i <= j && b > 0) + cout << i << " " << j << " " << b << endl; + } +} diff --git a/usth/MATH2.3/2/bipartite.cc b/usth/MATH2.3/2/bipartite.cc new file mode 100644 index 0000000..49b8dfd --- /dev/null +++ b/usth/MATH2.3/2/bipartite.cc @@ -0,0 +1,55 @@ +#include <iostream> +#include <queue> +#include <unordered_map> +#include <set> + +using namespace std; + +int +main () +{ + unordered_map<size_t, unordered_map<size_t, size_t>> adj; + size_t n, u, v; + cin >> n; + while (n--) + { + cin >> u >> v; + adj[u][v]++; + adj[v][u]++; + } + + queue<size_t> q; + set<size_t> one, another; + q.push (u); + one.insert (u); + + while (!q.empty ()) + { + u = q.front (); + q.pop (); + if (adj[u][u]) + { + cout << "no" << endl; + return 0; + } + for (auto const& [v, b] : adj[u]) + { + if (!b) + continue; + if (one.count (v) && one.count (u) + || another.count (v) && another.count (u)) + { + cout << "no" << endl; + return 0; + } + if (one.count (v) || another.count (v)) + continue; + q.push (v); + if (one.count (u)) + another.insert (v); + else + one.insert (v); + } + } + cout << "yes" << endl; +} diff --git a/usth/MATH2.3/2/connected.cc b/usth/MATH2.3/2/connected.cc new file mode 100644 index 0000000..0659094 --- /dev/null +++ b/usth/MATH2.3/2/connected.cc @@ -0,0 +1,44 @@ +#include <iostream> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +using namespace std; + +int +main () +{ + size_t n, a, b; + unordered_map<size_t, unordered_set<size_t>> edges; + + cin >> n; + for (size_t i = 0; i < n; ++i) + { + cin >> a >> b; + edges[a].insert (b); + edges[b].insert (a); + } + + unordered_set<size_t> s; + size_t count = 0; + for (auto const& [v, p] : edges) + { + if (s.count (v)) + continue; + count++; + vector<size_t> fifo {v}; + while (!fifo.empty ()) + { + size_t u = fifo.back (); + fifo.pop_back (); + if (s.count (u)) + continue; + s.insert (u); + for (auto const& w : edges[u]) + if (!s.count (w)) + fifo.push_back (w); + } + } + + cout << count << endl; +} diff --git a/usth/MATH2.3/2/dijkstra.cc b/usth/MATH2.3/2/dijkstra.cc new file mode 100644 index 0000000..e8a7931 --- /dev/null +++ b/usth/MATH2.3/2/dijkstra.cc @@ -0,0 +1,55 @@ +#include <iostream> +#include <deque> +#include <queue> +#include <unordered_map> +#include <vector> + +#define ENCODE(w, c, p) (((w) << 20) + ((c) << 10) + (p)) +#define WEIGHT(x) ((x) >> 20) +#define CUR(x) ((x) >> 10 & 1023) +#define PREV(x) ((x) & 1023) + +using namespace std; + +int +main () +{ + size_t n, a, b, w, s, e; + unordered_map<size_t, unordered_map<size_t, size_t>> edges; + + cin >> n >> s >> e; + for (size_t i = 0; i < n; ++i) + { + cin >> a >> b >> w; + edges[a][b] = edges[b][a] = w; + } + + unordered_map<size_t, size_t> prev; + priority_queue<size_t, vector<size_t>, greater<size_t>> pq; + pq.push (ENCODE (0, s, s)); + + while (!pq.empty ()) + { + size_t p = pq.top (); + a = PREV (p); + b = CUR (p); + w = WEIGHT (p); + if (!prev[b]) + prev[b] = a; + if (b == e) + break; + pq.pop (); + + for (auto const& [i, v] : edges[b]) + if (!prev[i]) + pq.push (ENCODE (w + v, i, b)); + } + + deque<size_t> d; + for (; e != s; e = prev[e]) + d.push_front (e); + d.push_front (e); + for (auto const& i : d) + cout << i << " "; + cout << "(length of " << w << ")" << endl; +} diff --git a/usth/MATH2.3/2/incidentmat2edges.cc b/usth/MATH2.3/2/incidentmat2edges.cc new file mode 100644 index 0000000..2fe5d79 --- /dev/null +++ b/usth/MATH2.3/2/incidentmat2edges.cc @@ -0,0 +1,33 @@ +#include <iostream> +#include <map> +#include <utility> + +using namespace std; + +int +main () +{ + int v, e, b; + map<pair<int, int>, int> m; + + cin >> v >> e; + for (int i = 0; i < v; ++i) + { + pair<int, int> p {-1, -1}; + + for (int j = 0; j < e; ++j) + { + cin >> b; + if (!b) + continue; + if (p.first < 0) + p.first = p.second = j; + else + p.second = j; + } + m[p]++; + } + + for (auto const& [p, c] : m) + cout << p.first << " " << p.second << " " << c << endl; +} diff --git a/usth/MATH2.3/3/README.md b/usth/MATH2.3/3/README.md new file mode 100644 index 0000000..fed19eb --- /dev/null +++ b/usth/MATH2.3/3/README.md @@ -0,0 +1,76 @@ +# Trees +## Problem 1 +`graph-is-tree.cc` (C++17) take a natural numbers `n` and a `n`-by-`n` adjacent +matrix from stdin and print to stdout either yes or no depending on whether the +given graph is a tree or not, e.g. + +### Input + 3 + 0 1 0 + 1 0 1 + 0 1 0 + +### Output + yes + +## Problem 2 +`binary-search-tree.c` takes a natural number `n` and `n` integers from stdin +and print to stdout a horizontal binary search tree formed (naïvely) from the +given input, e.g. + +### Input + 7 + 34 45 21 65 12 546 23 + +### Output + 12 + 21 + 23 + 34 + 45 + 65 + 546 + +## Problem 3 +`dc.cc` takes from stdin a list of numbers and operator, each terminated by a +semi-colon and print to stdout the evaluation of the given postfix arithmetic +expression, e.g. + +### Input + 6.9;4.20;+;2;^;6.9;4;-;3;/;+; + +### Output + 124.177 + +## Problem 4 +`st-dfs.cc` (C++17) takes a natural number `n` and an `n`-by-`n` adjacent +matrix from stdin and print the edges on a spanning tree of the given graph to +stdout, e.g. + +### Input + 4 + 0 1 1 1 + 1 0 1 1 + 1 1 0 1 + 1 1 1 0 + +### Output + 2 3 + 0 3 + 1 2 + +## Problem 5 +`sum-set.cc` takes a natural number `n` and a line of positive integers on one +line from stdin and print numbers whose sum are `n`, separated by a newline, to +stdout, e.g. + +### Input + 7 + 1 2 3 4 5 6 7 8 9 + +### Output + 1 2 4 + 1 6 + 2 5 + 3 4 + 7 diff --git a/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf new file mode 100644 index 0000000..cd0bef4 --- /dev/null +++ b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/3/a.out b/usth/MATH2.3/3/a.out new file mode 100755 index 0000000..e3f63ce --- /dev/null +++ b/usth/MATH2.3/3/a.out Binary files differdiff --git a/usth/MATH2.3/3/binary-search-tree.c b/usth/MATH2.3/3/binary-search-tree.c new file mode 100644 index 0000000..725fa44 --- /dev/null +++ b/usth/MATH2.3/3/binary-search-tree.c @@ -0,0 +1,68 @@ +#include <stdio.h> +#include <stdlib.h> + +#define MKTREE(entry, left, right) (cons((entry), cons((left), cons((right), NULL)))) +#define ENTRY(tree) (car((tree))) +#define LEFT(tree) (car(cdr((tree)))) +#define RIGHT(tree) (car(cdr(cdr((tree))))) + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *first, construct *rest) +{ + construct *list = malloc(sizeof(construct)); + list->car = first; + list->cdr = rest; + return list; +} + +void *car(construct *list) +{ + return list->car; +} + +construct *cdr(construct *list) +{ + return list->cdr; +} + +construct *insert(void *a, construct *tree) +{ + if (tree == NULL) + return MKTREE(a, NULL, NULL); + if (*(int *) a < *(int *) ENTRY(tree)) + return MKTREE(ENTRY(tree), insert(a, LEFT(tree)), RIGHT(tree)); + return MKTREE(ENTRY(tree), LEFT(tree), insert(a, RIGHT(tree))); +} + +void display(construct *tree, size_t indent) +{ + if (tree == NULL) + return; + display(LEFT(tree), indent + 1); + for (size_t i = 0; i++ < indent; putchar(9)); + printf("%d", *(int *) ENTRY(tree)); + putchar(10); + display(RIGHT(tree), indent + 1); +} + +int main() +{ + size_t n; + scanf("%zu", &n); + + construct *tree = NULL; + while (n--) { + int *a = malloc(sizeof(int)); + scanf("%d", a); + tree = insert(a, tree); + } + + display(tree, 0); + + return 0; +} diff --git a/usth/MATH2.3/3/dc.cc b/usth/MATH2.3/3/dc.cc new file mode 100644 index 0000000..b69742a --- /dev/null +++ b/usth/MATH2.3/3/dc.cc @@ -0,0 +1,43 @@ +#include <cmath> +#include <iostream> +#include <sstream> +#include <string> +#include <vector> + +using namespace std; + +int +main () +{ + double num, x, y; + string op; + vector<double> v; + + while (cin.peek () != '\n') + { + getline (cin, op, ';'); + stringstream s {op}; + s >> num; + if (s) + { + v.push_back (num); + continue; + } + + y = v.back (); + v.pop_back (); + x = v.back (); + v.pop_back (); + if (op == "^") + v.push_back (pow (x, y)); + else if (op == "+") + v.push_back (x + y); + else if (op == "-") + v.push_back (x - y); + else if (op == "*") + v.push_back (x * y); + else if (op == "/") + v.push_back (x / y); + } + cout << v.back () << endl; +} diff --git a/usth/MATH2.3/3/graph-is-tree.cc b/usth/MATH2.3/3/graph-is-tree.cc new file mode 100644 index 0000000..f79564d --- /dev/null +++ b/usth/MATH2.3/3/graph-is-tree.cc @@ -0,0 +1,56 @@ +#include <iostream> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +using namespace std; + +int +main () +{ + size_t n; + int b; + unordered_map<size_t, unordered_set<size_t>> edges; + + int m = 0; + cin >> n; + for (size_t i = 0; i < n; ++i) + for (size_t j = 0; j < n; ++j) + { + cin >> b; + if (!b || i > j) + continue; + edges[i].insert (j); + edges[j].insert (i); + m++; + } + + if (n - m - 1) + { + cout << "no" << endl; + return 0; + } + + unordered_set<size_t> s; + int count = -1; + for (auto const& [v, p] : edges) + { + if (s.count (v)) + continue; + count++; + vector<size_t> lifo {v}; + while (!lifo.empty ()) + { + size_t u = lifo.back (); + lifo.pop_back (); + if (s.count (u)) + continue; + s.insert (u); + for (auto const& w : edges[u]) + if (!s.count (w)) + lifo.push_back (w); + } + } + + cout << (count ? "no" : "yes") << endl; +} diff --git a/usth/MATH2.3/3/st-dfs.cc b/usth/MATH2.3/3/st-dfs.cc new file mode 100644 index 0000000..89814dd --- /dev/null +++ b/usth/MATH2.3/3/st-dfs.cc @@ -0,0 +1,44 @@ +#include <iostream> +#include <unordered_map> + +using namespace std; + +void +dfs (unordered_map<size_t, unordered_map<size_t, int>>& graph, + unordered_map<size_t, int>& been, size_t current) +{ + been[current] = 1; + for (auto const& [i, b] : graph[current]) + if (b > 0) + if (been[i]) + graph[current][i] = graph[i][current] = 0; + else + { + graph[current][i] = graph[i][current] = -1; + dfs (graph, been, i); + } +} + +int +main () +{ + size_t n; + unordered_map<size_t, unordered_map<size_t, int>> edges; + + cin >> n; + for (size_t i = 0; i < n; ++i) + for (size_t j = 0; j < n; ++j) + { + cin >> edges[i][j]; + edges[j][i] = edges[i][j]; + } + + unordered_map<size_t, unordered_map<size_t, int>> st; + unordered_map<size_t, int> been; + dfs (edges, been, 0); + + for (auto const& [i, m] : edges) + for (auto const& [j, b] : m) + if (b && i <= j) + cout << i << " " << j << endl; +} diff --git a/usth/MATH2.3/3/sum-set.cc b/usth/MATH2.3/3/sum-set.cc new file mode 100644 index 0000000..880fc6d --- /dev/null +++ b/usth/MATH2.3/3/sum-set.cc @@ -0,0 +1,44 @@ +#include <iostream> +#include <vector> + +using namespace std; + +void +backtrack (vector<size_t>& big, vector<size_t>& smol, size_t& n, size_t index) +{ + size_t sum = 0; + for (auto const& i : smol) + sum += i; + if (sum == n) + { + for (auto const& i : smol) + cout << i << " "; + cout << endl; + } + else + for (size_t i = index; i < big.size (); ++i) + if (sum + big[i] <= n) + { + smol.push_back (big[i]); + backtrack (big, smol, n, i + 1); + smol.pop_back (); + } +} + +int +main () +{ + size_t n; + size_t tmp; + vector<size_t> s; + + cin >> n; + for (size_t i = 0; i < n; ++i) + { + cin >> tmp; + s.push_back (tmp); + } + + vector<size_t> r; + backtrack (s, r, n, 0); +} diff --git a/usth/MATH2.3/4/README.md b/usth/MATH2.3/4/README.md new file mode 100644 index 0000000..880dacf --- /dev/null +++ b/usth/MATH2.3/4/README.md @@ -0,0 +1,71 @@ +# Booleans +## Problem 1 +`deg3.c` prints the a table listing the set of values of all 256 Boolean +functions of degree three to stdout. + +## Problem 2 +`sum-of-products.c` takes 2 natural numbers `n` and `f` from stdin, where `f` +is the encoded truth table of a Boolean function of degree `n`, for example, + +| x0 | x1 | value | +| :---: | :---: | :---: | +| 0 | 0 | 1 | +| 0 | 1 | 0 | +| 1 | 0 | 1 | +| 1 | 1 | 0 | + +will be encoded as `0b0101 = 5`. The program then print the bitwise arithmetic +sum-of-products expression to stdout, e.g. + +### Input + 2 5 + +### Output + ~x0&~x1 | ~x0&x1 + +## Problem 3 +`k-map`, e.g. + +### Input + 0 0 0 1 + 0 0 1 0 + 0 1 0 1 + 1 0 0 0 + 1 1 1 0 + 0 1 1 0 + 1 1 0 1 + 1 0 1 0 + +### Output + 00 01 10 11 + 0 1 0 1 1 + 0 0 0 0 0 + +## Problem 4 +`threshold.c` takes in natural number `n`, a real threshold value `t` and `n` +weights, then `n` boolean values from stdin and print to stdout the output of +the given threshold gate, e.g. + +### Input + 7 0.25051534245890184 + 0.11609819805105248 + 0.7924365005827357 + 0.9835187780201641 + 0.4235209817923591 + 0.08303890030044114 + 0.7196176517110272 + 0.988645113198539 + 1 1 0 1 1 0 1 + +### Output + 1 + +## Problem 5 +`sum.c` takes similar input format from stdin and print the bitwise arithmetic +expression using only bit flip (`~`) and addition (`|`) to stdout, e.g. + +### Input + 3 69 + +### Output + ~(~x0 | x1 | x2) | ~(~x0 | ~x1 | x2) | ~(~x0 | ~x1 | ~x2) diff --git a/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf new file mode 100644 index 0000000..fd3680e --- /dev/null +++ b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/4/deg3.c b/usth/MATH2.3/4/deg3.c new file mode 100644 index 0000000..a4f5726 --- /dev/null +++ b/usth/MATH2.3/4/deg3.c @@ -0,0 +1,18 @@ +#include <stdio.h> + +int main() +{ + printf("(x y z)"); + for (int i = 0; i < 8; ++i) + printf("\t(%d %d %d)", i & 4 && 1, i & 2 && 1, i & 1 && 1); + putchar(10); + + for (int i = 0; i < 256; ++i) { + printf("f%02x", i); + for (int j = 0; j < 8; ++j) + printf("\t%d", i & 1 << j && 1); + putchar(10); + } + + return 0; +} diff --git a/usth/MATH2.3/4/k-map.c b/usth/MATH2.3/4/k-map.c new file mode 100644 index 0000000..ef19b80 --- /dev/null +++ b/usth/MATH2.3/4/k-map.c @@ -0,0 +1,16 @@ +#include <stdio.h> + +int main() +{ + int x, y, z, f[8]; + + for (int i = 0; i < 8; ++i) { + scanf("%d %d %d", &x, &y, &z); + scanf("%d", f + x + (y << 1) + (z << 2)); + } + + printf("\t00\t01\t10\t11\n0\t%d\t%d\t%d\t%d\n0\t%d\t%d\t%d\t%d\n", + f[0], f[1], f[2], f[3], f[4], f[5], f[6], f[7]); + + return 0; +} diff --git a/usth/MATH2.3/4/sum-of-products.c b/usth/MATH2.3/4/sum-of-products.c new file mode 100644 index 0000000..3fac72b --- /dev/null +++ b/usth/MATH2.3/4/sum-of-products.c @@ -0,0 +1,25 @@ +#include <stdio.h> + +int main() +{ + size_t n, f; + int b = 0; + + scanf("%zu %zu", &n, &f); + for (size_t i = 0; !(i >> n); ++i) { + if (!(f & 1 << i)) + continue; + if (b) + printf(" | "); + b = 1; + printf(i & 1 ? "x0" : "~x0"); + for (size_t j = 1; j < n; ++j) + if (i & 1 << j) + printf("&x%zu", j); + else + printf("&~x%zu", j); + } + putchar(10); + + return 0; +} diff --git a/usth/MATH2.3/4/sum.c b/usth/MATH2.3/4/sum.c new file mode 100644 index 0000000..8fd28f3 --- /dev/null +++ b/usth/MATH2.3/4/sum.c @@ -0,0 +1,26 @@ +#include <stdio.h> + +int main() +{ + size_t n, f; + int b = 0; + + scanf("%zu %zu", &n, &f); + for (size_t i = 0; !(i >> n); ++i) { + if (!(f & 1 << i)) + continue; + if (b) + printf(" | "); + b = 1; + printf(i & 1 ? "~(x0" : "~(~x0"); + for (size_t j = 1; j < n; ++j) + if (i & 1 << j) + printf(" | ~x%zu", j); + else + printf(" | x%zu", j); + putchar(41); + } + putchar(10); + + return 0; +} diff --git a/usth/MATH2.3/4/threshold.c b/usth/MATH2.3/4/threshold.c new file mode 100644 index 0000000..5c39b3c --- /dev/null +++ b/usth/MATH2.3/4/threshold.c @@ -0,0 +1,23 @@ +#include <stdio.h> +#include <stdlib.h> + +int main() +{ + size_t n; + scanf("%zu", &n); + + double t, *weights = malloc(n * sizeof(double)); + scanf("%lf", &t); + for (size_t i = 0; i < n; ++i) + scanf("%lf", weights + i); + + int tmp; + for (size_t i = 0; i < n; ++i) { + scanf("%d", &tmp); + t -= tmp && weights[i]; + } + + putchar((t <= 0) + 48); + putchar(10); + return 0; +} diff --git a/usth/MATH2.3/5/README.md b/usth/MATH2.3/5/README.md new file mode 100644 index 0000000..70e52fa --- /dev/null +++ b/usth/MATH2.3/5/README.md @@ -0,0 +1,105 @@ +# Computations +## Problem 1 +`automata.c`, e.g. + +### Input + 4 + 1 1 3 + 0 1 2 + 0 3 0 + 1 1 2 + 4 0011 + +### Output + yes + +## Problem 2 +`nfa.cc` takes a state table of a non-deterministic finite-state automaton, its +final states and a string from stdin and print either `yes` or `no` to stdout +to answer whether this string is recognized by the automaton, e.g. + +### Input + 12 + 0 0 0 + 0 0 1 + 0 1 3 + 1 0 0 + 1 1 1 + 1 1 3 + 2 1 0 + 2 1 2 + 3 0 0 + 3 0 1 + 3 0 2 + 3 1 1 + 2 + 2 3 + 101 + +### Output + yes + +## Problem 3 +`automata-to-grammar.c` + +### Input + 4 + 1 1 3 + 0 1 2 + 0 3 0 + 1 1 2 + +### Output + S -> $ + S -> 0T + S -> 1V + T -> 0T + T -> 1U + U -> 0V + U -> 1S + V -> $ + V -> 0T + V -> 1U + +## Problem 4 +`grammar-to-automata.cc` (C++17) + +### Input + 10 + S -> $ + S -> 0T + S -> 1V + T -> 0T + T -> 1U + U -> 0V + U -> 1S + V -> $ + V -> 0T + V -> 1U + +### Output + 4 + V T U 1 + U V S 0 + S T V 1 + T T U 0 + +## Problem 5 +`turing.cc` (C++17) takes a natural number `n` and `n` 5-tuples representing a +Turing machine (with `-1` being the blank), a natural number `m` and a string +of `m` binaries from stdin, then print the output string to stdout, e.g. + +### Input + 7 + 0 0 0 0 1 + 0 1 1 1 1 + 0 -1 3 -1 1 + 1 0 0 0 1 + 1 1 2 0 -1 + 1 -1 3 -1 1 + 2 1 3 0 1 + 6 + 0 1 0 1 1 0 + +### Output + 010000 diff --git a/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf new file mode 100644 index 0000000..47d14ce --- /dev/null +++ b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf Binary files differdiff --git a/usth/MATH2.3/5/automata-to-grammar.c b/usth/MATH2.3/5/automata-to-grammar.c new file mode 100644 index 0000000..430782a --- /dev/null +++ b/usth/MATH2.3/5/automata-to-grammar.c @@ -0,0 +1,16 @@ +#include <stdio.h> + +int main() +{ + int n, b, j, k; + + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + scanf("%d %d %d", &b, &j, &k); + if (b) + printf("%c -> $\n", 'S' + i); + printf("%c -> 0%c\n%c -> 1%c\n", i+83, j+83, i+83, k+83); + } + + return 0; +} diff --git a/usth/MATH2.3/5/automata.c b/usth/MATH2.3/5/automata.c new file mode 100644 index 0000000..d18ca1e --- /dev/null +++ b/usth/MATH2.3/5/automata.c @@ -0,0 +1,24 @@ +#include <stdio.h> + +int main() { + int n; + scanf("%d", &n); + + int F[n], f[n][2]; + for (int i = 0; i < n; ++i) + scanf("%d %d %d", F + i, f[i], f[i] + 1); + + int m; + scanf("%d ", &m); + + char c[m + 1]; + scanf("%s", c); + + int state = 0; + for (int i = 0; i < m; ++i) + state = f[state][c[i] - 48]; + + puts(F[state] ? "yes" : "no"); + + return 0; +} diff --git a/usth/MATH2.3/5/grammar-to-automata.cc b/usth/MATH2.3/5/grammar-to-automata.cc new file mode 100644 index 0000000..125b3c9 --- /dev/null +++ b/usth/MATH2.3/5/grammar-to-automata.cc @@ -0,0 +1,29 @@ +#include <iostream> +#include <string> +#include <unordered_map> + +using namespace std; + +int +main () +{ + int n; + cin >> n; + + unordered_map<char, unordered_map<int, char>> automata; + unordered_map<char, int> finals; + for (int i = 0; i < n; ++i) + { + char c; + string s, t; + cin >> c >> t >> s; + if (s == "$") + finals[c] = 1; + else + automata[c][s[0] - '0'] = (s.length () == 1) ? '$' : s[1]; + } + + cout << automata.size () << endl; + for (auto& [c, m] : automata) + cout << c << '\t' << m[0] << '\t' << m[1] << '\t' << finals[c] << endl; +} diff --git a/usth/MATH2.3/5/nfa.cc b/usth/MATH2.3/5/nfa.cc new file mode 100644 index 0000000..8401202 --- /dev/null +++ b/usth/MATH2.3/5/nfa.cc @@ -0,0 +1,45 @@ +#include <iostream> +#include <string> +#include <unordered_map> +#include <vector> + +using namespace std; + +bool +recognize (unordered_map<int, unordered_map<int, vector<int>>>& f, + unordered_map<int, bool>& F, string& s, int i, int r) +{ + if (i >= s.size ()) + return F[r]; + for (auto const& t : f[r][s[i] - '0']) + if (recognize (f, F, s, i + 1, t)) + return true; + return false; +} + +int +main () +{ + int n; + unordered_map<int, unordered_map<int, vector<int>>> f; + cin >> n; + while (n--) + { + int s, i, r; + cin >> s >> i >> r; + f[s][i].push_back (r); + } + + unordered_map<int, bool> F; + cin >> n; + while (n--) + { + int s; + cin >> s; + F[s] = true; + } + + string s; + cin >> s; + cout << (recognize (f, F, s, 0, 0) ? "yes" : "no") << endl; +} diff --git a/usth/MATH2.3/5/turing.cc b/usth/MATH2.3/5/turing.cc new file mode 100644 index 0000000..7ef5deb --- /dev/null +++ b/usth/MATH2.3/5/turing.cc @@ -0,0 +1,56 @@ +#include <iostream> +#include <deque> +#include <tuple> +#include <unordered_map> + +using namespace std; + +int +main () +{ + int n; + unordered_map<int, unordered_map<int, tuple<int, int, int>>> tuples; + cin >> n; + while (n--) + { + int s, x, t, y, d; + cin >> s >> x >> t >> y >> d; + tuples[s][x] = {t, y, d}; + } + + deque<int> input; + cin >> n; + while (n--) + { + int i; + cin >> i; + input.push_back (i); + } + + int o {0}, i {0}, s {0}, x, d; + for (;;) + { + tie (s, x, d) = tuples[s][input[i - o]]; + if (!d) + break; + + if (i < o) + { + input.push_front (x); + o++; + } + else if (i - o == input.size ()) + input.push_back (x); + else + input[i - o] = x; + + if (d < 0) + i--; + else + i++; + } + + for (auto const& i : input) + cout << i; + cout << endl; +} |