到底为啥那么多人转Data Science

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
[Google级团队]
实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习岗
把贵司招聘信息放这里
查看: 2001|回复: 14
收起左侧

Monkey Grid 问题边界值的问题

[复制链接] |试试Instant~ |关注本帖
huangyingw 发表于 2015-9-4 05:10:38 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类General 本科 全职@ - 网上海投 - HR筛选  | Other | 其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
题目是这样子的:
Thereis a monkey which can walk around on a planar grid. The monkey canmove one space at a time left, right, up or down. That is, from (x,y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).Points where the sum of the digits of the absolute value of the xcoordinate plus the sum of the digits of the absolute value of the ycoordinate are lesser than or equal to 19 are accessible to themonkey. For example, the point (59, 79) is inaccessible because 5 + 9+ 7 + 9 = 30, which is greater than 19. Another example: the point(-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, whichis less than 19. How many points can the monkey access if it startsat (0, 0), including (0, 0) itself? There is no input for thisprogram.
Printout the how many points can the monkey access. (The number should beprinted as an integer whole number eg. if the answer is 10 (its not!!), print out 10, not 10.0 or 10.00 etc)
比方说,K=25,单个下标的最大值是898,这个值是怎么算出来的,如何证明?

Linzertorte 发表于 2015-9-4 05:23:12 | 显示全部楼层
bfs搜索出来 的
回复 支持 反对

使用道具 举报

 楼主| huangyingw 发表于 2015-9-4 05:37:33 | 显示全部楼层

能不能数学证明呢?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 05:42:59 | 显示全部楼层
  1. from collections import deque
  2. def can_access(x,y,k):. From 1point 3acres bbs
  3.   if x<0:
  4.     x=-x
  5.   if y<0:
  6.     y = -y. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.   return sum([ord(i)-ord('0') for i in str(x)]) + sum([ord(i)-ord('0') for i in str(y)]) <= k

  8. def monkey_walk(k):
  9.   best = 0
  10.   dx=[0,0,-1,1]
  11.   dy=[1,-1,0,0]
  12.   Q = deque(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.   Q.append((0,0))
  14.   visited = set()
  15.   visited.add((0,0))
  16.   while Q:
  17.     head = Q.popleft(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.     for d in xrange(0,4):
  19.       x,y = head[0]+dx[d], head[1]+dy[d]
  20.       if (x,y) in visited or not can_access(x,y,k):
  21.         continue
  22.       Q.append((x,y))
  23.       visited.add((x,y)). from: 1point3acres.com/bbs
  24.       best = max(best,x)
  25.       best = max(best,y). 1point3acres.com/bbs
  26.   print 'best', best
  27.   return len(visited)

  28. print monkey_walk(25)
  29.                   
复制代码
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 05:45:40 | 显示全部楼层
hoho best best
1.jpg
回复 支持 反对

使用道具 举报

 楼主| huangyingw 发表于 2015-9-4 05:47:04 | 显示全部楼层

嘿嘿,代码我也有,不过是java实现的,帮我留意一下有没有google全球招聘的职位吧?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 05:53:00 | 显示全部楼层
------ 1
best 1. 鍥磋鎴戜滑@1point 3 acres
5. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
------ 2
best 2. Waral 鍗氬鏈夋洿澶氭枃绔,
13
------ 3
best 3
25
------ 4
best 4-google 1point3acres
41
------ 5
best 5
61
------ 6
best 6
85
------ 7
best 7. From 1point 3acres bbs
113
------ 8
best 8
145
------ 9
best 18
505
------ 10. 1point 3acres 璁哄潧
best 28
1121. Waral 鍗氬鏈夋洿澶氭枃绔,
------ 11. visit 1point3acres.com for more.
best 38. 1point 3acres 璁哄潧
2025
------ 12
best 48
3245
------ 13
best 58
4805
------ 14. 鍥磋鎴戜滑@1point 3 acres
best 68. 鍥磋鎴戜滑@1point 3 acres
6725
------ 15. From 1point 3acres bbs
best 78
9021
------ 16
best 88. visit 1point3acres.com for more.
11705
------ 17. more info on 1point3acres.com
best 98
14785. 鍥磋鎴戜滑@1point 3 acres
------ 18
best 198
47905
------ 19
best 298
102485 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
------ 20
best 398
181533. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
------ 21
best 498.鐣欏璁哄潧-涓浜-涓夊垎鍦
287881
------ 22
best 598
424129
------ 23
best 698. 1point 3acres 璁哄潧
592597
------ 24
best 798
795285
------ 25
best 898
1033841
------ 26
best 998
1309537
------ 27
best 1998. From 1point 3acres bbs
4216357. Waral 鍗氬鏈夋洿澶氭枃绔,
------ 28
best 2998
9006221


发现一个规律 。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 05:54:34 | 显示全部楼层
用归纳法试试?

回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 06:00:45 | 显示全部楼层
就说k=24到k=25
k=24, 可以到达(0,798), k=25可以到达(0,898)
798+1 ,数位加1,是799,然后再1的话,就是800,直到加到899,都是数位和<=25.
这个就证明了一个方向了。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 06:04:37 | 显示全部楼层
哦证明了。。 直到加到898, 因为 899就超了,所以f(25)<899.
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-4 06:07:23 | 显示全部楼层
最后的公式   f(k) = {  if k<=8, return k; else   return      (k-8)%9
  1. def f(k):. 1point 3acres 璁哄潧
  2.   if k<=8:
  3.     return k
  4.   x = (k-8)%9 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.   for i in xrange(0,k/9)
  6.     x = x*10+9 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.   return x*10+8. from: 1point3acres.com/bbs
复制代码

补充内容 (2015-9-4 06:09):
for i in xrange(1,k/9)
回复 支持 反对

使用道具 举报

 楼主| huangyingw 发表于 2015-9-4 13:02:05 | 显示全部楼层
Linzertorte 发表于 2015-9-4 06:07
最后的公式   f(k) = {  if k

你太强了,牛逼轰轰的推导,学习中.
回复 支持 反对

使用道具 举报

 楼主| huangyingw 发表于 2015-9-4 13:59:26 | 显示全部楼层
Linzertorte 发表于 2015-9-4 06:07
最后的公式   f(k) = {  if k

哈哈,我自己也分析了一下,我觉得可能我的推导要简单一些,求k 的最大值,相当于求k+1的最小值然后减1
所以,代码也相应要简单一些.
这一局我赢啦.
def fun(k):
    x = (k+1) % 9
    for i in xrange(0, (k+1)/9):
        x = x*10+9. from: 1point3acres.com/bbs
    return x-1
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-9-5 02:43:16 | 显示全部楼层
huangyingw 发表于 2015-9-4 13:59
哈哈,我自己也分析了一下,我觉得可能我的推导要简单一些,求 k 的最大值,相当于求k+1的最小值然后减1. 鍥磋鎴戜滑@1point 3 acres
所 ...
. visit 1point3acres.com for more.
你开心就好
回复 支持 反对

使用道具 举报

 楼主| huangyingw 发表于 2015-9-5 12:22:12 | 显示全部楼层

哈哈,我阿Q一下罢了.你有工作,而且还是高大上的工作,我木有工作....
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-25 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表