8、算法练习专栏——牛客练习—-牛客小白月赛88

A：超级闪光牛可乐

链接

题目描述

​           森林中出现了野生的超级闪光牛可乐口牙！
         虽然我们不能为每一位参赛选手提供超级闪光牛可乐，但是……参加小白月赛且有通过题目的选手，第一名，前50名抽1人，51-200名抽2人，201名之后每100人抽1名，赠送牛可乐U型枕！
         img

​           森林中出现了野生的超级闪光牛可乐！想要捕捉它，你至少需要投喂 x 点诱惑力的食物。幸运的是，清楚姐姐在知道了这件事后，非常大气的为你开放了她的豪华零食仓库——仓库里有 n 种不同名称的食物，第 i 种食物能提供 wi点的诱惑力。当你所投喂食物的诱惑力之和不小于 x 时，就可以顺利的捕捉到它。

​           现在，你可以从仓库中取走一些食物了，不管怎么说，今天的目标只有一个，那就是拿下超级闪光牛可乐！

输入描述:

每个测试文件仅有一组测试数据。
第一行输入一个整数 x (1 <= x <= 1000) 表示至少需要多少诱惑力的食物才能捕捉这一只超级闪光牛可乐
第二行输入一个整数 n (1 <= n <= 26) 表示清楚姐姐豪华零食仓库中的零食种类数量。
随后 n 行，每行输入一个小写字母 ch 和一个整数 w (‘a’≤ch ≤ ‘z’, 1 <= w <= 500)
表示第 i 种零食的名称以及提供的诱惑力。保证零食的名称不重复；使用单个空格间隔。

输出描述:

需要在一行上输出一个由小写字母组成的答案字符串，代表你要喂给超级闪光牛可乐的食物。
注意，喂食的零食数量不能超过 1000 个，否则牛可乐会因为吃不下而直接离开。
楚姐姐仓库中没有的零食种类提供的诱惑力会被视为 0 。
果无法捕获牛可乐，仅需输出一行 −1 。

示例1

输入

复制

1
2
3
4
6
2
q 1
c 3

输出

复制

1
cc

说明

在这个样例中，你至少需要 诱惑力的食物才能捕捉这一只超级闪光牛可乐，而一个名称为 c 的零食就可以提供 3 诱惑力，所以你只需要投喂两个 c 。当然，另外一种可行的投喂方式是投喂六个 q 。

示例2

输入

复制

1
2
3
4
5
2
3
q 12
c 20
w 5

输出

复制

1
wida

说明

1
在这个样例中，投喂的食物一共能够提供 5 点诱惑力，足够捕捉这只超级闪光牛可乐。

备注:

1
如果有多个合法答案，你可以输出任意一种。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<char, int> PII;
const int N = 30;
int n, x;
PII a[N];
bool cmp(PII X,PII Y){
    return X.second > Y.second;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> x >> n;
    for (int i = 0; i < n; i++) {
        char c;
        int k;
        cin >> c >> k;
        a[i] = {c, k};
    }
    sort(a, a + n, cmp);
    int kk = x / a[0].second;
    if (kk > 1000) cout << "-1";
    for (int i = 0; i < kk; i++) cout << a[0].first;
    if (x % a[0].second != 0) cout << a[0].first;
    return 0;
}

B：人列计算机

链接

题目描述

人列计算机是一种用人来模拟计算机的逻辑运算的装置，它最早出现在刘慈欣的科幻小说《三体》中。在小说中，冯·诺伊曼向秦始皇介绍了用三千万秦兵组成人列计算机的计划，目的是解决三体问题。
这一计算机的原理其实非常的朴实无华，即使用人来代替电子元件：用黑白旗来代表二进制的 0 和 1 ，用不同的举旗方式来实现与、或、非等基本逻辑运算，从而构成一个巨大的计算系统。
img
现在，让我们来介绍一下什么是门电路。如下图所示， # 号（Ascii：35）代表门电路的轮廓：
在与门电路中，字符 A 与 B 代表输入，井号矩形内部的 & 号（Ascii：38）代表这是一个与门。
在或门电路中，字符 A 与 B 代表输入，井号矩形内部的 >=1 代表这是一个或门。
img

输入描述:

