SGU 222 - Little Rooks

Description Inspired by a “Little Bishops” problem, Petya now wants to solve problem for rooks. A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move horizontally and vertically from its current position and two rooks attack each other if one is on the path of the other. Given two numbers $n$ and $k$, your job is to determine the number of ways one can put $k$ rooks on an $n\times n$ chessboard so that no two of them are in attacking positions. Input The input file contains two integers $n$ ($1\leq n\leq 10$) and $k$ ($0\leq k\leq n^2$). Output Write index $I$ for given number as the first number in line. Write $I$ super-primes numbers that are items in optimal presentation for given number. Write these $I$ numbers in order of non-increasing. Sample Input 6 Sample Output 2 3 3 Analysis 由于 $K$ 个车每行只能放一个,所以一共有 $K!$ 种情况,一共有 $N\times N$ 的棋盘,行列选择共 $\binom{N}{k}\cdot \binom{N}{k}$ 种情况。因此,通过排列组合,我们有 $$\mathrm{ans} = \binom{N}{k}\cdot \binom{N}{k}\cdot K!$$ 化简可得 $$\mathrm{ans} = \frac{N!}{K!\cdot (N - K)!}\cdot\frac{N!}{(N - K)!}$$ Solution #include <iostream> #include <algorithm> using namespace std; const int MAX = 16; unsigned long long f[MAX]; int main() { f[0]...

2015年3月7日 · 1 分钟 · 344 字 · Kai Wang

SGU 154 - Factorial

Description You task is to find minimal natural number $N$, so that $N!$ contains exactly $Q$ zeroes on the trail in decimal notation. As you know $N! = 1\cdot2\cdots N$. For example, $5! = 120$, 120 contains one zero on the trail. Input One number $Q$ written in the input ($0\leq Q\leq 10^8$). Output Write “No solution”, if there is no such number $N$, and $N$ otherwise. Sample Input 2 Sample Output 10 Analysis 统计 $N!$ 末尾 0 的个数,其实只要看因数 2 和 5 个数的最小值,因为只有 $2\times 5$ 会产生 0。然而实际上因数 2 的个数远大于因数 5 的个数,所以只要看因数 5 的个数。 由于题目给出的空间限制只有 4096KB,所以不能打表,会 MLE。百度题解以后发现可以用二分。 二分的时候统计 1 到 $N$ 这 $N$ 个数中因数 5 的个数,我们采用这样的方法:$$\mathrm{ans} = \left\lfloor\frac{N}{5}\right\rfloor + \left\lfloor\frac{N}{5^2}\right\rfloor + \left\lfloor\frac{N}{5^3}\right\rfloor + \cdots $$ 处理这个...

2015年3月7日 · 2 分钟 · 515 字 · Kai Wang

SGU 130 - Circle

Description On a circle border there are $2k$ different points $A_1, A_2, \cdots , A_{2k}$, located contiguously. These points connect $k$ chords so that each of points $A_1, A_2, \cdots, A_{2k}$ is the end point of one chord. Chords divide the circle into parts. You have to find $N$ - the number of different ways to connect the points so that the circle is broken into minimal possible amount of parts $P$. Input The first line contains the integer $k$ ($1\leq k\leq 30$). Output The first line should contain two numbers $N$ and $P$ delimited by space. Sample Input 2 Sample Output 23 Analysis 我们可以采用分治的方法,固定某个点,从其上引一条弦,将圆分成左右两部分。我们可以将这两部分看成新的圆,那么方案数就是这两个圆的方案数相乘。即:$$f[N] = \sum{\left(f[i - 1] \cdot f[N - i]\right)}$$ 其中 $1\leq i\leq N$。$f[i-1]$ 表示左边的圆,为 $k = i - 1$ 时的情况,$f[N - i]$ 为右边的圆,表示 $k = N - i$ 时的情况。这样,我...

2015年3月7日 · 1 分钟 · 366 字 · Kai Wang

