标题:google 编程挑战赛题目
只看楼主
lisypro
Rank: 4
等 级:业余侠客
威 望:3
帖 子:695
专家分:216
注 册:2005-9-25
结帖率:33.33%
 问题点数:0 回复次数:6 
google 编程挑战赛题目

第一题 [250分]
Problem Statement

You want to buy two neighboring tickets in the first row of the theater so that one of the tickets is as far from the aisles as possible.
You will be given a String describing the first row of the theater where '.' represents an empty seat and 'X' represents an occupied seat. Your task is to return the index (from 0) of the empty seat that is furthest from the aisles (the two ends of the String) and is also next to an empty seat. If there are multiple possible seats, return the one with the smallest index. Return -1 if there are no seats that satisfy your requirements.
Definition

Class:
TheaterVisit
Method:
chooseSeat
Parameters:
string
Returns:
int
Method signature:
int chooseSeat(string row)
(be sure your method is public)


Constraints
-
row will contain between 1 and 50 characters, inclusive.
-
Each character in row will be either '.' or 'X'.
Examples
0)


"....."
Returns: 2
You can buy either tickets with indexes 1 and 2 or tickets with indexes 2 and 3.
1)


"......"
Returns: 2

2)


"..X..."
Returns: 3
You should buy tickets with indexes 3 and 4.
3)


".X.X..."
Returns: 4

4)


"X.XX.X"
Returns: -1

5)


".."
Returns: 0

搜索更多相关主题的帖子: google 挑战赛 
2005-12-21 08:13
lisypro
Rank: 4
等 级:业余侠客
威 望:3
帖 子:695
专家分:216
注 册:2005-9-25
得分:0 

第二题[500分]

Problem Statement

A group of vertical blocks are placed densely one after another on the ground. The blocks each have a width of 1, but their heights may vary. For example, if the heights of the vertical blocks are given as {1,5,5,1,6,1}, the configuration would look like the following picture:

Your task is to reproduce the exact shape of this structure using some number of non-intersecting rectangles. You will be given a vector <int> heights representing the heights of the vertical blocks from left to right. Return the minimal number of rectangles necessary to perform this task with the given configuration of blocks.
Definition

Class:
BlockStructure
Method:
cover
Parameters:
vector <int>
Returns:
int
Method signature:
int cover(vector <int> heights)
(be sure your method is public)


Constraints
-
heights will have between 1 and 50 elements, inclusive.
-
Each element of heights will be between 1 and 1000, inclusive.
Examples
0)


{1,5,5,1,6,1}
Returns: 3

We can use rectangles with sizes 6x1, 2x4 and 1x5.
1)


{2,2,2,4,4}
Returns: 2

We can use a 3x2 rectangle and a 2x4 rectangle.
2)


{6,6,6,6,6,6}
Returns: 1
The structure is a rectangle.
3)


{71,44,95,16,10,80,12,17,98,61}
Returns: 10
It's impossible to use less than 10 rectangles.
4)


{100,100,97,100,100,100,97,98,99,99}
Returns: 5


长期承接管理系统
代做各种vb/ / vc小程序
QQ:82341763
手机:13623290828
群号 11619730
2005-12-21 08:18
lisypro
Rank: 4
等 级:业余侠客
威 望:3
帖 子:695
专家分:216
注 册:2005-9-25
得分:0 

第三题[1000分]
Problem Statement

We have a sequence of integers, and we would like to remove all duplicate elements from this sequence. There may be multiple ways to perform this task. For example, given the sequence { 1, 2, 1, 3 }, we could end up with either { 1, 2, 3 } or { 2, 1, 3 } as the remaining sequence, depending on which duplicate 1 we remove from the original sequence. For this problem, we want to return the lexicographically first of of all possible remaining sequences. A sequence S1 comes before sequence S2 lexicographically if and only if S1 has a smaller value than S2 at the lowest index at which the two sequences differ (so, for example, { 1, 2, 3 } comes before { 2, 3, 1 }).
You will be given a int[] sequence. Return a int[] containing the sequence after all the duplicates are removed. See the examples for further clarification.
Definition

Class:
HardDuplicateRemover
Method:
process
Parameters:
int[]
Returns:
int[]
Method signature:
int[] process(int[] sequence)
(be sure your method is public)


Constraints
-
sequence will have between 1 and 50 elements, inclusive.
-
Each element of sequence will be between 1 and 1000, inclusive.
Examples
0)


{5, 6, 5, 1, 6, 5}
Returns: {1, 6, 5 }
There are six different ways to remove duplicates (remaining numbers are marked by '*'):
{ *5, *6, 5, *1, 6, 5},
{ *5, 6, 5, *1, *6, 5},
{ 5, *6, *5, *1, 6, 5},
{ 5, 6, *5, *1, *6, 5},
{ 5, *6, 5, *1, 6, *5},
{ 5, 6, 5, *1, *6, *5}.

The last variant is the lexicographically first.
1)


{3, 2, 4, 2, 4, 4}
Returns: {3, 2, 4 }

2)


{6, 6, 6, 6, 6, 6}
Returns: {6 }

3)


{1, 3, 2, 4, 2, 3}
Returns: {1, 2, 4, 3 }

4)


{5, 4, 1, 5}
Returns: {4, 1, 5 }


长期承接管理系统
代做各种vb/ / vc小程序
QQ:82341763
手机:13623290828
群号 11619730
2005-12-21 08:22
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
得分:0 
    晕哦。题目都看不明白。这就是英语差的恶果

[此贴子已经被作者于2005-12-21 8:51:22编辑过]



生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-12-21 08:51
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
得分:0 
请楼主翻译。。。。。
顺便说一下,我的第一题就是这个第一题

2005-12-21 09:53
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
得分:0 
#include<iostream>
#include<sstream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
class DiskClusters{
public:
int minimumFragmentation(string disk, int size){
int len=disk.length(),temp=0,vs=0,j=0,fg=0;
vector<int> l;
for(int i=0; i<len; i++)
if(disk[i]=='.')
temp++;
else{
l.push_back(temp);
temp=0;
}
sort(l.begin(),l.end());
vs=l.size();
for(; j<vs; j++){
size-=l[vs-1-j];
if(size<=0){
fg=1;
break;
}
}
if(fg) return j;
else return -1;
}
};

2005-12-21 09:54
corrupt
Rank: 2
等 级:新手上路
威 望:3
帖 子:535
专家分:0
注 册:2004-9-29
得分:0 
参加了, 得了 425
让淘汰了

2005-12-25 08:53



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-39189-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.145880 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved