编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:   Password: 
 登记登记   
 dwite.圆#1解决方案/分析
指数 -> Compsci.ca,比赛 -> dwite.
查看上一个主题 可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题
作者 信息
A.J.




邮政发布: 星期五2011年10月28日11:23 PM  帖子主题:DWITE圆#1解决方案/分析

代码:
欢迎回到每个人的Dwite。首先,我想欢迎Cyril进入我们的Dwite Dev团队(感谢您帮助我们。希望你不要太无聊:P).

这一轮相当好。关于#5有一个小问题我们忘了澄清像“TAT”这样的话,因为't'不等于't'而不是回文。

此外,一如既往地,随时对比赛的难度/风格进行评论,并谈论您自己的解决方案。

分析:

#1)这是一个相当直接的前锋问题,涉及逆转字符串。一个人应该小心数字与其他字母连接的情况(like '123cba'),在这里,数字确实会被反转,因为它们是一个单词的一部分并且不表示数字。

#2)由于我们始终可以将n堆栈划分为相等尺寸的堆栈,首先确定每个堆栈的最终数量是什么。让C_1,C_2,...,C_N表示N堆叠中的硬币数量,并且让F在制作所有移动后表示堆叠中的硬币数量。然后f =(C_1 + C_2 + ... + C_N)/ n,这总是一个整数。最后,我们计算每个堆栈应该转移到每个堆栈的硬币最终应该达到多少钱: abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N)。然而,这种双倍计数所做的移动次数,因为正在移动的每个硬币被占据一次,因为它被移动到的桩,其被移动到的堆。因此,我们将值划分为2以获得所需的移动数量: [ abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N) ] / 2

#3)希望你们在这个问题上有很多乐趣,因为我写了它。考虑以下子问题:给定线段ab,有一个(ax, ay) and B(bx, by), and a point C(cx, cy),距离c到ab的最短距离是多少?如果您可以回答这个问题,那么您必须做的就是一段时间浏览Path Billy拍摄了一条线段,在您离开时将距离CandyStore的最小距离存储到每个段。考虑以下:
 
                             l1       l2
                          |   |        |   
                    (1) C |   |        | (2) C
                         \|   | (3) C  |    /
                          \   |        |   /
                          |\  |        |  /
                          | \ |        | /
                          |  \|        |/
       ----------------------------
                          |
                          |
                          |
                          |
                          |
                          |

有3例(as shown above):
1)角度驾驶室是钝的(i.e. > 90 degrees)在这种情况下,CA是从C到AB的最短距离
2)角度cba是钝的(i.e. > 90 degrees)其中cb是从c到ab的最短距离
3)C在垂直于AB和通过A和B垂直的两条线之间(i.e. l1 and l2)。这种情况是需要一些数学的情况。
考虑以下案例3:

                                       
                          |             
                          |           
                          |        C        C'
                          |       /--------/
                          |      /        /
                          |     /        /
                          |    /        /
       ----------------------------
                          |
                          |
                          |
                          |
                          |
                          |