SGU 276 - Andrew's Troubles

Description Famous Berland ACM-ICPC team Anisovka consists of three programmers: Andrew, Michael and Ilya. A long time ago, during the first few months the team was founded, Andrew was very often late to the trainings and contests. To stimulate Andrew to be more punctual, Ilya and Andrew decided to introduce a new rule for team participants. If somebody is late (i.e. comes at least one second after appointed time) he owes a cup of tea to other team members. If he is late for 5 minutes, he owes two cups of tea. If he is late for 15 minutes, he owes three cups of tea. And if he is late for 30 minutes or more, he owes 4 cups of tea. The training starts at the time $S$ (counted in seconds, from some predefined moment of time) and Andrew comes at the time $P$ (also in seconds, counted from the same moment of time). Your task is to find how many cups of tea Andrew owes. Input The input file contains single line with integer numbers $S$ and $P$ ($0\leq S, P\leq 10^4$). Output Write to the output file the number of cups Andrew owes. Sample Input #1 10 10 Sample Output #1 0 Sample Input #2 10 11 Sample Output #2 1 Sample Input #3 0 300 Sample Output #3 Analysis 水题。 Solution #include <iostream> using namespace std; int main() { int S, P; while(cin >> S >> P) { int nDiff = P - S; if(nDiff...

2015年3月7日 · 1 分钟 · 320 字 · Kai Wang

SGU 126 - Boxes

Description There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box ($0 < A + B < 2147483648$). It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box. Input The first line contains two integers $A$ and $B$, delimited by space. Output First line should contain the number $N$ - the number of moves which are required to move all balls into one box, or -1 if it is impossible. Sample Input 2 6 Sample Output 2 Analysis 模拟法 设定一个规定步数(经过反复测试,在给定的数据范围内32步即可满足要求),如果在规定步数内完成任务,则输出步数,否则输出-1。 数学法 首先我们有一个结论 $(x, y)$ 与 $\left(\frac{x}{\mathrm{gcd}(x, y)}, \frac{y}{\mathrm{gcd}(x, y)}\right)$ 具有相同的答案。 证明:我们可以运用整体的思想,将 $\mathrm{gcd}(x, y)$ 个球看成一个球。例如 5 5,我们可以看成 1...

2015年3月7日 · 2 分钟 · 762 字 · Kai Wang

SGU 118 - Digital Root

Description Let $f(n)$ be a sum of digits for positive integer $n$. If $f(n)$ is one-digit number then it is a digital root for $n$ and otherwise digital root of $n$ is equal to digital root of $f(n)$. For example, digital root of 987 is 6. Your task is to find digital root for expression $$ A_1\cdot A_2\cdots A_N + A_1\cdot A_2\cdots A_{N-1} + \cdots + A_1\cdot A_2 + A_1$$ Input Input file consists of few test cases. There is $K$ ($1\leq K\leq 5$) in the first line of input. Each test case is a line. Positive integer number $N$ is written on the first place of test case ($N\leq 1000$). After it there are $N$ positive integer numbers (sequence $A$). Each of this numbers is non-negative and not more than $10^9$. Output Write one line for every test case. On each line write digital root for given expression. Sample Input 1 3 2 3 4 Sample Output 5 Analysis 结论题:$f(n) \equiv n \mod 9$。 证明如下: 令 $$n = a_0 \cdot 10^{p_0} + a_1 \cdot 10_{p_1} + \cdots + a_{m-1} \cdot 10^1 + a_m \cdot 10^0$$ 其中 $n$ 为 $m$ 位数。则 $$n \mod 9 = a_0 + a_1 + \cdots + a_{m-1} + a_m = f(n)$$ 即 $$f(n) \equiv n \mod 9$$ 证毕。 需要注意的是,当 $n \mod 9 = 0$ 的时候,...

2015年2月24日 · 1 分钟 · 422 字 · Kai Wang

