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

每周编程题（12/4 - 18/4）

时间：2014-05-01

来源：互联网

以下题目几有趣：
http://www.spoj.com/problems/BLOPER/

完成后，建议做较难版本：
http://www.spoj.com/problems/BLOPER2/

我未做到较难版，正在构思中...

遇到困难，请试试睇以下教学网页：
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-01

有趣0.0

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

暴力法

复制内容到剪贴板代码:bool calculate(size_t n, int64_t s, int64_t *a, int8_t *o)
{
int64_t temp = a[0];

for (size_t i = 1; i < n; ++i)
{
switch (o[i - 1])
{
case 0:
temp += a;
break;
case 1:
temp -= a;
break;
case 2:
temp += a << 1;
break;
case 3:
temp -= a << 1;
break;
}
}

return s == temp;
}
void output(size_t n, int8_t *o)
{
--n;

for (size_t i = 0; i < n; ++i)
{
switch (o)
{
case 0:
std::cout << '+';
break;
case 1:
std::cout << '-';
break;
case 2:
std::cout << '.';
break;
case 3:
std::cout << '~';
break;
}
}

}

bool find(size_t n, int64_t s, int64_t *a, int8_t *o)
{

while (!calculate(n, s, a, o))
{
++o[n - 2];
for (size_t i = n - 2; i != 0 && o == 4; --i)
{
o = 0;
++o[i - 1];
}
if (o[0] == 4)
return false;
}

return true;

}

void main()
{
size_t n = 0;
int64_t s = 0, *a;
int8_t *o;

std::cin >> n >> s;
a = new int64_t[n];
o = new int8_t[n - 1];

for (size_t i = 0; i < n; ++i)
std::cin >> a;

for (size_t i = 0; i < n - 1; ++i)
o = 0;

if (find(n, s, a, o))
output(n, o);
else
std::cout << "Impossible";

delete[] a;
delete[] o;

}

[ 本帖最后由 Susan﹏汪汪於 2014-4-12 12:17 AM 编辑 ]

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

引用:原帖由 Susan﹏汪汪於 2014-4-11 11:34 PM 发表
有趣0.0

宣传手法

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

暴力法嘅复杂度系 O(4^(N-1)) = O(4^21) = O(2^42)，相信会 TLE。

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

something like in "pascal triangle "

复制内容到剪贴板代码:level, [possible numbers]

1 [1]
2 [-1, 3]
3 [-4, 2, 0, 6]
4 [-8, 0, -2, 6, -4, 4, 2, 10]
5 [-13, -3, -5, 5, -7, 3, 1, 11, -9, 1, -1, 9, -3, 7, 5, 15]
6 [-19, -7, -9, 3, -11, 1, -1, 11, -13, -1, -3, 9, -5, 7, 5, 17, -15, -3, -5, 7, -7, 5, 3, 15, -9, 3, 1, 13, -1, 11, 9, 21]
7 [-26, -12, -14, 0, -16, -2, -4, 10, -18, -4, -6, 8, -8, 6, 4, 18, -20, -6, -8, 6, -10, 4, 2, 16, -12, 2, 0, 14, -2, 12, 10, 24, -22, -8, -10, 4, -12, 2, 0, 14, -14, 0, -2, 12, -4, 10, 8, 22, -16, -2, -4, 10, -6, 8, 6, 20, -8, 6, 4, 18, 2, 16, 14, 28]
8 [-34, -18, -20, -4, -22, -6, -8, 8, -24, -8, -10, 6, -12, 4, 2, 18, -26, -10, -12, 4, -14, 2, 0, 16, -16, 0, -2, 14, -4, 12, 10, 26, -28, -12, -14, 2, -16, 0, -2, 14, -18, -2, -4, 12, -6, 10, 8, 24, -20, -4, -6, 10, -8, 8, 6, 22, -10, 6, 4, 20, 2, 18, 16, 32, -30, -14, -16, 0, -18, -2, -4, 12, -20, -4, -6, 10, -8, 8, 6, 22, -22, -6, -8, 8, -10, 6, 4, 20, -12, 4, 2, 18, 0, 16, 14, 30, -24, -8, -10, 6, -12, 4, 2, 18, -14, 2, 0, 16, -2, 14, 12, 28, -16, 0, -2, 14, -4, 12, 10, 26, -6, 10, 8, 24, 6, 22, 20, 36]
9 [-43, -25, -27, -9, -29, -11, -13, 5, -31, -13, -15, 3, -17, 1, -1, 17, -33, -15, -17, 1, -19, -1, -3, 15, -21, -3, -5, 13, -7, 11, 9, 27, -35, -17, -19, -1, -21, -3, -5, 13, -23, -5, -7, 11, -9, 9, 7, 25, -25, -7, -9, 9, -11, 7, 5, 23, -13, 5, 3, 21, 1, 19, 17, 35, -37, -19, -21, -3, -23, -5, -7, 11, -25, -7, -9, 9, -11, 7, 5, 23, -27, -9, -11, 7, -13, 5, 3, 21, -15, 3, 1, 19, -1, 17, 15, 33, -29, -11, -13, 5, -15, 3, 1, 19, -17, 1, -1, 17, -3, 15, 13, 31, -19, -1, -3, 15, -5, 13, 11, 29, -7, 11, 9, 27, 7, 25, 23, 41, -39, -21, -23, -5, -25, -7, -9, 9, -27, -9, -11, 7, -13, 5, 3, 21, -29, -11, -13, 5, -15, 3, 1, 19, -17, 1, -1, 17, -3, 15, 13, 31, -31, -13, -15, 3, -17, 1, -1, 17, -19, -1, -3, 15, -5, 13, 11, 29, -21, -3, -5, 13, -7, 11, 9, 27, -9, 9, 7, 25, 5, 23, 21, 39, -33, -15, -17, 1, -19, -1, -3, 15, -21, -3, -5, 13, -7, 11, 9, 27, -23, -5, -7, 11, -9, 9, 7, 25, -11, 7, 5, 23, 3, 21, 19, 37, -25, -7, -9, 9, -11, 7, 5, 23, -13, 5, 3, 21, 1, 19, 17, 35, -15, 3, 1, 19, -1, 17, 15, 33, -3, 15, 13, 31, 11, 29, 27, 45]
...

