Các bài tập từ Topcoder ( Problems 11-20 )

[rox_rook]

Chúng ta đã có 1 topic thật sôi động về những bài tập giải thuật không quá khó cũng không quá dễ từ trang này, và mình cảm thấy quả thật lâu lâu làm 1 vài bài giải trí thế này rất bổ ích cho việc rèn luyện lập trình của chúng ta . Đừng có lày lội quá cay cú hoài làm ko ra thì có mà ...Và mình quyết định sẽ tiếp tục series này coi như 1 góc thư giãn cuối tuần dành cho các bạn yêu thích vẻ đẹp của giải thuật trong tin học. Cứ mỗi Set như thế sẽ gồm 10 bài, vì để tiện việc theo dõi cho các bạn mới học, cho nên mình không thể kéo dài lê thê lết thết được, mong các bạn thông cảm nhé. Bắt đầu tiếp nào :

Bài 1

Problem Statement

When shopping for TVs consumers may notice that a TV's size is given by its diagonal in inches. The aspect ratio of a screen is the ratio of its width to its height. Given the aspect ratio and the diagonal size in inches of a TV screen, you must compute its width and height in inches (see the notes and the first example for more information). If the width or the height is not an integer, round down to the nearest integer; for example, 1.7 would become 1. You are tasked with writing a method which accepts 3 arguments: an int diagonal specifying the TV's diagonal in inches, an int height specifying the aspect ratio height, and an int width specifying the aspect ratio width. Your program should compute the actual height and width of the TV in inches and return them in a int[] where the first element is the TV's height and the second element is the TV's width.
Definition

Class:
TVSize
Method:
calcSize
Parameters:
int, int, int
Returns:
int[]
Method signature:
int[] calcSize(int diagonal, int height, int width)
(be sure your method is public)


Notes
-
Let W denote the width, H denote the height and D denote the diagonal of the screen. Then W*W + H*H = D*D and W * height = H * width.
Constraints
-
diagonal will be between 5 and 1000, inclusive.
-
height will be between 1 and 99, inclusive.
-
width will be between 2 and 100, inclusive.
-
width will be greater than height.
Examples
0)


52
9
16
Returns: {25, 45 }
W = (width/height) * H
D*D = W*W + H*H
52^2 = (width/height)^2 * H^2 + H^2
52^2 = (16/9)^2 * H^2 + H^2
H = 25.49
W = 45.32
1)


7
2
3
Returns: {3, 5 }

2)


13
7
10
Returns: {7, 10 }

3)


7
32
47
Returns: {3, 5 }

4)


11
15
16
Returns: {7, 8 }

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

[rox_rook]

Bài 2

Problem Statement

A sentence is composed of words, spaces and punctuation. For this problem, words are maximal contiguous strings of letters. Given a sentence, sort the words in the sentence while preserving the spaces and punctuation. Sorting is case sensitive, so uppercase letters precede lowercase letters. Return the newly constructed sentence. Example:
"The big, brown dog ran down the street!"
Returns:
"The big, brown dog down ran street the!"
Observe the space and punctuation preservation between the original sentence and the resulting sentence.
Definition

Class:
SuperSort
Method:
wordSort
Parameters:
String
Returns:
String
Method signature:
String wordSort(String sentence)
(be sure your method is public)


Notes
-
Watch out for multiple consecutive spaces (they should be preserved).
Constraints
-
sentence will contain between 1 and 50 characters, inclusive.
-
Each character in sentence will be either a letter ('a'-'z', 'A'-'Z'), ' ', '.', ',', '!' or '?'.
Examples
0)


"The big, brown dog ran down the street!"
Returns: "The big, brown dog down ran street the!"

1)


"This is the first sentence of the paragraph."
Returns: "This first is of paragraph sentence the the."

2)


"t.d,a!f?g.b,q!i?p.h,s!u?m.l,e!v?y.c,j!w?k.n,x!o?r ."
Returns: "a.b,c!d?e.f,g!h?i.j,k!l?m.n,o!p?q.r,s!t?u.v,w!x?y ."

3)


"What is this?"
Returns: "What is this?"

4)


"? . , ! "
Returns: "? . , ! "

5)


" "
Returns: " "

6)


"faecdb"
Returns: "faecdb"