SGU 117 - Counting

Description Find amount of numbers for given sequence of integer numbers such that after raising them to the $M$-th power they will be divided by $K$. Input Input consists of two lines. There are three integer numbers $N, M, K$ ($0<N, M, K<10001$) on the first line. There are N positive integer numbers − given sequence (each number is not more than 10001) − on the second line. Output Write answer for given task. Sample Input 4 2 50 9 10 11 12 Sample Output 1 Analysis 快速幂,时间复杂度为 $O(n\log{n})$,应该是可以过的。 要注意用 int 的话会溢出,所以我直接用了 unsigned long long。 这道题目还有一个方法是质因数分解,求出 $M$ 次方以后的各个因数个数(就是把个因子个数乘以 $M$),然后和 $M$ 的个因子的个数比较即可。 Solution 快速幂 #include <iostream> using namespace std; typedef unsigned long long ull; ull Pow(ull x, ull y, ull z); int main() { ull nTmp; int N, M, K; while(cin >> N >> M >> K) { int nCnt = 0; for(int...

2015年2月24日 · 2 分钟 · 505 字 · Kai Wang

SGU 104 - Little shop of flowers

Description You want to arrange the window of your flower shop in a most pleasant way. You have $F$ bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through $V$, where $V$ is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase $V$ is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and $F$. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch $j$ whenever $i < j$. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers. Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic...

2015年2月24日 · 3 分钟 · 1111 字 · Kai Wang

SGU 101 - Domino

Description Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The blocks usually are called bones, dominoes, or pieces and sometimes men, stones, or even cards. The face of each piece is divided, by a line or ridge, into two squares, each of which is marked as would be a pair of dice… The principle in nearly all modern dominoes games is to match one end of a piece to another that is identically or reciprocally numbered. ENCYCLOPÆDIA BRITANNICA Given a set of domino pieces where each side is marked with two digits from 0 to 6. Your task is to arrange pieces in a line such way, that they touch through equal marked sides. It is possible to rotate pieces changing left and right side. Input The first line of the input contains a single integer $N$ ($1\leq N\leq 100$) representing the total number of pieces in the domino set. The following $N$ lines describe pieces. Each piece is represented on a separate line in a form of two digits from 0 to 6 separated by a space. Output Write “No solution””" if it is impossible to arrange them described way. If it is possible, write any of way. Pieces must...

2015年2月22日 · 3 分钟 · 1124 字 · Kai Wang

SGU 347 - Join the Strings

Description His Royal Highness King of Berland Berl XV was a very wise man and had a very accomplished wife, who was aware of the fact, that prominent and outstanding personalities once having written down their names on the pages of glorious History, remain there forever. His Royal Highness King Berl XV experienced an intrinsic, lost nowadays, deep and sincere sense of respect and trust for his beloved spouse. So he decided to acquire a chronicler of his own. Due to the ambiguous nature of misunderstanding and the crying injustice of history to ambiguity, he decided to leave all his royal responsibilities aside and made up his royal mind to find the chronicler, who will make him famous, depicting all his heroic deeds truthfully and gloriously enough. The King assembled the greatest minds of his kingdom at the Academic Chroniclers Meeting (ACM), as he named it, and decided to test their might. The task was to build the Smallest Lexicographical Concatenation (SLC) out of the given $N$ strings. SLC of $N$ strings $s_1,\cdots, s_N$ is the lexicographically smallest their concatenation $s_{i_1} + \cdots + s_{i_N}$, where $ i_1,\cdots, i_N $ is a permutation of integers from 1 through $N$. It’s a great privilege to be a chronicler, so don’t miss your chance and don’t screw it up! Make the king choose you! Input The first line of the input file contains a single integer $N$ ($1\leq N\leq 100$) indicating the number of strings. The following $N$ lines contain $N$ strings,...

2015年2月22日 · 2 分钟 · 646 字 · Kai Wang