botayhard · March 20, 2024 12:59 · Mar 20, 2024
diff --git a/go b/go
@@ -0,0 +1,461 @@
+package main
+
+import (
+	"bufio"
+	"bytes"
+	"math"
+	"os"
+	"sort"
+
+	//"rand"
+	"strconv"
+	"strings"
+)
+
+const (
+	io = "std"
+)
+
+func main() {
+	scanner := bufio.NewScanner(os.Stdin)
+	inputFile, _ := os.Open("input.txt")
+	defer inputFile.Close()
+	if io == "file" {
+		scanner = bufio.NewScanner(inputFile)
+	}
+	const nCapacity = 4
+	const maxCapacity = nCapacity * 1024 * 1024 // nCapacity Mi
+	buf := make([]byte, maxCapacity)
+	scanner.Buffer(buf, maxCapacity)
+	writer := bufio.NewWriter(os.Stdout)
+	outputFile, _ := os.Open("output.txt")
+	defer outputFile.Close()
+	if io == "file" {
+		writer = bufio.NewWriter(outputFile)
+	}
+	defer writer.Flush()
+	scanner.Scan()
+	n := atoi(scanner.Text())
+	s := make([]string, n)
+	//ssl := make([][]string, n)
+	ss := make([]string, n)
+	cs := make(map[string]string)
+	for i := 0; i < n; i++ {
+		scanner.Scan()
+		s[i] = scanner.Text()
+		//ssl[i] = splite(s[i])
+		if _, e := cs[s[i]]; !e {
+			cs[s[i]] = SortString(s[i])
+		}
+		ss[i] = cs[s[i]]
+	}
+	scanner.Scan()
+	m := atoi(scanner.Text())
+	t := make([]string, m)
+	//tsl := make([][]string, m)
+	st := make([]string, m)
+	for j := 0; j < m; j++ {
+		scanner.Scan()
+		t[j] = scanner.Text()
+		//tsl[j] = splite(scanner.Text())
+		if _, e := cs[t[j]]; !e {
+			cs[t[j]] = SortString(t[j])
+		}
+		st[j] = cs[t[j]]
+	}
+	for j := 0; j < m; j++ {
+		f := false
+		for i := 0; i < n; i++ {
+			if t[j] == s[i] {
+				f = true
+				break
+			}
+			//println(st[j],ss[i])
+			if st[j] == ss[i] {
+				p := make([]bool, len(t[j]))
+				c := 0
+				r := false
+				for k := range t[j] {
+					if t[j][k] != s[i][k] {
+						p[k] = true
+						c++
+						if c > 2 {
+							break
+						}
+					}
+					if k > 0 {
+						if p[k-1] && p[k] && t[j][k-1] == s[i][k] && t[j][k] == s[i][k-1] {
+							r = true
+						}
+					}
+				}
+				if r && c == 2 {
+					f = true
+					break
+				}
+			}
+		}
+		if f {
+			writer.WriteString("1\n")
+		} else {
+			writer.WriteString("0\n")
+		}
+	}
+}
+
+func SortString(s string) string {
+	sl := splite(s)
+	sort.Strings(sl)
+	return FastConcat(sl)
+}
+
+func FastConcat(sl []string) string {
+	var b bytes.Buffer
+	for _, v := range sl {
+		b.WriteString(v)
+	}
+	return b.String()
+}
+
+func CompStringSlice(sl1 []string, sl2 []string) bool {
+	if len(sl1) != len(sl2) {
+		return false
+	}
+	for k := range sl1 {
+		if sl1[k] != sl2[k] {
+			return false
+		}
+	}
+	return true
+}
+
+func slatoi(sl []string) (r []int) {
+	for _, v := range sl {
+		r = append(r, atoi(v))
+	}
+	return
+}
+
+func pow2(n int) int {
+	return powint(2, n)
+}
+
+func isPow2(x int) bool {
+	return x > 0 && (x&(x-1)) == 0
+}
+
+func powint(n int, m int) int {
+	return int(math.Pow(float64(n), float64(m)))
+}
+
+func splite(s string) []string {
+	return split(s, "")
+}
+
+func splits(s string) []string {
+	return split(s, " ")
+}
+
+func split(s string, c string) (sl []string) {
+	sl = strings.Split(s, c)
+	return
+}
+
+func atoi(s string) (n int) {
+	n, _ = strconv.Atoi(s)
+	return
+}
+
+func itoa(i int) (s string) {
+	s = strconv.Itoa(i)
+	return
+}
+
+func ftoa(n float64, t int) string {
+	return strconv.FormatFloat(n, 'f', t, 64)
+}
+
+func reverse(s string) string {
+	r := []rune(s)
+	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
+		r[i], r[j] = r[j], r[i]
+	}
+	return string(r)
+}
+
+func isPalindrome(s string) bool {
+	return reverse(s) == s
+}
+
+func abs(n int) int {
+	if n < 0 {
+		return -1 * n
+	}
+	return n
+}
+
+func min(a int, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+func max(a int, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func isPrime(n int) bool {
+	if n < 2 || n%2 == 0 {
+		return false
+	}
+	if n < 4 {
+		return true
+	}
+	for i := 3; i*i <= n; i += 2 {
+		if n%i == 0 {
+			return false
+		}
+	}
+	return true
+}
+
+func FactRec(n int) int {
+	if n == 1 {
+		return 1
+	}
+	return n * FactRec(n-1)
+}
+
+func FactIt(n int) int {
+	result := 1
+	for i := 2; i <= n; i++ {
+		result *= i
+	}
+	return result
+}
+
+func GCD(a int, b int) int {
+	for b != 0 {
+		a, b = b, a%b
+	}
+	return a
+}
+
+func LCM(a int, b int) int {
+	return (a / GCD(a, b)) * b
+}
+
+func PrimeFactors(n int) (map[int]int, int) {
+	p := make(map[int]int)
+	f := 0
+	for n%2 == 0 {
+		p[2]++
+		n = n / 2
+		f++
+	}
+	for i := 3; i*i <= n; i = i + 2 {
+		for n%i == 0 {
+			p[i]++
+			n = n / i
+			f++
+		}
+	}
+	if n > 2 {
+		p[n]++
+		f++
+	}
+	return p, f
+}
+
+func com(m int, n int) (c int) {
+	// сочетания без повторений: n -- всего, m -- нужно выбрать
+	c = FactRec(n) / FactRec(m) / FactRec(n-m)
+	return
+}
+
+func comwr(m int, n int) (c int) {
+	// сочетания с повторенями: n -- всего, m -- нужно выбрать
+	c = FactRec(n+m-1) / FactRec(m) / FactRec(n-1)
+	return
+}
+
+func per(m int, n int) (a int) {
+	// размещения без повторений: n -- всего нужно разместить, m -- всего мест
+	a = FactRec(n) / FactRec(n-m)
+	return
+}
+
+func perwr(m int, n int) (a int) {
+	//размещения с повторениями: n -- всего нужно разместить, m -- всего мест
+	a = powint(n, m)
+	return
+}
+
+func arr(n int) (p int) {
+	// перестановки без повторений: n -- всего нужно разметить по n местам
+	p = FactRec(n)
+	return
+}
+
+func arrwr(nk []int, n int) (p int) {
+	// перестановки с повторениями: nk -- количество каждого из k типов различных предметов
+	p = FactRec(n)
+	for _, v := range nk {
+		p /= FactRec(v)
+	}
+	return
+}
+
+/*
+
+func bubbleSort(a []int) []int { // O(la^2)
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+	for i := 0; i < la; i++ {
+		for j := 0; j < la-i-1; j++ {
+			if a[j] > a[j+1] {
+				a[j], a[j+1] = a[j+1], a[j]
+			}
+		}
+	}
+	return a
+}
+
+func quickSort(a []int) []int { // O(la^2)
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+	l, r := 0, la-1
+	p := rand.Int() % la
+	a[p], a[r] = a[r], a[p]
+	for i := range a {
+		if a[i] < a[r] {
+			a[i], a[l] = a[l], a[i]
+			l++
+		}
+	}
+	return a
+}
+
+func insetSort(a []int) []int { // O(la^2)
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+	i := 1
+	for i < la {
+		j := i
+		for j >= 1 && a[j] < a[j-1] {
+			a[j], a[j-1] = a[j-1], a[j]
+			j--
+		}
+		i++
+	}
+	return a
+}
+
+func selectSort(a []int) []int { // O(la^2)
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+	i := 1
+	for i < la-1 {
+		j := i + 1
+		m := i
+		if j < la {
+			if a[j] < a[m] {
+				m = j
+			}
+			j++
+		}
+		if m != i {
+			a[i], a[m] = a[m], a[i]
+		}
+		i++
+	}
+	return a
+}
+
+
+func mergeFunc(fp []int, sp []int) []int {
+	n := make([]int, len(fp)+len(sp))
+	fpi := 0
+	spi := 0
+	ni := 0
+	for fpi < len(fp) && spi < len(sp) {
+		if fp[fpi] < sp[spi] {
+			n[ni] = fp[fpi]
+			fpi++
+		} else if sp[spi] < fp[fpi] {
+			n[ni] = sp[spi]
+			spi++
+		}
+		ni++
+	}
+	for fpi < len(fp) {
+		n[ni] = fp[fpi]
+		fpi++
+		ni++
+	}
+	for spi < len(sp) {
+		n[ni] = sp[spi]
+		spi++
+		ni++
+	}
+	return n
+}
+
+func mergeSort(a []int) []int { // O(la*log(la))
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+	fp := mergeSort(a[0 : la/2])
+	sp := mergeSort(a[la/2:])
+	return mergeFunc(fp, sp)
+}
+
+func countSort(a []int) []int { // O(la+k)
+	la := len(a)
+	if la < 2 {
+		return a
+	}
+    m:= a[0]
+    i := 1
+    for i < la {
+        if a[i] > m {
+            m = a[i]
+        }
+        i++
+    }
+    b:= make([]int, m + 1)
+    j := 0
+    for j < la {
+        b[a[j]]++
+        j++
+    }
+	lb:=len(b)
+    k := 1
+    for k < lb {
+        b[k] += b[k - 1]
+        k++
+    }
+    r := make([]int, la)
+    m = 0
+    for m < la {
+        r[b[a[m]] - 1] = a[m]
+        b[a[m]]--
+        m++
+    }
+    return r
+}
+
+*/