## REFLECTIONS

2015年2月6日 · 2 分钟 · 934 字 · Kai Wang

## ACM-ICPC 寒假练习 01

2015年2月6日 · 4 分钟 · 1599 字 · Kai Wang

## SGU 127 - Telephone directory

Description CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then $K$ lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing $N$ records, but since the information is confidential, without the phones locations. Input The first line contains a natural number $K$ ($0 < K < 255$) - the maximum number of lines that one page can contain. The second line contains a natural $N$ ($0 < N < 8000$) - number of phone numbers supplied. Each of following $N$ lines contains a number consisting of 4 digits - phone numbers in any order, and it is known, that numbers in this list cannot repeat. Output First line should contain a natural number $P$ - the number of pages in the telephone directory. Sample Input 5...

2015年2月5日 · 2 分钟 · 538 字 · Kai Wang

## SGU 112 - a^b - b^a

Description You are given natural numbers $a$ and $b$. Find $a^b - b^a$. Input Input contains numbers $a$ and $b$ ($1\leq a,b\leq 100$). Output Write answer to output. Sample Input 2 3 Sample Output -1 Analysis 非常明显的高精度，再观察一下样例，要处理减法，而且有负数，注意一下好了。 Solution #include <iostream> #include <memory.h> using namespace std; const int MAX = 1024; const int HEX = 10000; const int BIT = 4; class Huge { public: Huge(); Huge(int x); ~Huge(); public: Huge& operator *= (int x); Huge& operator - (Huge &x); bool operator > (Huge x); public: friend ostream& operator << (ostream &out, Huge &x); public: int m_pData[MAX]; int m_nLen; }; Huge::Huge() { memset(m_pData, 0, sizeof(m_pData)); m_nLen = 1; } Huge::Huge(int x) { memset(m_pData, 0, sizeof(m_pData)); m_pData[1] = x; m_nLen = 1; } Huge::~Huge() { } bool Huge::operator > (Huge x) { if(this->m_nLen != x.m_nLen) { return this->m_nLen > x.m_nLen; } else { for(int i = this->m_nLen; i >= 1; i--) { if(this->m_pData[i] != x.m_pData[i]) { return this->m_pData[i] > x.m_pData[i]; } } } return true; } Huge& Huge::operator *= (int x) { for(int i = 1; i <= this->m_nLen; i++) { this->m_pData[i] *= x; } for(int i = 1; i <= this->m_nLen; i++) { this->m_pData[i + 1] += this->m_pData[i] / HEX; this->m_pData[i] %= HEX; } while(this->m_pData[this->m_nLen + 1]) { this->m_nLen++; } return *this; } Huge& Huge::operator -...

2015年2月5日 · 1 分钟 · 460 字 · Kai Wang

## SGU 113 - Nearly prime numbers

Description Nearly prime number is an integer positive number for which it is possible to find such primes $P_1$ and $P_2$ that given number is equal to $P_1\cdot P_2$. There is given a sequence on $N$ integer positive numbers, you are to write a program that prints “Yes” if given number is nearly prime and “No” otherwise. Input Input file consists of $N + 1$ numbers. First is positive integer $N$ ($1\leq N\leq 10$). Next $N$ numbers followed by $N$. Each number is not greater than $10^9$. All numbers separated by whitespace(s). Output Write a line in output file for each number of given sequence. Write “Yes” in it if given number is nearly prime and “No” in other case. Sample Input 1 6 Sample Output Yes Analysis 考虑到数据范围不是很大，$10^9$ 以内仅有五千多万个质数，可以通过打表来解决。打表自然是筛法求素数。 每次读入数据以后，只要比较到 $\sqrt{X}$ 就可以了，这样我们就可以在 $O\left(\sqrt{n}\right)$ 的时间内求出结果。 这里有个小小的注意点，我们在循环的时候，最好使用 i * i <= X 来代替 i...

2015年2月5日 · 1 分钟 · 479 字 · Kai Wang

## SGU 107 - 987654321 problem

Description For given number $N$ you must output amount of $N$-digit numbers, such, that last digits of their square is equal to 987654321. Input Input contains integer number $N$ ($1\leq N\leq 10^6$). Output Write answer in output file. Sample Input 8 Sample Output 0 Analysis 在一定意义上，这也是一道数学题。 由于一个数平方的后X位，只与这个数字的后X位有关系，所以我们不妨使用下面的程序打一个表来看一下。 #include <iostream> using namespace std; int main() { // sqrt(987654321) > 30000 for(long long i = 30000; i <= 999999999; i++) { long long x = i * i; if(x % 1000000000 == 987654321) { cout << i << " "; } } return 0; } 打完表以后，我们发现只有 8 个数字满足条件，而且分布在 100,000,000 到 999,999,999 之间。 下面我们来推导满足题目条件的答案与输入的位数 $N$ 的关系：$$\mathrm{ans} = \begin{cases}0, & N \leq 8\\ 8, & N = 9\\ 72\times 10^{N - 10}, & N \geq 10\end{cases}$$ 最后一...

