Skip to content

Latest commit

 

History

History
386 lines (270 loc) · 12.4 KB

pat.7.2.md

File metadata and controls

386 lines (270 loc) · 12.4 KB
Raw

卡住的键盘 1112 Stucked Keyboard (20 point(s))

在一个损坏的键盘上，某些键总是被卡住。

因此，当你用该键盘输入一些句子时，与这些键相对应的字符将在屏幕上重复出现 $k$ 次。

现在，给定 $k$ 以及最终屏幕显示的结果字符串，请你找出所有可能坏掉的按键，并给出原始字符串。

注意，有些字符可能被重复键入。

每当卡住的按键被按下时，其对应的字符将固定被输出 $k$ 次。

例如，当 $k=3$ 时，从字符串 thiiis iiisss a teeeeeest，我们可以推断出 i 和 e 可能被卡住了，但是 s 并没有被卡住，尽管它也重复出现过。

所以，原始字符串可能是 this isss a teest。

输入格式

第一行包含整数 $k$。

第二行包含屏幕中显示的结果字符串，字符串中只包含 {a-z}, {0-9}, _。

输出格式

按照检测顺序在一行中输出所有可能卡住的按键，每个按键只需输出一次。

第二行输出原始字符串。

数据范围

  • $2 \le k \le 100$,
  • 输入字符串非空且长度不超过 $1000$,
  • 至少包含一个卡住的按键。

输入样例：

3
caseee1__thiiis_iiisss_a_teeeeeest

输出样例：

ei
case1__this_isss_a_teest

1112 Stucked Keyboard (20 point(s))

On a broken keyboard, some of the keys are always stucked. So when you type some sentences, the characters corresponding to those keys will appear repeatedly on screen for k times.

Now given a resulting string on screen, you are supposed to list all the possible stucked keys, and the original string.

Notice that there might be some characters that are typed repeatedly. The stucked key will always repeat output for a fixed k times whenever it is pressed. For example, when k=3, from the string thiiis iiisss a teeeeeest we know that the keys i and e might be stucked, but s is not even though it appears repeatedly sometimes. The original string could be this isss a teest.

Input Specification:

Each input file contains one test case. For each case, the 1st line gives a positive integer $k (1<k≤100)$ which is the output repeating times of a stucked key. The 2nd line contains the resulting string on screen, which consists of no more than 1000 characters from {a-z}, {0-9} and _. It is guaranteed that the string is non-empty.

Output Specification:

For each test case, print in one line the possible stucked keys, in the order of being detected. Make sure that each key is printed once only. Then in the next line print the original string. It is guaranteed that there is at least one stucked key.

#include <iostream>
#include <cstring>

using namespace std;

const int N = 200;

int st[N];

int main()
{
    int k;
    string str;
    cin >> k >> str;

    for (int i = 0; i < str.size(); i ++ )
    {
        int j = i + 1;
        while (j < str.size() && str[j] == str[i]) j ++ ;
        int len = j - i;
        if (len % k) st[str[i]] = 1;  // 1 表示 str[i] 不可能是坏的
        i = j - 1;
    }

    string res;
    for (int i = 0; i < str.size(); i ++ )
    {
        if (!st[str[i]]) cout << str[i], st[str[i]] = 2;  // 2表示可能是坏的，且已经被输出

        if (st[str[i]] == 1) res += str[i];
        else
        {
            res += str[i];
            i += k - 1;  // 坏的，为什么跳 k-1 ？因为后面又 i ++
        }
    }

    cout << endl << res << endl;

    return 0;
}

C 语言竞赛 1116 Come on! Let's C (20 point(s))

C 语言竞赛是浙江大学计算机学院主持的一个欢乐的竞赛。既然竞赛主旨是为了好玩，颁奖规则也就制定得很滑稽：

  • 0、冠军将赢得一份“神秘大奖”（比如很巨大的一本学生研究论文集……）。
  • 1、排名为素数的学生将赢得最好的奖品 —— 小黄人玩偶！
  • 2、其他人将得到巧克力。

给定比赛的最终排名以及一系列参赛者的 ID，你要给出这些参赛者应该获得的奖品。

输入格式

第一行包含整数 $N$，表示参赛者人数。

随后 $N$ 行给出最终排名，每行按排名顺序给出一位参赛者的 ID（$4$ 位数字组成）。

然后一行给出 $K$，表示查询人数。

接下来 $K$ 行，每行给出一个需要查询的 ID。

输出格式

对每个要查询的 ID，在一行中输出 ID: 奖品，其中奖品或者是 Mystery Award（神秘大奖）、或者是 Minion（小黄人）、或者是 Chocolate（巧克力）。

如果所查 ID 根本不在排名里，打印 Are you kidding?（耍我呢？）。如果该 ID 已经查过了（即奖品已经领过了），打印 ID: Checked（不能多吃多占）。

数据范围

$1 \le N,K \le 10^4$,

输入样例：

6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222

输出样例：

8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

1116 Come on! Let's C (20 point(s))

"Let's C" is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following:

  • 0、 The Champion will receive a "Mystery Award" (such as a BIG collection of students' research papers...).
  • 1、 Those who ranked as a prime number will receive the best award -- the Minions (小黄人)!
  • 2、 Everyone else will receive chocolates.

Given the final ranklist and a sequence of contestant ID's, you are supposed to tell the corresponding awards.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (≤10^4)$, the total number of contestants. Then N lines of the ranklist follow, each in order gives a contestant's ID (a 4-digit number). After the ranklist, there is a positive integer K followed by K query ID's.

Output Specification:

For each query, print in a line ID: award where the award is Mystery Award, or Minion, or Chocolate. If the ID is not in the ranklist, print Are you kidding? instead. If the ID has been checked before, print ID: Checked.

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;

int Rank[N];
int st[N];

void init()  // 筛法求质数
{
    for (int i = 2; i < N; i ++ )
        if (!st[i])  // 有没有被筛过
        {
            st[i] = 1;
            for (int j = i * 2; j < N; j += i)  // 把其倍数筛掉
                st[j] = 2;
        }
}

int main()
{
    init();

    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int id;
        cin >> id;
        Rank[id] = i;
    }

    int k;
    cin >> k;
    while (k -- )
    {
        int id;
        cin >> id;

        printf("%04d: ", id);
        if (!Rank[id]) puts("Are you kidding?");
        else if (Rank[id] == -1) puts("Checked");
        else
        {
            int t = st[Rank[id]];
            if (t == 0) puts("Mystery Award");  // 1 的话 st[1] 是 0
            else if (t == 1) puts("Minion");  // 素数
            else puts("Chocolate");

            Rank[id] = -1;  // 别忘了标记
        }
    }

    return 0;
}

谷歌的招聘 1152 Google Recruitment (20 point(s))

$2004$ 年 $7$ 月，谷歌在硅谷的 $101$ 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。

内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 $10$ 位素数，这个素数是自然常数 $e$ 中最早出现的 $10$ 位连续数字。

能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 $e$ 是一个著名的超越数，前面若干位写出来是这样的：

  • e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921...
  • 其中粗体标出的 $10$ 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 $L$ 的数字中，找出最早出现的 $K$ 位连续数字所组成的素数。

输入格式

输入在第一行给出 $2$ 个正整数，分别是 $L$ 和 $K$。

接下来一行给出一个长度为 $L$ 的正整数 $N$。

输出格式

在一行中输出 $N$ 中最早出现的 $K$ 位连续数字所组成的素数。

如果这样的素数不存在，则输出 $404$。

注意，原始数字中的前导零也计算在位数之内。

例如在 $200236$ 中找 $4$ 位素数，$0023$ 算是解；但第一位 $2$ 不能被当成 $0002$ 输出，因为在原始数字中不存在这个 $2$ 的前导零。

数据范围

  • $1 \le L \le 1000$,
  • $1 \le K &lt; 10$

输入样例1：

20 5
23654987725541023819

输出样例1：

49877

输入样例2：

10 3
2468024680

输出样例2：

404

1152 Google Recruitment (20 point(s))

In July 2004, Google posted on a giant billboard along Highway 101 in Silicon Valley (shown in the picture below) for recruitment. The content is super-simple, a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e. The person who could find this prime number could go to the next step in Google's hiring process by visiting this website.

prime.jpg

The natural constant e is a well known transcendental number（超越数）. The first several digits are: e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921...where the 10 digits in bold are the answer to Google's question.

Now you are asked to solve a more general problem: find the first K-digit prime in consecutive digits of any given L-digit number.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: L (≤ 1,000) and K (< 10), which are the numbers of digits of the given number and the prime to be found, respectively. Then the L-digit number N is given in the next line.

Output Specification:

For each test case, print in a line the first K-digit prime in consecutive digits of N. If such a number does not exist, output 404 instead. Note: the leading zeroes must also be counted as part of the K digits. For example, to find the 4-digit prime in 200236, 0023 is a solution. However the first digit 2 must not be treated as a solution 0002 since the leading zeroes are not in the original number.

// 筛法判断质数的方法没法接受（时间限制）
// 因此我们先求 sqrt(N) 个质数，然后用试除法
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 40000;

int n, k;
bool st[M];
int primes[M], cnt;

void init()
{
    for (int i = 2; i < M; i ++ )
        if (!st[i])
        {
            primes[cnt ++ ] = i;  // 筛法求素数
            for (int j = i * 2; j < M; j += i)
                st[j] = true;
        }
}

// 试除法判断是不是质数
bool check(int x)
{
    for (int i = 0; primes[i] <= x / primes[i]; i ++ )
        if (x % primes[i] == 0)  // 是任何一个小于等于sqrt(x)的素数的倍数，则不是素数
            return false;
    return true;
}

int main()
{
    init();

    string str;
    cin >> n >> k >> str;

    for (int i = 0; i + k <= n; i ++ )
    {
        int t = stoi(str.substr(i, k));  // 遍历每个数
        if (check(t))
        {
            cout << str.substr(i, k) << endl;
            return 0;
        }
    }

    puts("404");

    return 0;
}