1
2
每个测试文件仅有一组测试数据。
我们保证，A 与 B 的值仅可能为 0 或者 1 ；输入为严格的 5 行 10 列，空白部分均使用空格填充。

输出描述:

1
对于给定的逻辑门图像，输出一个整数代表运算过后的结果。

示例1

输入

复制

1
2
3
4
5
   *****  
1***   *  
   * & ***
1***   *  
   *****

输出

复制

1
1

说明

$$
在这个样例中，我们需要计算 1 和 1 进行与操作运算过后的结果，查阅上方的表格可以很容易的得到，答案为 1。
$$

示例2

输入

复制

1
2
3
4
5
   *****  
0***   *  
   *>=1***
1***   *  
   *****

输出

复制

1
1

​ 示例3

输入

复制

1
2
3
4
5
   *****  
   *   *  
1*** 1 *O*
   *   *  
   *****

输出

复制

1
0

备注:

如果你不熟悉逻辑门的运算原理，那么让我们一起来了解一下。
如果是与门，你需要输出 A 和 B 进行与运算后的结果；如果是或门，你需要输出 A 和 B 进行或运算后的结果；如果是非门，你需要输出 A 进行非运算后的结果，基本的计算方式可以参考下图。如果您需要更多位运算相关的知识，可以参考 OI-Wiki上的相关章节（点击可跳转）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>

using namespace std;
string a[15];
int n,kk;
int b[2];
int main()
{
    int k = 0;
    for (int i = 0; i < 5; i++) {
        getline(cin,a[i]);
    }                
    
    int x, y;
    if (a[1][0] != ' ')
    {
        x = a[1][0] - '0';
        y = a[3][0] - '0';
    } else {
        x = a[2][0] - '0';
    }
    
    if (a[2][5] == '&') {
        cout << (x && y);   
    }
    else if (a[2][5] == '=') {
        cout << (x || y);
    }
    else {
        cout << !x;
    }
    return 0;
}

C：时间管理大师

链接

题目描述

制定合理的日程能够帮助利用好时间进行加训，加训和加训。
新学期开始了，应该好好学习了！凌晨两点整，加睡失败的你在为新一天的各项重要事件制定闹钟。
img

$$

你的手上有一张日程表，上面列出了一些事件发生的时间。你想在每一个日程事件开始前 1, 3 和 5 分钟各设定一个闹钟，
最后，将这些闹钟按照时间先后顺序依次输出（就像你在手机闹钟界面看到的一样）。
注意，如果有多个闹钟被设定在同一时间，那么它们会被视为同一个。
正式地，假设闹钟 a 将在 h_a 时 m_a分响起，闹钟 b 在 h_b 时 m_b 分响起，那么：

  • 如果 h_a<h_b，闹钟 a 先于闹钟 b 响起；
  • 当h_a=h_b 时， 如果m_a<m_b ，闹钟 a 先于闹钟 b 响起；
  • 当 h_a=h_b 时， 如果 m_a=m_b，闹钟 a 和闹钟 b 应当被看作同一个闹钟。

输入描述:

$$
\begin{flalign}
&每个测试文件仅有一组测试数据。\\
&第一行输入一个整数n(1< n < 1000)表示日程的数量。\\
&随后n行，第i行输入两个整数h_i,和m_i(3≤h,≤23,0≤m≤59)表示第i个日程\\
&开始的时分（采用24小时制），数字不包含前导零。注意可能有多个日程事件开始于同一时刻。&\\
\end{flalign}
$$

输出描述:

$$
\begin{flalign}
&第一行输出一个整数m,代表设定的闹钟数量。\\
&随后m行，第i行输出两个由单个空格分隔的整数h_i’和m_i’(0≤h_i≤23,0≤m_i≤59),\\
&代表第i个闹钟在h_i’;时m_i’分响起。数字不应当包含前导零。&\\
\end{flalign}
$$
示例1

输入

复制

1
2
3
2
3 5
3 3

输出

复制

1
2
3
4
5
4
2 58
3 0
3 2
3 4

说明