2015年2月5日 · 2 分钟 · 510 字 · Kai Wang

Description Petya is well-known with his famous cabbage patties. Petya’s birthday will come very soon, and he wants to invite as many guests as possible. But the boy wants everybody to try his specialty of the house. That’s why he needs to know the number of the patties he can cook using the stocked ingredients. Petya has $P$ grams of flour, $M$ milliliters of milk and $C$ grams of cabbage. He has plenty of other ingredients. Petya knows that he needs $K$ grams of flour, $R$ milliliters of milk and $V$ grams of cabbage to cook one patty. Please, help Petya calculate the maximum number of patties he can cook. Input The input file contains integer numbers $P$, $M$, $C$, $K$, $R$ and $V$, separated by spaces and/or line breaks ($1 \leq P, M, C, K, R, V \leq 10000$). Output Output the maximum number of patties Petya can cook. Sample Input 3000 1000 500 30 15 60 Sample Output 8 Analysis 简单的数学分析就知道，所求答案为 $\left\lfloor\frac{P}{K}\right\rfloor$，$\left\lfloor\frac{M}{R}\right\rf... 2015年1月30日 · 1 分钟 · 483 字 · Kai Wang ## SGU 135 - Drawing Lines Description Little Johnny likes to draw a lot. A few days ago he painted lots of straight lines on his sheet of paper. Then he counted in how many zones the sheet of paper was split by these lines. He noticed that this number is not always the same. For instance, if he draws 2 lines, the sheet of paper could be split into 4, 3 or even 2 (if the lines are identical) zones. Since he is a very curious kid, he would like to know which is the maximum number of zones into which he can split the sheet of paper, if he draws$N$lines. The sheet of paper is to be considered a very large (=infinite) rectangle. Input The input file will contain an integer number:$N$($0\leq N\leq 65535$). Output You should output one integer: the maximum number of zones into which the sheet of paper can be split if Johnny draws$N$lines. Sample Input #1 0 Sample Output #1 1 Sample Input #2 1 Sample Output #2 2 Analysis 数学题。直线分平面数，我们也可以通过找规律的方法来求出它的公式： 线段数$N$平面数$M$0 1 1 1 + 1 = 2 2 2 + 2 = 4 3 4 + 3 = 7 4 7 + 4 = 11 5 11 + 5 = 16 6 16... 2015年1月29日 · 1 分钟 · 397 字 · Kai Wang ## SGU 115 - Calendar Description First year of new millenium is gone away. In commemoration of it write a program that finds the name of the day of the week for any date in 2001. Input Input is a line with two positive integer numbers$N$and$M$, where$N$is a day number in month$M$.$N$and$M$is not more than 100. Output Write current number of the day of the week for given date (Monday – number 1, … , Sunday – number 7) or phrase “Impossible” if such date does not exist. Sample Input 21 10 Sample Output 7 Analysis 翻看日历，我们可以知道 2001 年 1 月 1 日为星期一。 这样，我们只需要计算输入的日期为该年中的第几天就行了。 当然，要记得判断输入的日期是否合法。 Solution #include <iostream> using namespace std; const int pDay[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int main() { int N, M, ans = 0; cin >> N >> M; if((M > 12 || N > 31) || (M == 4 || M == 6 || M == 9 || M == 11) && N > 30 || M == 2 && N > 28) { cout << "Impossible" << endl; } else... 2015年1月29日 · 1 分钟 · 286 字 · Kai Wang ## SGU 123 - The Sum Description The Fibonacci sequence of numbers is known:$F_1 = 1$;$F_2 = 1$;$F_{n+1} = F_n + F_{n-1}$, for$n>1$. You have to find$S$- the sum of the first$K$Fibonacci numbers. Input First line contains natural number$K$($0<K<41$). Output First line should contain number$S$. Sample Input 5 Sample Output 12 Analysis 考虑到数据范围，这道题目只要模拟一下就行了。但是我还是比较喜欢使用数学方法来求解。 令$S_n$表示斐波那契数列的前$N$项和，那么我们很容易求得$S_n = F_{n+2} - 1$。 Solution #include <iostream> using namespace std; const int MAX = 64; int f[MAX]; int main() { int N; cin >> N; f[1] = f[2] = 1; for(int i = 3; i <= N + 2; i++) { f[i] = f[i - 1] + f[i - 2]; } cout << f[N + 2] - 1 << endl; return 0; } 这道题目应该是非常简单的。当然，如果你不知道斐波那契数列可以在$O(n)\$时间内求得，那么这道题目对于你来说还是有一定难度...

2015年1月29日 · 1 分钟 · 252 字 · Kai Wang