diff options
Diffstat (limited to 'introductory_problems')
-rw-r--r-- | introductory_problems/apple_division.cpp | 23 | ||||
-rw-r--r-- | introductory_problems/bit_strings.cpp | 21 | ||||
-rw-r--r-- | introductory_problems/chessboard_and_queens.cpp | 55 | ||||
-rw-r--r-- | introductory_problems/coin_piles.cpp | 12 | ||||
-rw-r--r-- | introductory_problems/digit_queries.cpp | 32 | ||||
-rw-r--r-- | introductory_problems/gray_code.cpp | 23 | ||||
-rw-r--r-- | introductory_problems/grid_paths.cpp | 47 | ||||
-rw-r--r-- | introductory_problems/number_spiral.cpp | 22 | ||||
-rw-r--r-- | introductory_problems/palindrome_reorder.cpp | 28 | ||||
-rw-r--r-- | introductory_problems/permutations.cpp | 18 | ||||
-rw-r--r-- | introductory_problems/readme.md | 103 | ||||
-rw-r--r-- | introductory_problems/tower_of_hanoi.cpp | 21 | ||||
-rw-r--r-- | introductory_problems/trailing_zeros.cpp | 13 | ||||
-rw-r--r-- | introductory_problems/two_knights.cpp | 13 | ||||
-rw-r--r-- | introductory_problems/two_sets.cpp | 27 |
15 files changed, 456 insertions, 2 deletions
diff --git a/introductory_problems/apple_division.cpp b/introductory_problems/apple_division.cpp new file mode 100644 index 0000000..11a0450 --- /dev/null +++ b/introductory_problems/apple_division.cpp @@ -0,0 +1,23 @@ +// 1623. Apple Division +#include <bits/stdc++.h> +using namespace std; + +int main() { + const long long max = INT_MAX; + static int n, p[20]; + long long a, b, best = max; + scanf("%d", &n); + for (int i = 0; i < n; i++) + scanf("%d", &p[i]); + for (int i = 0; i < (1 << n); i++) { + a = b = 0; + for (int j = 0; j < n; j++) { + if (i & (1 << j)) + a += p[j]; + else + b += p[j]; + } + best = min(best, abs(a - b)); + } + printf("%lld\n", best); +} diff --git a/introductory_problems/bit_strings.cpp b/introductory_problems/bit_strings.cpp new file mode 100644 index 0000000..84acfea --- /dev/null +++ b/introductory_problems/bit_strings.cpp @@ -0,0 +1,21 @@ +// 1617. Bit Strings +#include <bits/stdc++.h> + +const int mod = 1e9 + 7; + +long long fast_pow2(int x) { + long long res = 1, y = 2; + while (x) { + if (x & 1) + res = (res * y) % mod; + y = (y * y) % mod; + x >>= 1; + } + return res; +} + +int main() { + static int n; + scanf("%d", &n); + printf("%lld\n", fast_pow2(n)); +} diff --git a/introductory_problems/chessboard_and_queens.cpp b/introductory_problems/chessboard_and_queens.cpp new file mode 100644 index 0000000..4dc5f2f --- /dev/null +++ b/introductory_problems/chessboard_and_queens.cpp @@ -0,0 +1,55 @@ +// 1624. Chessboard and Queens +#include <bits/stdc++.h> +#include <cstdio> +using namespace std; + +const int n = 8; +char c; +int ans; +bool b[n][n], input[n][n]; + +bool place(int x, int y) { + bool valid = true; + for (int i = 0; i < n; i++) + if (b[x][i] || b[i][y]) + valid = false; + for (int i = 0; x - i >= 0 && y + i < n; i++) + if (b[x - i][y - i]) + valid = false; + for (int i = 0; x - i >= 0 && y + i < n; i++) + if (b[x - i][y + i]) + valid = false; + return valid; +} + +bool check(void) { + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + if (b[i][j] && input[i][j]) + return false; + return true; +} + +void dfs(int i) { + if (i == n) { + if (check()) + ans++; + return; + } + for (int j = 0; j < n; j++) + if (place(i, j)) { + b[i][j] = true; + dfs(i + 1); + b[i][j] = false; + } +} + +int main() { + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) { + scanf(" %c", &c); + input[i][j] = (c == '*'); + } + dfs(0); + printf("%d\n", ans); +} diff --git a/introductory_problems/coin_piles.cpp b/introductory_problems/coin_piles.cpp new file mode 100644 index 0000000..2d00cc6 --- /dev/null +++ b/introductory_problems/coin_piles.cpp @@ -0,0 +1,12 @@ +// 1754. Coin Piles +#include <bits/stdc++.h> +using namespace std; + +int main() { + static int t, a, b; + scanf("%d", &t); + for (int i = 0; i < t; i++) { + scanf("%d %d", &a, &b); + printf((((a + b) % 3) != 0 || a > 2 * b || b > 2 * a) ? "NO\n" : "YES\n"); + } +} diff --git a/introductory_problems/digit_queries.cpp b/introductory_problems/digit_queries.cpp new file mode 100644 index 0000000..008d3f5 --- /dev/null +++ b/introductory_problems/digit_queries.cpp @@ -0,0 +1,32 @@ +// 2431. Digit Queries +#include <bits/stdc++.h> +using namespace std; + +long long pow10(int x) { + long long res = 1; + for (int i = 0; i < x; i++) + res *= 10; + return res; +} + +int solve(long long n) { + if (n < 9) + return (int)n + 1; + int len = 1; + while (pow10(len - 1) * len * 9 < n) { + n -= 9 * pow10(len - 1) * len; + len++; + } + string s = to_string(pow10(len - 1) + n / len); + return (int)(s[n % len] - '0'); +} + +int main() { + static int q; + static long long k; + scanf("%d", &q); + for (int i = 0; i < q; i++) { + scanf("%lld", &k); + printf("%d\n", solve(k - 1)); + } +} diff --git a/introductory_problems/gray_code.cpp b/introductory_problems/gray_code.cpp new file mode 100644 index 0000000..9911cd4 --- /dev/null +++ b/introductory_problems/gray_code.cpp @@ -0,0 +1,23 @@ +// 2205. Gray Code +#include <bits/stdc++.h> +using namespace std; + +static int n; +const int max_n = 16; +static bool a[max_n + 1]; + +void print(void) { + for (int i = n; i; i--) + printf("%d", a[i]); + printf("\n"); +} + +int main() { + scanf("%d", &n); + print(); + for (int i = 1; i < 1 << n; i++) { + int lsb = __builtin_ffs(i); + a[lsb] ^= 1; + print(); + } +} diff --git a/introductory_problems/grid_paths.cpp b/introductory_problems/grid_paths.cpp new file mode 100644 index 0000000..778a344 --- /dev/null +++ b/introductory_problems/grid_paths.cpp @@ -0,0 +1,47 @@ +// 1625. Grid Paths +#include <bits/stdc++.h> +using namespace std; + +const int n = 7; +int ans; +char c[n * n + 1]; +bool vis[n + 1][n + 1]; + +bool inbound(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= n; } + +void dfs(int x, int y, int i) { + if (i == n * n - 1 || (x == n && y == 1)) { + ans += (i == n * n - 1 && (x == n && y == 1)); + return; + } + if ((!inbound(x + 1, y) || vis[x + 1][y]) && + (!inbound(x - 1, y) || vis[x - 1][y])) + if (inbound(x, y - 1) && !vis[x][y - 1] && inbound(x, y + 1) && + !vis[x][y + 1]) + return; + if ((!inbound(x, y + 1) || vis[x][y + 1]) && + (!inbound(x, y - 1) || vis[x][y - 1])) + if (inbound(x + 1, y) && !vis[x + 1][y] && inbound(x - 1, y) && + !vis[x - 1][y]) + return; + vis[x][y] = true; + if (c[i] == 'D' || c[i] == '?') + if (inbound(x + 1, y) && !vis[x + 1][y]) + dfs(x + 1, y, i + 1); + if (c[i] == 'U' || c[i] == '?') + if (inbound(x - 1, y) && !vis[x - 1][y]) + dfs(x - 1, y, i + 1); + if (c[i] == 'R' || c[i] == '?') + if (inbound(x, y + 1) && !vis[x][y + 1]) + dfs(x, y + 1, i + 1); + if (c[i] == 'L' || c[i] == '?') + if (inbound(x, y - 1) && !vis[x][y - 1]) + dfs(x, y - 1, i + 1); + vis[x][y] = false; +} + +int main() { + scanf(" %s", c); + dfs(1, 1, 0); + printf("%d\n", ans); +} diff --git a/introductory_problems/number_spiral.cpp b/introductory_problems/number_spiral.cpp new file mode 100644 index 0000000..95290b7 --- /dev/null +++ b/introductory_problems/number_spiral.cpp @@ -0,0 +1,22 @@ +// 1071. Number Spiral +#include <bits/stdc++.h> +using namespace std; + +long long x, y; + +long long solve(long long x, long long y) { + long long z = fmax(x, y) - 1; + if (z & 1) + return x < y ? z * z + x : z * z + 2 * z - y + 2; + else + return x < y ? z * z + 2 * z - x + 2 : z * z + y; +} + +int main() { + static int tmp; + scanf("%d", &tmp); + for (int i = 0; i < tmp; i++) { + scanf("%lld %lld", &x, &y); + printf("%lld\n", solve(x, y)); + } +} diff --git a/introductory_problems/palindrome_reorder.cpp b/introductory_problems/palindrome_reorder.cpp new file mode 100644 index 0000000..8e0a602 --- /dev/null +++ b/introductory_problems/palindrome_reorder.cpp @@ -0,0 +1,28 @@ +// 1755. Palindrome Reorder +#include <bits/stdc++.h> +using namespace std; + +int main() { + static char s[1000001]; + scanf("%s", s); + static int n = strlen(s), odd = -1, freq[26]; + for (int i = 0; i < n; i++) + freq[s[i] - 'A']++; + for (int i = 0; i < 26; i++) { + if (freq[i] & 1) { + if (odd != -1) { + printf("NO SOLUTION\n"); + } else { + odd = i; + } + } + } + for (int i = 0; i < 26; i++) + for (int j = 0; j < freq[i] / 2; j++) + printf("%c", i + 'A'); + if (odd != -1) + printf("%c", odd + 'A'); + for (int i = 25; i >= 0; i--) + for (int j = 0; j < freq[i] / 2; j++) + printf("%c", i + 'A'); +} diff --git a/introductory_problems/permutations.cpp b/introductory_problems/permutations.cpp new file mode 100644 index 0000000..46d8e79 --- /dev/null +++ b/introductory_problems/permutations.cpp @@ -0,0 +1,18 @@ +// 1070. Permutations +#include <bits/stdc++.h> +using namespace std; + +int main() { + static int num; + scanf("%d", &num); + if (num == 1) + printf("1 "); + else if (num <= 3) + printf("NO SOLUTION\n"); + else { + for (int i = 2; i <= num; i += 2) + printf("%d ", i); + for (int i = 1; i <= num; i += 2) + printf("%d ", i); + } +} diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md index cca3339..52fbe2d 100644 --- a/introductory_problems/readme.md +++ b/introductory_problems/readme.md @@ -22,8 +22,107 @@ You are given a DNA sequence: a string consisting of A, C, G, and T. Your task i **Output**: Print one integer: the length of the longest repetition. (Example: 3) ### Increasing Array -You are given an array of `n` integers. You want to modify the array so that it is increasing, ie. every element is at least as large as the previous element. On each move, you may increase the value of any elementby one. What is the minimum number of moves required? +You are given an array of `n` integers. You want to modify the array so that it is increasing, ie. every element is at least as large as the previous element. On each move, you may increase the value of any element by one. What is the minimum number of moves required? -**Input**: Thefirst input line contains an integer `n`: the size of the array. Then the second line contains `n` integers: the contents of the array. (Example: 5`\n`3 2 5 1 7) +**Input**: The first input line contains an integer `n`: the size of the array. Then the second line contains `n` integers: the contents of the array. (Example: 5`\n`3 2 5 1 7) **Output**: Print the minimum number of moves. (Example: 5) + +### Permutations +A permutation of integers `1, 2, ..., n` is called beautiful if there are no adjacent elements whose difference is 1. Given `n`, construct a beautiful permutation if such a permutation exists. + +**Input**: The only input line contains an integer `n`. (Example: 5) + +**Output**: Print a beautiful permutation of integers. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION". (Example: 4 2 5 3 1) + +### Number Spiral +A number spiral is an infinite grid whose upper-left square has number 1. Your task is to find out the number in row `y` and column `x`. + +**Input**: The first imput line contains an integer `t`: the number of tests. After this, there are `t` lines, each containing integers `y` and `x`. (Example: 3`\n`2 3`\n`1 1`\n`4 2) + +**Output**: For each test, print the number in row `y` and column `x`. (Example: 8 1 15) + +### Two Knights +Your task is to count for `k = 1, 2, ..., n` the number of ways two knights can be placed on a `k * k` chessboard so that they do not attack eachother. + +**Input**: The only input line contains an integer `n`. (Example: 8) + +**Output**: Print `n` integers: the results. (Example: 0 6 28 96 252 550 1056 1848) + +### Two Sets +Your task is to divide the numbers `1, 2, ..., n` into two sets of equal sum. + +**Input**: The only input line contains an integer `n`. (Example: 7) + +**Output**: Print "YES", if the division is possible, and "NO" otherwise. After this, print if the division is possible, print an example of how to create the sets. + +### Bit Strings +Your task is to calculate the number of bit strings of length `n`. For example, if `n = 3`, the correct answer is 8, because the possible bit strings are `000`, `001`, `010`, `011`, `100`, `101`, `110`, and `111`. + +**Input**: The only input line has an integer `n`. (Example: 3) + +**Output**: Print the result modulo 10E9 + 7. (Example: 8) + +### Trailing Zeros +Your task is to calculate the number of trailing zeros in the factorial `n!`. For example, `20! = 20!=2432902008176640000` and it has 4 trailing zeros. + +**Input**: The only input line has an integer `n`. (Example: 20) + +**Output**: Print the number of in `n!`. (Example: 4) + +### Coin Piles +You have two coin piles containing `a` and `b` coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile. Your task is to efficiently find out if you can empty both the piles. + +**Input**: The first input line has an integer `t`: the number of tests. After this, there are `t` lines, each of which has two integers `a` and `b`: the numbers of coins in the piles. (Example: 3`\n`2 1`\n`2 2`\n`3 3) + +**Output**: For each test, print "YES" if you can empty the piles and "NO" otherwise. (Example: YES NO YES) + +### Palindrome Reorder +Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (ie. it reads the same forwards and backwards). + +**Input**: The only input line has a string of length `n` consisting of characters A-Z. (Example: AAAACACBA) + +**Output**: Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTIONS". (Example: AACABACAA) + +### Gray Code +A gray code is a list of `2^n` bit strings of length `n`, where any two successive strings differ in exactly one bit (ie. their hamming distance is one). Your task is to create a gray code for a given length `n`. + +**Input**: The only input line has an integer `n`. (Example: 2) + +**Output**: Print `2^n` lines that describes the gray code. You can print any valid solution. (Example: 00 01 11 10) + +### Digit Queries +Consider an infinite string that consists of all positive integers in increasing order: 12345678910111213141516171819202122232425... Your task is to process `q` queries of the form: what is the digit at position `k` in the string? + +**Input**: The first input line has an integer `q`: the number of queries. After this, there are `q` lines that describe the queries. Each line has an integer `k`: a 1-indexed position in the string. (Example: 3 7 19 12) + +**Output**: For each query, print the corresponding digit. (Example: 7 4 1) + +### Grid Paths +There are 88418 paths in a 7 * 7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left), and R (right). You are given a description of a path which may also contain certain characters ? (any direction). Your task is to calculate the number of paths that match the description. + +**Input**: The only input line has a 48-character string of characters ?, D, U, L, and R. (Example: ??????R??????U??????????????????????????LD????D?) + +**Output**: Print one integer: the total number of paths. (Example: 201) + +### Tower of Hanoi +The Tower of Hanoi game consists of three stacks (left, middle, and right) and `n` round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom. +The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk. Your task is to find a solution that minimises the number of moves. + +**Input**: The only input line has an integer `n`: the number of disks. (Example: 2) + +**Output**: First print an integer `k`: the minimum number of moves. After this, print `k` lines that describe the moves. Each line has two integers `a` and `b`: you move a distk from stack `a` to stack `b`. (Example: 3 12 13 23) + +### Apple Division +There are `n` apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal. + +**Input**: The first input line has an integer `n`: the number of apples. The next input line has `n` integers `p1, p2, ..., pn`: the weight of each apple. (Example: 5`\n`3 2 7 4 1) + +**Output**: Print one integer: the minimum difference between the weights of the groups. (Example: 1) + +### Chessboard and Queens +Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking eachother. How many possible ays are there to place the queens? + +**Input**: The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*). + +**Output**: Print one integer: the number of ways you can place the queens. diff --git a/introductory_problems/tower_of_hanoi.cpp b/introductory_problems/tower_of_hanoi.cpp new file mode 100644 index 0000000..806fc51 --- /dev/null +++ b/introductory_problems/tower_of_hanoi.cpp @@ -0,0 +1,21 @@ +// 2165. Tower of Hanoi +#include <bits/stdc++.h> +using namespace std; + +void move(int from, int to, int depth) { + if (depth == 1) { + printf("%d %d\n", from, to); + return; + } + int other = 6 - from - to; + move(from, other, depth - 1); + printf("%d %d\n", from, to); + move(other, to, depth - 1); +} + +int main() { + static int n; + scanf("%d", &n); + printf("%d\n", (1 << n) - 1); + move(1, 3, n); +} diff --git a/introductory_problems/trailing_zeros.cpp b/introductory_problems/trailing_zeros.cpp new file mode 100644 index 0000000..02fff6f --- /dev/null +++ b/introductory_problems/trailing_zeros.cpp @@ -0,0 +1,13 @@ +// 1618. Trailing Zeros +#include <bits/stdc++.h> +using namespace std; + +int main() { + static int n, ans; + scanf("%d", &n); + while (n) { + n /= 5; + ans += n; + } + printf("%d\n", ans); +} diff --git a/introductory_problems/two_knights.cpp b/introductory_problems/two_knights.cpp new file mode 100644 index 0000000..60933bc --- /dev/null +++ b/introductory_problems/two_knights.cpp @@ -0,0 +1,13 @@ +// 1072. Two Knights +#include <bits/stdc++.h> +using namespace std; + +int main() { + static int n; + scanf("%d", &n); + for (int i = 1; i <= n; i++) { + long long cnt = 1LL + (i - 1) * (i - 2) / 2; + cnt = cnt * (i - 1) * (i + 4); + printf("%lld\n", cnt); + } +} diff --git a/introductory_problems/two_sets.cpp b/introductory_problems/two_sets.cpp new file mode 100644 index 0000000..ce13e0c --- /dev/null +++ b/introductory_problems/two_sets.cpp @@ -0,0 +1,27 @@ +// 1092. Two Sets +#include <bits/stdc++.h> +using namespace std; + +int main() { + static int n; + scanf("%d", &n); + if (n % 4 == 1 || n % 4 == 2) + printf("NO\n"); + else if (n % 4 == 3) { + printf("YES\n"); + printf("%d\n", n / 2); + for (int i = 2; i <= n / 2; i += 2) + printf("%d %d ", i, n - i); + printf("%d\n%d\n", n, n / 2 + 1); + for (int i = 1; i <= n / 2; i += 2) + printf("%d %d ", i, n - i); + } else { + printf("YES\n"); + printf("%d\n", n / 2); + for (int i = 2; i <= n / 2; i += 2) + printf("%d %d ", i, n - i + 1); + printf("\n%d\n", n / 2); + for (int i = 1; i <= n / 2; i += 2) + printf("%d %d ", i, n - i + 1); + } +} |