7)


"a A b B c C d D e E"
Returns: "A B C D E a b c d e"

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.

[rox_rook]

Bài 3

Problem Statement

When programming, I don't like to take my fingers off the keyboard, and hence, I don't use the mouse. So, when navigating my source, I like to do so in such a way as to minimize keystrokes. My text editor supports the following keystrokes: left, right, up, down, home, end, top, bottom, word left and word right. The word left and word right keystrokes position the cursor at a word beginning; a word beginning is the first letter of the word. None of the keystrokes cause the cursor to wrap. When moving the cursor vertically, my text editor does not change the cursor's horizontal position. So, if the cursor is at column 50 and the up arrow is pressed, moving the cursor to a row with only 10 characters, only the row changes. My text editor does not allow the cursor to be positioned left of the first column, above the first row or below the last row. The keys left, right, up, down, home, end, top, bottom, word left and word right behave as described below: 1. left, right, up and down - move the cursor one position in the indicated direction (see notes). 2. home - causes the cursor to move to column 0 of the current row. 3. end - causes the cursor to move to the last character of source in the current row. 4. top - causes the cursor to move to the top row (row 0) retaining its column position. 5. bottom - causes the cursor to move to the bottom row retaining its column position. 6. word left - causes the cursor to jump to the first word beginning that is strictly left of the cursor position, if one exists. Otherwise does nothing. 7. word right - causes the cursor to jump to the first word beginning that is strictly right of the cursor position, if one exists. Otherwise does nothing. You will be given a String[] source representing the source code, a int[] start representing the starting position of the cursor and a int[] finish representing the ending position of the cursor. The first int in both start and finish specifies the 0-indexed row and the second int specifies the 0-indexed column. You are to calculate and return the minimum number of keystrokes required to get from start to finish.
Definition

Class:
TextEditorNavigation
Method:
keystrokes
Parameters:
String[], int[], int[]
Returns:
int
Method signature:
int keystrokes(String[] source, int[] start, int[] finish)
(be sure your method is public)


Notes
-
For the purposes of this problem, we use the convention that the cursor covers each character. Some editors (normally in "insert mode") have the cursor preceding each character.
-
A keypress may not have any effect. For example, pressing up in the top row does nothing, pressing left in the first column does nothing and pressing down in the bottom row does nothing. Pressing right always has an effect.
Constraints
-
source will contain between 1 and 50 elements, inclusive.
-
Each element of source will contain between 1 and 50 characters, inclusive.
-
Each character must be a letter ('a'-'z', 'A'-'Z') or ' '.
-
start and finish will each contain exactly 2 elements.
-
start and finish will each represent character positions that exist in source.
Examples
0)

{"AAAAA AAA AAAAAAAAAAAAA  AAAA",
 "AA   AAAAAAAAA AAAA     AAAA",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBB BBBBBBBBBB BBBBBBB",
 "CCC CCCC CCCCCC      CCCC",
 "DDDDDDDDDDDDDDDDDDD"}

{5, 7}
{2, 2}
Returns: 6
This can be achieved by the following keystrokes in the given order: home, top, down, down, right, right.
1)

{"A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB",
 "CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CC",
 "DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD ",
 "EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EE",
 "FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF ",
 "GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GG",
 "HHHHHHHHHHH HHHHHHHHHH HHHHHHHHHH HHHHHHHHHH HHHHH",
 "IIIIIIIIIIIIIII IIIIIIIIIIIIIII IIIIIIIIIIIIIII   ",
 "JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJ",
 "KKKKKKKKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKKKKK",
 "LLLLLLLLLL LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL",
 "MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
 "N N N N N N N N N N N N N N N N N N N N N N N N N ",
 "OOOOO OOOO OOO OO O O OO OOO OOOO OOOOO OOOOOO OOO",
 "PPPPPPP PPPPPP PPPPP PPPP PPP PP P P PP PPP PPPP P",
 "QQQQQQ QQQQQ QQQQ QQQ QQ Q Q QQ QQQ QQQQ QQQQQ QQQ",
 "ZZZZ ZZ ZZZ ZZ ZZZZ ZZ ZZZ ZZ ZZZZ ZZ ZZZ ZZ ZZZZ ",
 "SSS S SSS S SSS S SSS S SSS S SSS S SSS S SSS S SS",
 "TT TT TT TT TT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT"}

{12, 20}
{4, 36}
Returns: 8

2)

    
{"A A A A AAAAAAA A A A A A A A A A A",
 "B BBBBB B B B B BBBBB B B B B B B B B"}

{1, 0}
{1, 22}
Returns: 6

3)

{"AAAAAAAAAAAAAA A A A A A A A A A A"}

{0, 2}
{0, 15}
Returns: 1

4)

  
{"A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "N N N N N N N N N N N N N N N N N N N N N N N N N ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 " O O O O O O O O O O O O OO O O O O O O O O O O O ",
 " P P P P P P P P P P P P P PP P P P P P P P P P P ",
 " Q Q Q Q Q Q Q Q Q Q Q Q Q Q QQ Q Q Q Q Q Q Q Q Q ",
 " R R R R R R R R R R R R R R R RR R R R R R R R R ",
 " S S S S S S S S S S S S S S S S SS S S S S S S S ",
 " T T T T T T T T T T T T T T T T T TT T T T T T T ",
 " U U U U U U U U U U U U U U U U U U UU U U U U U ",
 " V V V V V V V V V V V V V V V V V V V VV V V V V ",
 " W W W W W W W W W W W W W W W W W W W W WW W W W ",
 " X X X X X X X X X X X X X X X X X X X X X XX X X ",
 " Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y YY Y ",
 " Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z ZZZ"}

{49, 49}
{38, 26}
Returns: 23

5)


{"AAA", "BB", "CCC"}
{1, 1}
{1, 1}
Returns: 0

6)

{"AAAAA AAA AAAAAAAAAAAAA  AAAA",
 "AA   AAAAAAAAA AAAA     AAAA",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBB BBBBBBBBBB BBBBBBB",
 "CCC CCCC CCCCCC      CCCC",
 "DDDDDDDDDDDDDDDDDDD"}

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

7)

{"A PC to do CAD huh  Sounds reasonable",
 "Aurthor go out and buy us five new PCs",
 "Dont you want to think about this for a minute",
 "No every second counts and we want to be ahead of",
 "the competition",
 "       OK Greate idea Please place lOOk worth of",
 "unmarked bills in my suitcase and Ill be on my way"}

{0, 11}
{1, 15}
Returns: 2

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.

[rox_rook]

Bài 3 coi dài vậy chứ mình nghĩ cũng không khó, giải thuật mình nghĩ là duyệt theo chiều rộng BFS, dễ thấy từ 1 điểm trên ma trận ta có tất cả 7 lựa chọn đi tới các điểm khác :
1.Trái
2.Phải
3.Dưới
4.Trên...
Cộng thêm mấy cái điều kiện lặt vặt thì ta cũng thêm vào bình thường thui.
Vậy từ 1 điểm cho trước ta có 7 bước move - sang 1 điểm nào đó, vậy mỗi lần duyệt đẩy nó vào hàng đợi rùi đánh dấu từ điểm đó chạy qua điểm khác..., bài toán trở về bài toán cực kì đơn giản duyệt các đỉnh tìm đường đi ngắn nhất trên đồ thị . Bạn nào có idea khác thì chúng ta cùng bàn nhé, đang trong tuần chắc chưa có cơ hội để cài đặt thử, hẹn cuối tuần vậy hì hì !

[Xcross87]

Bài 1 đơn giản.
Xin phép đưa đáp án = C