1
2
3
第一个日程事件开始于 03:05 ，我们需要在 03:00 、03:02 和 03:04 这三个时刻各设置一个闹钟。
第二个日程事件开始于 03:03 ，我们需要在 02:58 、03:00 和 03:02 这三个时刻各设置一个闹钟。
注意到 03:00 和 03:02 这两个时刻都被设置了两个闹钟，需要将它们看成同一个，最终共需设定四个闹钟。

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <set>

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
class Mycompare{
public:
    bool operator()(PII v1, PII v2){//重载运算符
        return v1.first < v2.first || (v1.first == v2.first && v1.second < v2.second);
    }
};
set<PII, Mycompare> p;
int n;


bool cmp(PII X, PII Y) {
    return X.first < Y.first || (X.first == Y.first && X.second < Y.second);
}
int main()
{
    ios::sync_with_stdio(false),cout.tie(0),cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int h, m;
        cin >> h >> m;
        if (m >= 5) {
            int kk = m - 5;
            p.insert({h, kk});
        }
        if (m >= 3) {
            int kk = m - 3;
            p.insert({h, kk});
        }
        if (m >= 1) {
            int kk = m - 1;
            p.insert({h, kk});
        }
        if (m < 5) {
            int xx = h - 1;
            int kk = m - 5 + 60;
            p.insert({xx, kk});
        }
        if (m < 3){
            int xx = h - 1;
            int kk = m - 3 + 60;  
            p.insert({xx, kk});            
        } 
        if (m < 1) {
            int xx = h - 1;
            int kk = m - 1 + 60;
            p.insert({xx, kk});
        }
    }
    cout << p.size() << '\n';
    for (auto item:p) cout << item.first << " " << item.second << '\n';
    
    return 0;
}

D：我不是大富翁

链接

题目描述

提到大富翁游戏！就想到环！！就想到经典的约瑟夫问题！！！作为经典问题，其出彩的展示了数学思维在实际问题中的应用，启发了一代又一代的算竞人。
好了，不要再约瑟夫了，都是经典问题害的你，没法正常的玩大富翁游戏。现在，让我们来愉快的玩大富翁吧！,img

Rabbit\rm\mathcal RabbitRabbit 拿到了一张环形的大富翁地图，地图被平均划分为了 nnn 个地块，地块的编号以 1 为起点，顺时针进行排布。即 111 号地块的顺时针方向依次为 2, 3,… 号地块；111 号地块的逆时针方向依次为 n, n−1\dot 号地块（由于是环形的，所以 111 号地块与 n 号地块相邻，如下图所示）。

​ img

游戏过程如下：系统会给定一个长度为 m 的行动力序列 a_1,a_2,\dots,a_m ，在第 i (1≤i≤m) 回合，Rabbit都需要移动 aia_iai 个地块，但是他可以自由选择移动的方向（换句话说，可以自由选择是向逆时针还是顺时针方向移动 aia_iai 个地块）。
在游戏的开始时，Rabbit 位于 1 号地块，他想知道是否存在这样一种移动方式，使得 m 个回合后他依旧在 1 号地块。

输入描述:

$$
\begin{flalign}
&每个测试文件仅有一组测试数据。\\
&第一行输入两个整数 n 和 m ( 1≤n, m≤5000) 表示地块数量和行动回合数。\\
&第二行输入 m 个整数 a_1,a_2,\dots,a_m (0\le a_i\le 2 \cdot 10^5) 表示行动力序列。&\\
\end{flalign}
$$

输出描述:

$$
\begin{flalign}
&如果 m 个回合后 Rabbit依旧在 1 号地块，则输出 YES ；否则，请输出 NO。\\
&您可以以任何大小写形式输出答案，例如，yEs\ yes\ 和\ YeS\ 视为肯定的回答。& \\
\end{flalign}
$$

示例1

输入

复制

1
2
360 3
120 120 120

输出

复制

1
YES

示例2

输入

复制

1
2
50 5
30 0 10 10 10

输出

复制

1
yES

示例3

输入

复制

1
2
114 5
14 1 9 1 9

输出

复制

1
no

备注:

如果您需要使用 Python 解题，我们建议您在提交时选择 pypy2 或 pypy3 。

思路

菜鸟一个，写个个人代码题解

