当前位置：首页 → 问答吧 → 每周编程题（19/4 - 25/4）

每周编程题（19/4 - 25/4）

时间：2014-05-18

来源：互联网

复活节快乐！

搵到一题好浅（如果你明白条题目）：
http://www.spoj.com/problems/KIT/

我就睇唔明，系有人喺 SPOJ 论坛讲解先知道想点。
估就估到，但斋睇题目真系唔知讲乜，可能系我英文水皮。

请大家唔好睇评论同论坛相关帖子，睇下明唔明。

另外，想请教以下呢题：http://www.spoj.com/problems/INS14D/

遇到困难，请试试睇以下教学网页：http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static
亦欢迎发问。

常用 SPOJ 题术语解释：
AC - 代表 Accepted，表示答案符合要求，已被接受。
WA - 代表 Wrong Answer，表示答案出错。
TLE - 代表 Time Limited Exceeded，表示超出时间限制。

作者: fitcat07 发布时间: 2014-05-18

呢题超简单

只系做维吉尼亚密码...或者移位式密码

即系

复制内容到剪贴板代码:Input 1:
10
1 2 3 4 5 4 3 2 1 0
aa aaa
zzzzz
-1

Output 1:
bc
def
dcbaz

首先就系得到一串字符"aaaaazzzzz"(断行在这里忽略)
然后使用密码加密
即

复制内容到剪贴板代码:'a' + 1 = 'b'
'a' + 2 = 'c'
'a' + 3 = 'd'
'a' + 4 = 'e'
'a' + 5 = 'f'
'z' + 4 = 'd'
'z' + 3 = 'c'
'z' + 2 = 'b'
'z' + 1 = 'a'
'z' + 0 = 'z'

作者: Susan﹏汪汪发布时间: 2014-05-18

攞到AC

复制内容到剪贴板代码:#include <iostream>
#include <string>
using namespace std;

int main() {
// your code goes here

int n = 0;
cin >> n;

int *pad = new int[n];
for(int i = 0; i < n; ++i)
{
cin >> pad[i];
}

int shift = 0;
char chr;
bool jump = true;
while(cin.get(chr))
{
if(chr == '-')
{
cin >> chr;
if(chr == '1')
{
break;
}
}
if(chr < 'a' || chr > 'z')
{
if(!jump) cout << endl;
jump = true;
continue;
}
jump = false;

char temp = (((chr - 'a') + pad[shift++]) % 26) + 'a';
shift %= n;
cout << temp;
}

delete[] pad;

return 0;
}

作者: Susan﹏汪汪发布时间: 2014-05-18

做得好！

我读到呢句，畀佢混乱咗我：

引用:The message he wants to send can be encrypted if each character in the string is encoded by a number from the pad provided each number from the number- pad is only used once.

呢句话「can be ... if ...」，即系话情况许可，就做到加密。咁情况唔许可呢？冇讲到喎。

重有，我睇过不下五次，都睇唔到有话顺序由第一个 number-pad 嘅数字开始，直到尾，然后返回第一个数字。
都系嗰句，估就估到，理解不能。唯有承认英文差...

作者: fitcat07 发布时间: 2014-05-18

引用:原帖由 fitcat07 於 2014-4-19 01:29 PM 发表
做得好！

我读到呢句，畀佢混乱咗我：

呢句话「can be ... if ...」，即系话情况许可，就做到加密。咁情况唔许可呢？冇讲到喎。

重有，我睇过不下五次，都睇唔到有话顺序由第一个 number-p ...

果句只系英文写法问题...无咩特别意思

作者: Susan﹏汪汪发布时间: 2014-05-18

第二题...Digo Needs Guns

汪汪随便写左个...居然用左好多时间去跑三个test...然后TLE

但如果佢冇一开始就拋出WA...即系话答案应该啱

复制内容到剪贴板代码:#include <iostream>
using namespace std;

int main() {
// your code goes here

uint32_t n, t;

cin >> n;

for(uint32_t i = 0; i < n; ++i)
{
cin >> t;
cout << (t / 5 + (t % 5 ? 1 : 0)) << endl;
}

return 0;
}

作者: Susan﹏汪汪发布时间: 2014-05-18

第三个test终於攞到WA

作者: Susan﹏汪汪发布时间: 2014-05-18

引用:原帖由 Susan﹏汪汪於 2014-4-19 01:34 PM 发表
果句只系英文写法问题...无咩特别意思

咁，点解唔系由右至左？

作者: fitcat07 发布时间: 2014-05-18

引用:原帖由 Susan﹏汪汪於 2014-4-19 02:02 PM 发表
第三个test终於攞到WA

数据量太多，用 cin 会比 scanf 慢得多，因此 TLE。

原来自己搞错咗一尐嘢，现在已经 AC

作者: fitcat07 发布时间: 2014-05-18

引用:原帖由 fitcat07 於 2014-4-19 04:14 PM 发表
数据量太多，用 cin 会比 scanf 慢得多，因此 TLE。

原来自己搞错咗一尐嘢，现在已经 AC

攞到WA
应该有special case

作者: Susan﹏汪汪发布时间: 2014-05-18

引用:原帖由 Susan﹏汪汪於 2014-4-19 06:34 PM 发表
攞到WA
应该有special case

我嘅答案无须处理特别案例。
唔想剧透，我将文字反白了。

作者: fitcat07 发布时间: 2014-05-18

引用:原帖由 Susan﹏汪汪於 2014-4-19 01:44 PM 发表
第二题...Digo Needs Guns

汪汪随便写左个...居然用左好多时间去跑三个test...然后TLE

但如果佢冇一开始就拋出WA...即系话答案应该啱#include
using namespace std;

int main() {
// your code g ...

Hi susan,就这么简单，以下这个九边形，需要 4 伎 gun? 但

(9 / 5 + (9 % 5 ? 1 : 0)) = 1

作者: assembly.jc 发布时间: 2014-05-18

I don't understand the second question, what is that gun for? how to get result 1? Anyone can explain that?

作者: form5 发布时间: 2014-05-18

引用:原帖由 assembly.jc 於 2014-4-20 12:34 AM 发表
Hi susan,就这么简单，以下这个九边形，需要 4 伎 gun? 但

(9 / 5 + (9 % 5 ? 1 : 0)) = 1

https://lh4.googleusercontent.com/-riQpfdCxc3c/U1Kj-IbBm8I/AAAAAAAAAFs/zH-vDqaMRUk/w669-h437-no/ploygon.png

9 / 5 + (9 % 5 ? 1 : 0)
= 1 + (4 ? 1 : 0)
= 1 + 1
= 2

作者: Susan﹏汪汪发布时间: 2014-05-18

引用:原帖由 form5 於 2014-4-20 12:37 AM 发表
I don't understand the second question, what is that gun for? how to get result 1? Anyone can explain that?

A gun can be placed only at the intersections of two walls.We are asked to find the minimum number of guns needed to cover the whole room.
By means of "cover", any positions of the room can be reached by bullets from at least one gun.

Consider the example from assembly.jc:

There are nine intersections from all the nine walls, namely A - I.
If we only place only one gun at intersection A, its bullets can't reach areas near intersections C, D, E and F.
If we place a gun at A, B, C and D, the whole room can be covered.
But the question is, can we place less than 4 guns to do this?
What is the minimum number of guns required?
Remember, we don't know the shape of the room in advance - just the number of walls and the rooms are polygons.

作者: fitcat07 发布时间: 2014-05-18

引用:原帖由 Susan﹏汪汪於 2014-4-20 01:59 AM 发表

9 / 5 + (9 % 5 ? 1 : 0)
= 1 + (4 ? 1 : 0)
= 1 + 1
= 2

Hi susan,

哈, 唔好意思，计错算

。以下这个十三边形，2 支 gun 就够了 (say, A and B) ? 但
13 / 5 + (13 % 5 ? 1 : 0) = 3