/** * calculate size of actual TV * @param *      input: const int[] (3-element array includes -diagonal_size -height_ratio -width_ratio) * @return       *      output: int* (reference the result, 2-element array includes -actual_height -actual_width) */ int calcSize(const int[] input, int* output) {    // assign easy-to-read variables    int D = input[0], h = input[1], w = input[2];    double H, W;        if(h < w)        return 0;     H = (D * h) / sqrt(w * w + h * h);    W = (D * w) / sqrt(w * w + h * h);    *(output) = H;    *(output + 1) = W;    return 1;}

Đáp án = PHP

function calcSize($D, $h, $w) {    
    $H = ($D * $h) / sqrt($w * $w + $h * $h);
    $W = ($D * $w) / sqrt($w * $w + $h * $h);
    $result = array(floor($H), floor($W));
    return $result;
} 

[zxc]

Tui thì thích giải thuật hơn code. mới chỉ đọc qua bài 3.
@rox_rook: bài 3 tôi nghĩ không đơn giản vậy. nếu bàn phím chỉ có 4 nut đó thì không nói làm gì. nhưng bàn phìm còn có home, end, word_left, word_right. ngoài ra, khi dùng bottom và top, không hẳn là columns không thay đổi, nếu như columns hiện tại đang lớn hơn chiều dài của hàng phía trên hoặc phía dưới thì khi di chuyển không thể duy tri columns cũ được.

ví dụ:

AAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
A A A A A A A A A A A A A A A A A A A A A A A  A A

Hiện tại ta đang ở vị trí {20, 1} cần di chuyển đến vị trí {9, 2}
thì tôi nghĩ cách nhanh nhất là top, down, down

[rox_rook]

- Sorry cậu zxc, tối qua 7h sáng mới ngủ T_T, bên đây holiday. Hồi này có vào mà mắt mở không lên.
- Còn bài này thì thật sự tui cũng chưa cài đặt, từ hồi tết 9 tháng rùi T_T, còn giải thuật thì tui nghĩ thực sự BFS sẽ work trong trường hợp này. Cậu có ý kiến gì thì đưa lên cùng thảo luận. Có gì tui sẽ cố cài đặt thử xem sao !

[zxc]

BFS thì chắc chắn sẽ hoạt động. Nhưng làm tìm kiếm mà dùng BFS thì hơi chán, còn heuristic thì quả thật không nghĩ ra cách tính nào cho nó phù hợp cả. Hic, vào học kỳ mới mất rồi, nhìn đề cương mấy môn học sợ "vãi linh hồn", chắc từ nay không có thời gian để tìm hiểu với mấy cậu được. Chúc làm bài zui zẻ.

[Xcross87]

Quay lại series TopCoder bị hoang tàn bấy lâu nay.
Giờ X câu nó trở lại để mọi người cùng luyện code + luyện cấu trúc dữ liệu giải thuật.

Các ngôn ngữ sử dụng: C, C++, C++.Net, C#

Bài 2:


Problem Statement

***Note: Please keep programs under 7000 characters in length. Thank you


Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int

Define the function S(x) as the sum of the squares of the digits of x.
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.

Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x. That is: S(x), S(S(x)), S(S(S(x))), etc...
For example, repeatedly applying S to 37:
S(37)=3*3+7*7=58.
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42.
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37.
Note this sequence will repeat so we can stop calculating now and:
T(37)={58,89,145,42,20,4,16,37}.
However, note T(x) may not necessarily contain x.

Implement a class SquareDigits, which contains a method smallestResult. The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.

The method signature is (be sure your method is public):
int smallestResult(int n);

TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.

Examples:
If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.

If n=2: T(0) through T(10) do not contain the value 2. If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.

If n=10: T(0) through T(6) do not contain 10. If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat...
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.

n=1 -> x=1
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666
Definition

Class:
SquareDigits
Method:
smallestResult
Parameters:
int
Returns:
int
Method signature:
int smallestResult(int param0)
(be sure your method is public)


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.

[6220119]

brute force solution ...
n = 184 thì x= 12779 ...

#include<map>#include<iostream> class SquareDigits{public:    static int smallestDigits(int);    static int S(int);    static bool isContain(int,const int&);}; int SquareDigits::S(int x){    int r=0;    while(x!=0)    {        r+=(x%10)*(x%10);        x/=10;    }    return r;} bool SquareDigits::isContain(int n, const int &x){    std::map<int,int> T;    while(1)    {        int key ,val;        key = n;        val = S(key);        if(x==val)            return true;        n=val;              if(T[key]==val)            break;        T[key]=val;    }    return false;} int SquareDigits::smallestDigits(int n){    if(n==0)        return n;     for(int s=1;;++s)//brute force ...        if(isContain(s,n))            return s;    return -1;//never reach ...}  int main(){    std::cout<<"n\tx\n";    for(int i=0;i<200;++i)        std::cout<<i<<"\t"<<SquareDigits::smallestDigits(i)<<"\n";    _getch();    return 0;}