下面的部分都是本人的个人理解，如果有错误，请大家斧正。
首先，这道题目可以理解为解决这么一个问题：如果我们想让Rabbit的最终位置在1保持不变，那么此时我们这样思考，我们现在假设Rabbit现在已经到达了最终的目的地同时还是1这个位置，也就是保持不动，那么我们可以到达这个位置的条件是什么呢？实际上就是距离你位置1距离为a[m]的位置是否存在上一次跳转的记录（实际上也就是上一次你在进行第m-1次跳转的之后可能到达位置的记录），我来举个例子，就以题目示例1举例子：\

360 3
120 120 120

一开始你的位置就是1，但是为了方便计算，我们实际上可以将这个图变为0~n-1的图像，这个地方应该可以理解到，后面的代码大家就知道为什么需要这样变了。
一开始你在位置0，那么你可以跳到的位置就是 ((0 + 120) % 360) 和 ((0 - 120 % 360) + 360) % 360 两个位置，
那么我们就给这两个位置设置为为1，表示的是我走第一步可以走到的位置,
实际公式： f[(0 + k) % n] = 1,f[((0-k % n) + n) % n] = 1;
那么我们在下一步需要寻找我们可以跳到哪些位置就可以通过枚举0 ~ n - 1的位置，找一下判断一下第1次可以走到的位置，然后将第1次可以走到的位置继续顺时针走一下a[2]，再逆时针走一下a[2]看看可以走到哪些位置，然后将这些位置记录为2,表示这些位置是Rabbit第2次走到的。依次类推，第3次想看看可以跳到哪些位置，就只需要看看第2次我们跳到哪里去了，然后通过第2次跳到的位置找到我们第3次可以跳到的地方，记录=3，下面直接来看下：

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
const int N = 5010;
int f[N][N];
int n, m; 
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    
    // 第1次跳转单独列出来
    int k;
    cin >> k; 
    f[1][k % n] = 1;
    f[1][((-k % n) + n) % n] = 1;
      
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) { // 枚举一下0 ~ n - 1的所有位置
            if (f[i - 1][j] == i - 1) { // 如果当前是第 i - 1 次跳跃的时候到达的位置就更新一下第 i 次跳跃可以跳跃到的位置
                f[i][(((j + x) % n) + n) % n] = i; // 顺时针跳转
                f[i][(((j - x) % n) + n) % n] = i; // 逆时针跳转
            }
        }
    }
    if (f[m][0] == m) cout << "YES"; // 最后就来看一下跳了第 m 次之后是否可以跳到0这个位置，那么也就是f[m][0]会记录=m的情况;
    else cout << "NO"; // 反之则是到不了咯
       
    return 0;
}

这段代码的内存消耗还是蛮大的，我们现在来尝试一下是否可以优化一下空间，将二维转直接变为一维，对于本人的这种写法本人觉得应该是不可以直接转为一维的，因为如果转为一维这里更新的时候就会变成这个样子：\

1
2
3
4
if (f[j] == i - 1) { // 如果当前是第 i - 1 次跳跃的时候到达的位置就更新一下第 i 次跳跃可以跳跃到的位置
                f[(((j + x) % n) + n) % n] = i; // 顺时针跳转
                f[(((j - x) % n) + n) % n] = i; // 逆时针跳转
            }

如此你此时就可能会造成它还没有遍历到的第j个位置的位置f[j] = i,这样就会造成第i - 1次跳跃可能达到情况有损失了，所以这里是不允许直接转换为一维的，但是我们可以通过滚动数组的方式来优化一下。

代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
const int N = 5010;
int f[2][N];
int n, m;
   
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    int k;
    cin >> k;
    f[0][k % n] = 1;
    f[0][((-k % n) + n) % n] = 1;
       
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) {
            if (f[i % 2][j] == i - 1) {
                f[(i + 1) % 2][(((j + x) % n) + n) % n] = i;
                f[(i + 1) % 2][(((j - x) % n) + n) % n] = i;
            }
        }
    }
    if (f[(m + 1) % 2][0] == m) cout << "YES";
    else cout << "NO";
       
    return 0;
}

