Google编程竞赛题

griefforyou 2005-12-08 01:38:26
题目如下：
Problem Statement
    
A simple line drawing program uses a blank 20 x 20 pixel canvas and a directional cursor that starts at the upper left corner pointing straight down. The upper left corner of the canvas is at (0, 0) and the lower right corner is at (19, 19). You are given a String(), commands, each element of which contains one of two possible commands. A command of the form "FORWARD x" means that the cursor should move forward by x pixels. Each pixel on its path, including the start and end points, is painted black. The only other command is "LEFT", which means that the cursor should change its direction by 90 degrees counterclockwise. So, if the cursor is initially pointing straight down and it receives a single "LEFT" command, it will end up pointing straight to the right. Execute all the commands in order and return the resulting 20 x 20 pixel canvas as a String() where character j of element i represents the pixel at (i, j). Black pixels should be represented as uppercase 'X' characters and blank pixels should be represented as '.' characters.
Definition
    
Class:
DrawLines
Method:
execute
Parameters:
String()
Returns:
String()
Method signature:
Public Function execute(commands As String()) As String()
(be sure your method is public)
    

Notes
-
The cursor only paints the canvas if it moves (see example 1).
Constraints
-
commands will contain between 1 and 50 elements, inclusive.
-
Each element of commands will be formatted as either "LEFT" or "FORWARD x" (quotes for clarity only), where x is an integer between 1 and 19, inclusive, with no extra leading zeros.
-
When executing the commands in order, the cursor will never leave the 20 x 20 pixel canvas.
Examples
0)

    
{"FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19"}
Returns:
{"XXXXXXXXXXXXXXXXXXXX",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"XXXXXXXXXXXXXXXXXXXX" }
This sequence of commands draws a 20 x 20 outline of a square. The cursor is initially at (0, 0) pointing straight down. It then travels to (0, 19) after the first FORWARD command, painting each pixel along its path with a '*'. It then rotates 90 degrees left, travels to (19, 19), rotates 90 degrees left, travels to (19, 0), rotates 90 degrees left, and finally travels back to (0, 0).
1)

    
{"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT"}
Returns:
{"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"...................." }
The cursor spins round and round, but never actually paints any pixels. The result is an empty canvas.
2)

    
{"FORWARD 1"}
Returns:
{"X...................",
"X...................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"...................." }
Going forward by one pixel creates a line that is 2 pixels long because both the start and end points are painted.
3)

    
{"LEFT", "FORWARD 19", "LEFT", "LEFT", "LEFT",
"FORWARD 18", "LEFT", "LEFT", "LEFT", "FORWARD 17",
"LEFT", "LEFT", "LEFT", "FORWARD 16", "LEFT",
"LEFT", "LEFT", "FORWARD 15", "LEFT", "LEFT", "LEFT",
"FORWARD 14", "LEFT", "LEFT", "LEFT", "FORWARD 13",
"LEFT", "LEFT", "LEFT", "FORWARD 12", "LEFT", "LEFT",
"LEFT", "FORWARD 11", "LEFT", "LEFT", "LEFT", "FORWARD 10",
"LEFT", "LEFT", "LEFT", "FORWARD 9", "LEFT", "LEFT",
"LEFT", "FORWARD 8", "LEFT", "LEFT", "LEFT", "FORWARD 7"}
Returns:
{"XXXXXXXXXXXXXXXXXXXX",
"...................X",
"..XXXXXXXXXXXXXXXX.X",
"..X..............X.X",
"..X.XXXXXXXXXXXX.X.X",
"..X.X..........X.X.X",
"..X.X.XXXXXXXX.X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.XXXXXXXXXX.X.X",
"..X.X............X.X",
"..X.XXXXXXXXXXXXXX.X",
"..X................X",
"..XXXXXXXXXXXXXXXXXX",
"...................." }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
...全文
310 9 打赏 收藏 转发到动态 举报
写回复
用AI写文章
9 条回复
切换为时间正序
请发表友善的回复…
发表回复
griefforyou 2005-12-08
  • 打赏
  • 举报
 回复
今天选择了一个100分的题，想不到更简单


Problem Statement
    
When editing a single line of text, there are four keys that can be used to move the cursor: end, home, left-arrow and right-arrow. As you would expect, left-arrow and right-arrow move the cursor one character left or one character right, unless the cursor is at the beginning of the line or the end of the line, respectively, in which case the keystrokes do nothing (the cursor does not wrap to the previous or next line). The home key moves the cursor to the beginning of the line, and the end key moves the cursor to the end of the line. You will be given a Integer, N, representing the number of character in a line of text. The cursor is always between two adjacent characters, at the beginning of the line, or at the end of the line. It starts before the first character, at position 0. The position after the last character on the line is position N. You should simulate a series of keystrokes and return the final position of the cursor. You will be given a String where characters of the String represent the keystrokes made, in order. 'L' and 'R' represent left and right, while 'H' and 'E' represent home and end.
Definition
    
Class:
CursorPosition
Method:
getPosition
Parameters:
String, Integer
Returns:
Integer
Method signature:
Public Function getPosition(keystrokes As String, N As Integer) As Integer
(be sure your method is public)
    

Constraints
-
keystrokes will be contain between 1 and 50 'L', 'R', 'H', and 'E' characters, inclusive.
-
N will be between 1 and 100, inclusive.
Examples
0)

    
"ERLLL"
10
Returns: 7
First, we go to the end of the line at position 10. Then, the right-arrow does nothing because we are already at the end of the line. Finally, three left-arrows brings us to position 7.
1)

    
"EHHEEHLLLLRRRRRR"
2
Returns: 2
All the right-arrows at the end ensure that we end up at the end of the line.
2)

    
"ELLLELLRRRRLRLRLLLRLLLRLLLLRLLRRRL"
10
Returns: 3

3)

    
"RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL"
19
Returns: 12

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


这次可以编译了，但是提示Len函数和Mid函数未声明，而我在代码放到VB里运行正常，不知道需要怎么写才能让TopCoder的编译器支持这两个函数

编译错误信息：
Your code did not compile:

(6) : error BC30451: Name 'Len' is not declared.

For i = 0 To Len(keystrokes) - 1
~~~
(7) : error BC30451: Name 'Mid' is not declared.

CurrentPosition = CursorMove(Mid(keystrokes, i + 1, 1), CurrentPosition, N)




我的源代码如下：

Public Function getPosition(keystrokes As String, N As Integer) As Integer
Dim CurrentPosition As Integer
Dim i As Integer
CurrentPosition = 0
For i = 0 To Len(keystrokes) - 1
CurrentPosition = CursorMove(Mid(keystrokes, i + 1, 1), CurrentPosition, N)
Next
getPosition = CurrentPosition
End Function

Private Function CursorMove(Action As String, C As Integer, N As Integer) As Integer
Select Case Action
Case "E"
CursorMove = N
Case "H"
CursorMove = 0
Case "L"
If C - 1 < 0 Then
CursorMove = 0
Else
CursorMove = C - 1
End If
Case "R"
If C + 1 > N Then
CursorMove = N
Else
CursorMove = C + 1
End If
End Select
End Function
griefforyou 2005-12-08
  • 打赏
  • 举报
 回复
题目稍微看一下，然后对照给出的输入数据和输出结果大概就可以明白了。

只是我现在不清楚在测试软件的环境下与在VB环境下的代码需要做哪些变化。
IamDeane 2005-12-08
  • 打赏
  • 举报
 回复
报完名了啊，我早就想去看看，虽然水平不高，呵呵，这满是鸟文，这不欺负中国人么，抗议
Summer006 2005-12-08
  • 打赏
  • 举报
 回复
我也报了名，但没去看。
题是英文的啊？？？那我还是放弃算了。。。
哪位高人可否翻译一下啊，我也想试试～～
griefforyou 2005-12-08
  • 打赏
  • 举报
 回复
我开始没有考虑清楚就动手写了，结果代码写的不理想，百且也超时了。。　：（

代码如下：
'Class1.cls

Option Explicit


Private Enum Direction
d_down = 0
d_right = 1
d_up = 2
d_left = 3
End Enum

Private Type Point
X As Integer
Y As Integer
End Type

Private resultArr(19, 19) As String
Private CurrentDirection As Direction
Private CurrentPosition As Point

Public Function execute(commands() As String) As String()
Dim i As Integer, j As Integer
CurrentDirection = d_down

For i = 0 To 19
For j = 0 To 19
resultArr(i, j) = "."
Next
Next
CurrentPosition.X = 0
CurrentPosition.Y = 0

For i = 0 To UBound(commands)
ExecuteCommand commands(i)
Next

execute = resultArr
End Function

Private Sub ExecuteCommand(strCommand As String)
Dim ForwardStep As Integer

If strCommand = "LEFT" Then
If CurrentDirection = d_left Then
CurrentDirection = d_down
Else
CurrentDirection = CurrentDirection + 1
End If
ElseIf Left(strCommand, 8) = "FORWARD " Then
ForwardStep = Val(Mid(strCommand, 9))
Forward ForwardStep
End If
End Sub

Private Sub Forward(ForwardStep As Integer)
Dim i As Integer
Select Case CurrentDirection
Case d_down
For i = 0 To ForwardStep
SetPixel CurrentPosition.Y + i, CurrentPosition.X
Next
CurrentPosition.Y = CurrentPosition.Y + i - 1
Case d_up
For i = 0 To ForwardStep
SetPixel CurrentPosition.Y - i, CurrentPosition.X
Next
CurrentPosition.Y = CurrentPosition.Y - i + 1
Case d_right
For i = 0 To ForwardStep
SetPixel CurrentPosition.Y, CurrentPosition.X + i
Next
CurrentPosition.X = CurrentPosition.X + i - 1
Case d_left
For i = 0 To ForwardStep
SetPixel CurrentPosition.Y, CurrentPosition.X - i
Next
CurrentPosition.X = CurrentPosition.X - i + 1
End Select
End Sub

Private Sub SetPixel(Y As Integer, X As Integer)
resultArr(Y, X) = "X"
End Sub


'Form1.frm
Option Explicit

Private Sub Form_Load()
Dim c As New Class1
Dim A() As String
Dim result() As String
Dim strTemp As String
A = Split("LEFT,FORWARD 19,LEFT,LEFT,LEFT,FORWARD 18,LEFT,LEFT,LEFT,FORWARD 17,LEFT,LEFT,LEFT,FORWARD 16,LEFT,LEFT,LEFT,FORWARD 15,LEFT,LEFT,LEFT,FORWARD 14,LEFT,LEFT,LEFT,FORWARD 13,LEFT,LEFT,LEFT,FORWARD 12,LEFT,LEFT,LEFT,FORWARD 11,LEFT,LEFT,LEFT,FORWARD 10,LEFT,LEFT,LEFT,FORWARD 9,LEFT,LEFT,LEFT,FORWARD 8,LEFT,LEFT,LEFT,FORWARD 7", ",")
result = c.execute(A)

Dim i, j

For i = 0 To 19
strTemp = ""
For j = 0 To 19
strTemp = strTemp & result(i, j)
Next
Debug.Print strTemp
Next
End Sub

输出结果为
XXXXXXXXXXXXXXXXXXXX
...................X
..XXXXXXXXXXXXXXXX.X
..X..............X.X
..X.XXXXXXXXXXXX.X.X
..X.X..........X.X.X
..X.X.XXXXXXXX.X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.X........X.X.X
..X.X.XXXXXXXXXX.X.X
..X.X............X.X
..X.XXXXXXXXXXXXXX.X
..X................X
..XXXXXXXXXXXXXXXXXX
....................


基本通过。。。





上面的代码我是在VB里写的，不知道在TopCoder中如何通过编译和测试。哪位指点一下？


northwolves 2005-12-08
  • 打赏
  • 举报
 回复
http://www.google.com/chinacodejam
http://www.topcoder.com/pl/?module=Static&d1=gccj05&d2=ZH_instructions

都打不开
northwolves 2005-12-08
  • 打赏
  • 举报
 回复
也想报名来着，只是报名和介绍的那个连接始终打不开，不知是何缘故？
griefforyou 2005-12-08
  • 打赏
  • 举报
 回复
写错了，是明白了。。。
griefforyou 2005-12-08
  • 打赏
  • 举报
 回复
总算明天了，是VB.Net

Imports Microsoft.VisualBasic
Public Class CursorPosition
Public Function getPosition(keystrokes As String, N As Integer) As Integer
Dim CurrentPosition As Integer
Dim i As Integer
CurrentPosition = 0
For i = 0 To Len(keystrokes) - 1
CurrentPosition = CursorMove(Mid(keystrokes, i + 1, 1), CurrentPosition, N)
Next
getPosition = CurrentPosition
End Function
Private Function CursorMove(Action As String, C As Integer, N As Integer) As Integer
Select Case Action
Case "E"
CursorMove = N
Case "H"
CursorMove = 0
Case "L"
If C - 1 < 0 Then
CursorMove = 0
Else
CursorMove = C - 1
End If
Case "R"
If C + 1 > N Then
CursorMove = N
Else
CursorMove = C + 1
End If
End Select
End Function
End Class
Google竞赛题（c语言）
Google竞赛题Google竞赛题Google竞赛题Google竞赛题Google竞赛题Google竞赛题
Google中国编程大赛入围赛真题
Google中国编程大赛入围赛真题
awesome-programming-competitions:很棒的编程比赛清单
很棒的编程比赛 精选的正在进行的编程竞赛清单。 传统的 这些竞赛要求您练习算法和数据结构知识。 基于俄罗斯的国际知名竞争性编程网站。 拥有强大的社区，全年举办教育和排名较高的编程比赛。 一个网站，可帮助您通过一系列面试问题，视频和解决方案来练习编程技能。 您将有几个小时来解决日益棘手的算法编程问题。 顶尖编码员将被邀请参加Google网站上的决赛。 从三月开始。 个人和企业编程网站。 包含大量跨越多种语言的练习题。 网站还定期举办企业赞助的编码竞赛。 -一系列600多项数学/计算机编程问题。 -Java，C ++和C＃语言的在线计算机编程竞赛。 比赛每周举行两次，会员可以赢取$ 25- $ 300。 严格针对高中生，这项算法竞赛为美国IOI团队确定了人才。 从12月到3月运行。 游戏类 在这些比赛中，您将编写一个机器人来玩游戏。 战法（Battlecode） -编写机器
挑战程序设计竞赛（第2版）
世界顶级程序设计高手的经验总结 【ACM-ICPC全球总冠军】巫泽俊主译 日本ACM-ICPC参赛者人手一册 本书对程序设计竞赛中的基础算法和经典问题进行了汇总，分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验，对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解，并介绍了许多实用技巧。每章后附有习题，供读者练习，巩固所学。 本书适合程序设计人员、程序设计竞赛爱好者以及高校计算机专业师生阅读。 目录 · · · · · · 译者序 前言 第1章　蓄势待发——准备篇 1.1 　何谓程序设计竞赛 1.2 　最负盛名的程序设计竞赛 1.2.1 　世界规模的大赛——Google Code Jam（GCJ） 1.2.2 　向高排名看齐！——TopCoder 1.2.3 　历史最悠久的竞赛—— ACM-ICPC 1.2.4 　面向中学生的信息学奥林匹克竞赛——JOI-IOI 1.2.5 　通过网络自动评测——Online Judge（OJ） 1.3 　本书的使用方法 1.3.1 　本书所涉及的内容 1.3.2 　所用的编程语言 1.3.3 　题目描述的处理 1.3.4 　程序结构 1.3.5 　练习题 1.3.6 　读透本书后更上一层楼的练习方法 1.4 　如何提交解答 1.4.1 　POJ的提交方法 1.4.2 　GCJ的提交方法 1.5 　以高效的算法为目标 1.5.1 　什么是复杂度 1.5.2 　关于运行时间 1.6 　轻松热身 1.6.1 　先从简单题开始 1.6.2 　POJ的题目Ants 1.6.3 　难度增加的抽签问题 阅读 第2章　初出茅庐——初级篇 2.1 　最基础的“穷竭搜索” 2.1.1 　递归函数 2.1.2 　栈 2.1.3 　队列 2.1.4 　深度优先搜索 2.1.5 　宽度优先搜索 2.1.6 　特殊状态的枚举 2.1.7 　剪枝 2.2 　一往直前！贪心法 2.2.1 　硬币问题 2.2.2 　区间问题 2.2.3 　字典序最小问题 2.2.4 　其他例题 2.3 　记录结果再利用的“动态规划” 2.3.1 　记忆化搜索与动态规划 2.3.2 　进一步探讨递推关系 2.3.3 　有关计数问题的DP 2.4 　加工并存储数据的数据结构 2.4.1 　树和二叉树 2.4.2 　优先队列和堆 2.4.3 　二叉搜索树 2.4.4 　并查集 2.5 　它们其实都是“图” 2.5.1 　图是什么 2.5.2 　图的表示 2.5.3 　图的搜索 2.5.4 　最短路问题 2.5.5 　最小生成树 2.5.6 　应用问题 2.6 　数学问题的解题窍门 2.6.1 　辗转相除法 2.6.2 　有关素数的基础算法 2.6.3 　模运算 2.6.4 　快速幂运算 2.7 　一起来挑战GCJ的题目（1） 2.7.1 　Minimum Scalar Product 2.7.2 　Crazy Rows 2.7.3 　Bribe the Prisoners 2.7.4 　Millionaire 阅读 第3章　出类拔萃——中级篇 3.1 　不光是查找值！“二分搜索” 3.1.1 　从有序数组中查找某个值 3.1.2 　假定一个解并判断是否可行 3.1.3 　最大化最小值 3.1.4 　最大化平均值 3.2 　常用技巧精选（一） 3.2.1 　尺取法 3.2.2 　反转（开关问题） 3.2.3 　弹性碰撞 3.2.4 　折半枚举（双向搜索） 3.2.5 　坐标离散化 3.3 　活用各种数据结构 3.3.1 　线段树 3.3.2 　Binary Indexed Tree 3.3.3 　分桶法和平方分割 3.4 　熟练掌握动态规划 3.4.1 　状态压缩DP 3.4.2 　矩阵的幂 3.4.3 　利用数据结构高效求解 3.5 　借助水流解决问题的网络流 3.5.1 　最大流 3.5.2 　最小割 3.5.3 　二分图匹配 3.5.4 　一般图匹配 3.5.5 　匹配、边覆盖、独立集和顶点覆盖 3.5.6 　最小费用流 3.5.7 　应用问题 3.6 　与平面和空间打交道的计算几何 3.6.1 　计算几何基础 3.6.2 　极限情况 3.6.3 　平面扫描 3.6.4 　凸包 3.6.5 　数值积分 3.7 　一起来挑战GCJ的题目（2） 3.7.1 　Numbers 3.7.2 　No Cheating 3.7.3 　Stock Charts 3.7.4 　Watering Plants 3.7.5 　Number Sets 3.7.6 　Wi-fi Towers 第4章　登峰造极——高级篇 4.1 　更加复杂的数学问题 4.1.1 　矩阵 4.1.2 　模运算的世界 4.1.3 　计数 4.1.4 　具有对称性的计数 4.2 　找出游戏的必胜策略 4.2.1 　游戏与必胜策略 4.2.2 　Nim 4.2.3 　Grundy数 4.3 　成为图论大师之路 4.3.1 　强连通分量分解 4.3.2 　2-SAT 4.3.3 　LCA 4.4 　常用技巧精选（二） 4.4.1 　栈的运用 4.4.2 　双端队列的运用 4.4.3 　倍增法 4.5 　开动脑筋智慧搜索 4.5.1 　剪枝 4.5.2 　A*与IDA* 4.6 　划分、解决、合并：分治法 4.6.1 　数列上的分治法 4.6.2 　树上的分治法 4.6.3 　平面上的分治法 4.7 　华丽地处理字符串 4.7.1 　字符串上的动态规划算法 4.7.2 　字符串匹配 4.7.3 　后缀数组 4.8 　一起来挑战GCJ的题目（3） 4.8.1 　Mine Layer 4.8.2 　Year of More Code Jam 4.8.3 　Football Team 4.8.4 　Endless Knight 4.8.5 　The Year of Code Jam 阅读 本书中未涉及的拓展主题 书中例题列表 参考文献
请问有没有那种在线的Python练习题库？.pdf
请问有没有那种在线的 请问有没有那种在线的Python练习题库？ 练习题库？ 推荐⼏个Python从初学者⼊门到⾯试刷题的Python在线练习⽹站： Pyschools（适合 （适合Python基础⼊门） 基础⼊门） 完全免费，只需要google账号登陆即可。Pyschools包括三个主要部分： Python基础知识学习：本部分将为你提供有关学习Python编程的资源的链接。 练习：本部分附带⼀些⼩练习，可以应⽤所学的知识。 项⽬挑战：本部分使你可以与其他程序员⼀起参加⼀些竞赛。 每⼀类基础语法下设置了多种不同的练习题 基础知识的在线练习 Problem Solving with Algorithms and Data Structures using Python（适合 （适合Python基础 基础 ⼊门） ⼊门） 完全免费，提供Python基本的语法学习和练习题 每⼀章节学习完成之后进⾏课后在线练习 HackerRank（适合 （适合Python进阶刷题） 进阶刷题） HackerRank⽹站是程序员们相互交流&挑战的社交平台。⽹站提供各种编程谜题、现实中的编 程难题和挑战。程序员
VB基础类

7,762

社区成员

197,608

社区内容

发帖
与我相关
我的任务
社区描述
VB 基础类
社区管理员
  • VB基础类社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章