通过绘制与AB平行的C线,通过A,B和C进行平行四通(让我们打电话给第四个角C')。然后请注意,从C到AB的最短距离是平行四边形ABCC的高度。由于我们知道平行四边形的区域是基地*高度,因此我们得到了:

   (距离c到ab的最短距离) * (Base of ABCC') = Area of ABCC'
<=>距离c到ab =的最短距离(Area of ABCC')/AB (由于AB是ABCC的基础)

ABCC'的区域可以通过乘矢量CA和AB的横向产品或换句话说来计算:

区域abcc'= |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|

因此案例3),从C到AB的最短距离是:

|(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|       |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|
---------- - ---------------------------------   =   ------------------------------------------
                   AB                                    sqrt((by - ay)^2 + (bx - ax)^2)

#4)我想向那些寻求“非野蛮人”解决方案的团队道歉,并没有最终解决它。我意识到试验箱如此之小,让你的福雷斯曾经工作过,所以我为此道歉(这个问题旨在比这更难)。所以我将在此说明非BruteForce解决方案。让n_ {d},n_ {d-1},...,n_0是从左到右输入n的小数位(这是n = n_ {d} * 10 ^ d + ... + n_0 * 10 ^ 0)。一般想法是,当计算0到N时,我们将计算这些数字中的每一位数为0的次数。让z.(x)表示从0到n计数时xth数字为0的次数。如果n_ {x}(即n的xth数字) is not a 0, then z(x)= 10 ^ x * a,其中a是通过从n_ {d},n_ {d-1},...,n_ {x + 1}通过数字形成的数字。(即,通过删除n的最后x数字来形成的数字)。如果n_ {x} = 0,则z(x) = 10^x*(a-1)+ B + 1,其中a如前所述,b是通过仅采用n的最后x数字形成的数字。然后,您添加所有这些计数,然后添加1个以计算数字0,以获取数字从0到n计数时数字转向0的总次数: z(0) + z(1) + ... + z(d)+ 1。我知道这是令人困惑的,所以这里是说明这个想法的一个例子:

让我们采取n = 2034.我们知道在从0到n计数时每个数字每个数字是0的数量:

z(0) (or unit's digit):单位数字为0的次数为10 ^ 0 * 203 = 203.本机的数字为0,在10,20,30,40,...,2020,2030(所以你注意到这就像从1到203的计数忽略了单位的数字).

z(1) (or ten's digit):十个数字为0的次数为10 ^ 1 * 20 = 200.十个数字是0 10次(100,200,300,...,1900,2000),对于这些时间,单位的数字可以是0到9的任何东西(这就是10 ^ 1部分等式的地方来自哪里).

z(2) (or hundred's digit):现在,由于百百名的数字是0,我们得到它是0 10 ^ 2 *(2 - 1)+ 34 + 1 = 135次。首先,我们计算数百位数是0的次数,其中一个数字为0< 2 (这只是10 ^ 2 *(2 - 1)= 100,这是1000,1001,1002,1003,...,1099),然后我们计算百家数字的次数为0,第一个数字2(这只是34 + 1,+ 1是为了占2000年,而其他人是2001年,2002年,......,2034).

z(3) (the thousand's digit): This is just 10^3*(0)= 0.这是有道理的,因为最重要的数字永远不会是0。

从0到2034计数时,0的遇到数量为= z(0) + z(1) + z(2) + z(3)= 203 + 200 + 135 + 0 + 1 = 538 + 1 = 539

这是很快的运行,因为它的时间复杂性是o(n*d),其中d是数字的平均数字的数字,最多为n。

#5) There are two ways you can solve this question. One solution is to take the longest common subsequence (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) of the given word and its reverse. The other solution is to try answering a subproblem instead:
通过从第i字母到给定的词的第j个字母来看,通过从一封信中删除任何数量的字母来形成最长的回文。让最长[i] [j]表示这个值。我们现在将在案件中脱颖而出:

1) i = j
2) i给定词的信= j给定词的信
3)我是给定词的信  != j给定词的信

情况1 :在这种情况下,我们正在处理一个刻字字,显然是最长的[i] [j] = 1(随着任何一个刻字的是一个回文,我们不必删除任何东西来形成一个parindrome).

案例#2:如果是这种情况,那么我们知道最长的Parindrome始于第i个字母,并以J TH字母结束。因此,问题归结为通过从通过从中形成的单词中删除任何数量的字母来找到最长的回文的长度。(i+1) th letter to the (j-1)给定词的信(即最长[i + 1] [j-1])。因此,在这种情况下,最长[i] [j] =最长的[i + 1] [j-1] + 2(“+ 2”是两个帐户,因为最长的Parindrome从第i字母开始并以第J个字母结束,因为它们是平等的)

案例#3:如果是这种情况,那么最长的回文是由一些字母形成的(i+1)把信到j the信,或者从我信中的一些字母到(j-1)信封。由于我们想要最长的Palindrome,我们将获得最大的这两个值。因此,在这种情况下最长[i] [j] = max(最长[i + 1] [j],最长[i] [j-1])

但是,我们还没有完成。将所有这些复发添加在一起并创建一个天真的递归函数将超时(作为每对开始和结束字母(i, j)通过该功能多次访问)。因此,对此的修复是在2D阵列中存储最长的[I] [J],并且可以在其上工作(即动态编程),或创建递归函数,以确保不访问一对起始和结束字母(i, j) more than once (即用备忘录递归)。这个程序的时间复杂性是o(n^2),其中n是给定字的长度。

我想强调这些都很少有适用于这个问题的解决方案。随意尝试编码一些问题,测试程序可在dwite.org上使用。

我希望你们都喜欢比赛。
赞助
赞助
赞助
赞助
Cyril.




邮政发布: 2011年10月29日星期六晚上12:37  帖子主题:Re:Dwite圆#1解决方案/分析

#4可以在对数时间完成。

让f(n)是1到n之间的所有整数的总冷却。 (然后,我们的答案只是f(n)+ 1.)让我们回答这个问题:我们如何在F(12340)方面表达F(123405)?我们应该尝试最后一位数字的所有可能性。

将所有数字视为最后一位数字0.这些数字中有12340个,所以每个数字都有助于它们的最后一位0.从中间发生的这些数字的零怎么样?请注意,要完成该数量的其余部分,我们只能计算1到12340;我们只计算该范围内的零。因此,这种情况贡献了12340 + F(12340)到我们的总数。

现在,将所有数字考虑在1到5中的最后一位数。我们得到了类似的情况,但这时间结束时没有零。对于这些情况中的每一个,我们添加F(12340)。

最后,将所有数字视为6到9.这与前一个情况不同,因为我们不希望包含大于123405的数字,如123408.我们可以使用f(12339)来排除这些数字f(12340)。

所以,一般来说:

f(n)=
(设n'=楼层(n / 10),d = n%10)
总和i = 0到9 {
n'+ f(n'),如果i = 0
f(n'),如果是1<= i <= d
f(n' - 1),如果我> d
}

或者,如果你想觉得像黑客:

长长f(长长n){
return n<10? 0:n / 10 +(1 + n%10)* f(n / 10)+(9-n%10)* f(n / 10 - 1);
}

所以我们真的应该强制限制n<= 10^10000! 很高兴
d310




邮政发布: 2011年10月29日10:40 AM  帖子主题:Re:Dwite圆#1解决方案/分析

A.J. @ Fri 2011年10月28日11:23 PM写道:

有3例(如上所示):
1)角度驾驶室是钝的(i.e. >90度)在这种情况下,CA是从C到AB的最短距离
2)角度cba是钝的(i.e. >90度)其中cb是从c到ab的最短距离
3)C在垂直于AB和通过A和B的两条线之间(即L1和L2)之间。这种情况是需要一些数学的情况。


我觉得你的意思是:
1)角度驾驶室是钝的(i.e. >90度) in which case CA is the shortest distance from C to A
2)角度cba是钝的(i.e. >90度) in which case CB is the shortest distance from C to B

并且不要忘记可能只有一个点,所以在输入点时,只需首先计算与C到所有点的距离。
然后,如果C可以在AB之间创建垂直分支,则检查每对点。

仍然是一场伟大的比赛!
yves.




邮政发布: 2011年10月29日星期六下午2:03  帖子主题:Re:Dwite圆#1解决方案/分析

D310 @ 2011年10月29日星期六10:40我写道:
A.J. @ Fri 2011年10月28日11:23 PM写道:

有3例(如上所示):
1)角度驾驶室是钝的(i.e. >90度)在这种情况下,CA是从C到AB的最短距离
2)角度cba是钝的(i.e. >90度)其中cb是从c到ab的最短距离
3)C在垂直于AB和通过A和B的两条线之间(即L1和L2)之间。这种情况是需要一些数学的情况。