代码一（二维，200ms or so,98400kb）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
const int N = 5010;
int f[N][N];
int n, m;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    int k;
    cin >> k;
    // 首先单独记录一下第一层的情况
    f[1][(0 + k) % n] = 1; 
    f[1][(((0 - k) % n) + n) % n] = 1; 
    
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) {
            if (f[i - 1][j] == i - 1) {
                f[i][(((j + x) % n) + n) % n] = i;
                f[i][(((j - x) % n) + n) % n] = i;
            }
        }
    }
    if (f[m][0] == m) cout << "YES";
    else cout << "NO";
    
    return 0;
}

代码二（DP + 滚动数组，130ms左右，504kb）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
const int N = 5010;
int f[2][N];
int n, m;
  
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    int k;
    cin >> k;
    f[1][k % n] = 1;
    f[1][((-k % n) + n) % n] = 1;
      
    for (int i = 2; i <= m; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < n; j++) {
            if (f[(i + 1) % 2][j] == i - 1) {
                f[i % 2][(j + x) % n] = i;
                f[i % 2][(((j - x) % n) + n) % n] = i;
            }
        }
    }
    if (f[m % 2][0] == m) cout << "YES";
    else cout << "NO";
      
    return 0;
}

E：多重映射

链接

题目描述

​     在书写代码时，我们时常会使用到批量查找替换的功能。现在，我们需要对一些数字进行类似的操作。
         （本题没有题图，因为说话的人在映射后丢失了！）
         img

$$
\begin{flalign}
&已知一个由数字构成的序列 A ，不妨定义一个函数 M(x)=y 表示将序列 A 中全部的数字 x 都替换为 y 。例如 &A={ 2,2,4,5,1,4} \\
&执行一次 M(2)=1 操作后，序列变为 A′={1,1,4,5,1,4} ，很神奇吧！\\
&这样的替换显然是能够进行反复叠加的，\\
&举例说明，对于上方操作过后的 A′再执行一次 M(1)=2 操作，序列会变为 A′′={2,2,4,5,2,4} 。\\
&现在，给出若干个这样的操作，请你输出修改过后的序列。& \\
\end{flalign}
$$

输入描述:

$$
\begin{flalign}
&每个测试文件均包含多个测试点。第一行输入一个整数 T (1≤T≤10^5) 代表测试数据组数，每组测试数据描述如下：\\
&第一行输入两个整数 n 和 m (1≤n,m≤10^5) 表示序列长度和操作数量。\\
&第二行输入 n 个整数 a_1,a_2,…,a_n(1≤a_i≤10^6) 表示给定的序列。\\
&此后 m 行，第 i 行输入两个整数 x_i 和 y_i (1≤x_i,y_i\le10^6) 表示一个操作。\\
&保证所有测试用例的 n 之和不会超过 2⋅10^5 ，m 之和不会超过 2⋅10^5。&
\end{flalign}
$$

输出描述:

1
对于每组数据，你都需要在一行上输出 n 个整数，代表执行操作后的序列，数字彼此间通过单个空格间隔。

示例1

输入

复制

1
2
3
4
5
6
7
8
2
6 1
2 2 4 5 1 4
2 1
6 2
2 2 4 5 1 4
2 1
1 6

输出

复制

1
2
1 1 4 5 1 4
6 6 4 5 6 4

说明

1
该样例已经在题干中加以解释。

示例2

输入

复制

1
2
3
4
5
6
7
8
1
3 5
20 17 18
8 16
15 1
20 2
20 1
15 1

输出

复制

1
2 17 18

备注:

1

代码（并查集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e6 + 10;
int a[N],p[N], l[N], r[N];
int T,n, m;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            p[a[i]] = a[i];
        }
        
        for (int i = 1; i <= m; i++) {
            cin >> l[i] >> r[i];
            p[l[i]] = l[i];
            p[r[i]] = r[i];
        }
        
        for (int i = m; i >= 0; --i) {
            p[l[i]] = p[r[i]];
        }
        for (int i = 1; i <= n; i++) {
            a[i] = p[a[i]];
            cout << a[i]<< " ";
        }
        cout << '\n';
    }
    
    
    
    return 0;
}

F：现在是消消乐时间

链接

题目描述

​           方块消除游戏是一种益智类的游戏，它的玩法是通过射出小球来消除屏幕上的方块，小球在移动过程中会碰撞并消除所遇到的方块，当遇到墙壁时则会反弹。
         img

          现在，我们有一个简化版本的方块消除游戏，它的具体规则描述如下：

  • 整个游戏在一个 n 行 m 列的矩形中进行。矩形的底部 d 行 m 列为空白单元格，其余位置放置着可被消除的方块，每个方块占据一个单元格，方块的中心点和单元格的中心点重合；
  • 矩形底部空白区域中 d+1 条横线与竖线相交形成的 (d+1)×(m+1) 个交点为合法的小球发射地点，你可以在这些交点中任选一个作为发射地点，随后，从左上 45^∘^ 、右上 45^∘^ 、左下 45^∘^ 、右下 45^∘^ 这四个方向中选择一个方向射出小球；
  • 小球在移动过程中会沿着射出的方向运行，当其碰到任意一个方块的中心时，会将其消除；当其碰到墙壁后，会发生反弹。

          我们进一步的规定这里的反弹所代表的含义：

  • 如果小球射向矩形的四个角，那么游戏直接结束；
  • 否则，如果小球碰到矩形左侧或右侧边缘，那么小球的水平方向（x轴）的速度会变为相反数，垂直方向（y轴）的速度不变，即小球的运动方向会沿着垂直于墙壁的方向反射；
  • 如果小球碰到矩形上方或下方边缘，那么小球的垂直方向（y轴）的速度会变为相反数，水平方向（x轴）的速度不变，即小球的运动方向会沿着水平于墙壁的方向反射。

现在， Salt 想要知道，是否存在这样一个发射地点，使得小球射出后能够消除全部的方块。

输入描述:

1
2
          每个测试文件仅有一组测试数据。
          第一行输入三个整数 n, m 和 d (1≤n, m≤2000, 0≤d≤n0) 表示游戏矩形网格的行数、列数以及空白占据的行数。

输出描述:

$$
\begin{flalign}
&如果存在这样的发射地点，首先输出一行 \rm YES ，接下来在第二行输出两个整数 x 和 y (0 \le x \le d, 0≤y≤m) \\
&表示发射地点所在的横线编号与竖线编号，在第三行输出小球的发射方向：\\
&如果向左上 45^{\circ} 方向射出小球，输出 \rm {UL} ；\\
&如果向右上 45^{\circ} 方向射出小球，输出 \rm {UR} ；\\
&如果向左下 45^{\circ} 方向射出小球，输出 \rm{DL} ；\\
&如果向右下 45^{\circ} 方向射出小球，输出 \rm{DR} 。\\
&如果不存在这样的发射地点，仅需输出一行 \rm {NO} 。你可以以任何大小写形式输出答案。& \\
\end{flalign}
$$

示例1

输入

复制

1
6 3 0

输出

复制

1
NO

说明

1
    在第一个样例中，我们一共有 16 种不同的发射情况，如下图所示（其中蓝色箭头代表发射方向）。由于这 16 种情况均无法一次性消除全部的方块，故我们输出 NO 。

示例2

输入

复制

1
6 4 2

输出

复制

1
2
3
YeS
1 2
uL

说明

1
在第二个样例中，存在多种发射方式使得小球能够一次性消除全部方块，我们在此仅展示其中一种。

备注:

1
如果有多种合法答案，你可以输出任意一种。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
n,***p(int,input().strip().split())
D *= 2

# 角落
corner = set()
corner.add((0,0))
corner.add((0,m))
corner.add((n,0))
corner.add((n,m))

# 起点，偏移量
def getRes(start,xc,yc):
    x,y = start
    t = 0
    while True:
        # 走到撞墙为止
        while 0 <= x+xc <= n and 0 <= y+yc <= m:
            nx,ny = x+xc,y+yc
            if x+nx >= D:
                t += 1
            x,y = nx,ny
        
        # 撞墙转向
        if not y:
            yc *= -1
        elif not x:
            xc *= -1
        elif y == m:
            yc *= -1
        else:
            xc *= -1
        
        # 去到角落 或者 回到起点
        if (x,y) in corner or (x,y) == start:
            return t == m * (n-D//2)


if getRes((0,0),1,1):
    print("YES")
    print(0,0)
    print("UR")
elif getRes((0,1),1,1):
    print("YES")
    print(0,1)
    print("UR")
else:
    print("NO")