any number tat found in the "level [possible numbers]" may give the hints to walk in the "pascal triangle"

say, level 3, sum == 6,
it must be 1 -> right(+) -> right(+)
where sum == 0 (LHS of 6) must be 1 -> right(+)->left(-)

[ 本帖最后由 form5 於 2014-4-12 06:24 PM 编辑 ]

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

引用:原帖由 fitcat07 於 2014-4-12 01:18 PM 发表
暴力法嘅复杂度系 O(4^(N-1)) = O(4^21) = O(2^42)，相信会 TLE。

实验的确如此

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

to check impossible numbers, generate the list, it has pattern too, anything not in the list should be "Impossible"

复制内容到剪贴板代码:level [set(possible numbers)]
1 [1]
2 [-1, 3]
3 [-4, 0, 2, 6]
4 [-8, -4, -2, 0, 2, 4, 6, 10]
5 [-13, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 15]
6 [-19, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 21]
7 [-26, -22, -20, -18, -16, -14, -12, -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 28]
8 [-34, -30, -28, -26, -24, -22, -20, -18, -16, -14, -12, -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 36]
9 [-43, -39, -37, -35, -33, -31, -29, -27, -25, -23, -21, -19, -17, -15, -13, -11, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 45]

level 9 => max should be 9*(9+1)/2 = 45, min should be -(45-2), except odd number (43), (-41)

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

引用:原帖由 form5 於 2014-4-12 05:54 PM 发表

something like in "pascal triangle "
level, [possible numbers]

1 [1]
2 [-1, 3]
3 [-4, 2, 0, 6]
4 [-8, 0, -2, 6, -4, 4, 2, 10]
5 [-13, -3, -5, 5, -7, 3, 1, 11, -9, 1, -1, 9, -3, 7, 5 ...

完全唔明白

如果以下test case

复制内容到剪贴板代码:3 5
1 2 3

output可以系

复制内容到剪贴板代码:-.

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

just another wild guess, say level 9 has n numbers, list[0] ... to ... list[n-1]
the max number is the right most in the tree, the second max list[n-1]. number is n/2-1, and so on ...

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

引用:原帖由 form5 於 2014-4-12 07:02 PM 发表

just another wild guess, say level 9 has n numbers, list[0] ... to ... list[n-1]
the max number is the right most in the tree, the second max list[n-1]. number is n/2-1, and so on ...

就系唔多明...

复制内容到剪贴板代码:1 [1]
2 [-1, 3]
3 [-4, 0, 2, 6]

呢个可以点推测到个答案

复制内容到剪贴板代码:3 5
1 2 3

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

引用:原帖由 Susan﹏汪汪於 2014-4-12 06:57 PM 发表
完全唔明白

如果以下test case3 5
1 2 3output可以系-.

http://www.spoj.com/problems/BLOPER/

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

引用:原帖由 form5 於 2014-4-12 07:07 PM 发表

http://www.spoj.com/problems/BLOPER/

咁test case

复制内容到剪贴板代码:3 10
2 3 5

呢？

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

咦？原来第一题咁简单

只要求计算连续数

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

引用:原帖由 Susan﹏汪汪於 2014-4-12 07:05 PM 发表
就系唔多明...
1 [1]
2 [-1, 3]
3 [-4, 0, 2, 6]

呢个可以点推测到个答案3 5
1 2 3

are you talking about question 1?
5 is not in list [-4, 0, 2, 6], that's why it is "Impossible"
1-2-3 = -4
1-2+3 = 2
1+2-3 = 0
1+2+3 = 6

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

引用:原帖由 form5 於 2014-4-12 07:30 PM 发表

are you talking about question 1?
5 is not in list [-4, 0, 2, 6], that's why it is "Impossible"
1-2-3 = -4
1-2+3 = 2
1+2-3 = 0
1+2+3 = 6

一直冇睇清楚Q1

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