我觉得你的意思是:
1)角度驾驶室是钝的(i.e. >90度) in which case CA is the shortest distance from C to A
2)角度cba是钝的(i.e. >90度) in which case CB is the shortest distance from C to B

不,c到ab是正确的;线CA的长度是驾驶室钝时从点C到线段AB的最短距离。
A.J.




邮政发布: 孙2011年10月30日12:09 AM  帖子主题:Re:Dwite圆#1解决方案/分析

哇,我没有看到#4的对数解决方案。干得好的西里尔!
Ihsh.




邮政发布: 2011年11月1日星期二上午9:25  帖子主题:Re:Dwite圆#1解决方案/分析

嗯,我有一个关于#3的问题:你如何看待角度驾驶室或CBA是钝的?

现在,我可以想到的唯一方法是计算三角形ABC,平方的三个方面长度,并看看AC或BC的平方是否大于每种情况下剩余两个方块的总和(换句话说,余弦法。但是,这似乎并不像它一样简单......
Crossley7.




邮政发布: 2011年11月1日星期二上午9:29  帖子主题:Re:Dwite圆#1解决方案/分析

您必须使用触发可能的,因为线条不一定是水平或垂直的。所以是的,这就是你必须做的。虽然可能是一些方法可以使用毕达哥拉斯定理来解决它(我没有打扰修理我的解决方案,所以我不确定)
A.J.




邮政发布: 2011年11月02日星期三下午3:50  帖子主题:Re:Dwite圆#1解决方案/分析

您可以使用余弦定律来帮助您:

ab ^ 2 + bc ^ 2 - 2 * ab * bc * cos(角度abc)= ac ^ 2。

这基本上是毕达哥拉斯定理的概括。
赞助
赞助
赞助
赞助
哈哈




邮政发布: 星期四2011年11月3日12:28 AM  帖子主题:Re:Dwite圆#1解决方案/分析

我仍然不明白Cyril的解决方案......对不起不是一个非常强大的数学/ Compsci学生可以进一步打破....





邮政发布: 星期五2012年5月25日下午5:55  帖子主题:Re:Dwite圆#1解决方案/分析

Cyril. @ 2011年10月29日星期六晚上12:37写道:
#4可以在对数时间完成。
长长f(长长n){
return n<10? 0:n / 10 +(1 + n%10)* f(n / 10)+(9-n%10)* f(n / 10 - 1);
}


不应该在t(n)= 2t(n / 10)+ o(1)= O(n ^ 0.31)时间内运行,而不是O(lg n)时间?
从上一个显示帖子:   
   指数 -> Compsci.ca,比赛 -> dwite.
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题

11  [ 10 Posts ]
跳到:   


Style:  
搜索: