Trang 1 trên tổng số 13 12311... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 128 kết quả

Đề tài: Các đề bài từ Topcoder ( Problems 1-10 )

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Các đề bài từ Topcoder ( Problems 1-10 )

    Topder là nơi mà các cao thủ từ thuật toán đến design đến developer đều tụ hồi về đây. Nó có rất nhiều giải thưởng các loại, từ highschool cho đến professional.
    Bài tập của nó thì mình đã đọc qua, rất thực tế và có 1 số bài cũng không quá khó. Ở đó bài tập thường chia ra 3 level, level 1-2-3. Cấp độ 3 là trâu bò nhất T_T. Box này mình sẽ tập trung post những bài tập trong đó ra, và lưu ý mình sẽ không dịch lại mà để thẳng đề bằng Tiếng Anh. Có lẽ đầu tiên mình sẽ chọn những problems ở mức độ Highschool trước rùi nếu chung ta thấy qua dễ thì chúng ta sẽ move on to Algorithm luôn. Nhưng theo mình thấy có 1 số bài không phải dễ T_T. Các bạn đừng qua lo là tournament gì hết, những bài tập này đa số có đánh đố nhưng không đến nỗi như những kì thi quốc tế, nó dành cho lập trình viên ở đủ mọi trình độ. Nếu bạn là 1 người đam mê lập trình mà cảm thấy mình vẫn còn hơi yếu về thuật toán thì there it is T_T , những bài tập này là dành cho bạn.
    Có lẽ mình sẽ tìm cách chia lại level sao cho hợp lý, nhưng trước mắt mình sẽ post các bài từ vòng 1-16, 1-32 trước. rùi sau đó sẽ sắp xếp lại cho ổn định sau.
    Chú ý nếu bạn muốn tham gia thi đấu thì bạn phải đăng ký 1 nick, có hẹn h và có tài khoản account ở paypal hay đâu đó đễ lãnh giải thưởng, nó có rất nhiều mục thi đấu từ algorithm cho tới design rất và rất nhiều...bạn có thể đọc thêm chi tiết ở đây nhé
    Code:
    http://www.topcoder.com/tc
    Box này chúng ta sẽ cùng nhau thảo luận cách giải, và cùng nhau rèn luyện trước khi đủ sức để tham gia thi đấu với các cường quốc tin học như China và Poland T_T.( Top 1 là 1 thằng China cỡ 17t, hic hic ).
    Ngôn ngữ cài đặt chuẩn của trang này bao gồm : C++, Java, C#, VB và Python. Một lưu ý sẽ là không có C vì đa số mình có đọc đề thấy nó toàn bắt cài đặt bằng class, và object.
    Lưu ý box này không phải là box đánh đố mà là thảo luận, chúng ta sẽ hợp sức giải những bài này, đưa ra idea cũng như qua đó chúng ta sẽ rèn luyện tư duy luôn, 1 công 2 việc nhỉ hì hì. Và cuối cùng rất mong sự đóng góp nhiệt tình của các bạn.
    ps : Đối với ai đã vững giải thuật thì đây là cơ hội rèn luyện tuyệt vời và nâng cao trình độ.
    Đối với ai còn yếu giải thuật thì lại là 1 cơ hội tuyệt vời hơn để bắt đầu học giải thuật.
    Ở đây giải thuật theo mình chỉ là các bước để xử lý 1 vấn đề nào đó thôi, không có ai mới học mà tự biết hết được, chỉ có rèn luyện và rèn luyện thì dần chúng ta sẽ quen và tư duy sẽ nâng cao lên.

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài 1 đã được cao thủ Xcross nhà mình giải ra 1 cách thuyết phục, ngôn ngữ cài đặt là C#. Mình sẽ post lại cho các bạn tiện theo dõi và cùng tham gia nhé T_T.
    Bài 1

    Problem Statement

    Given an int low, an int high, and an int pow, return the sum of i^j, for all i between low and high, inclusive, and all j between 1 and pow, inclusive.
    Definition

    Class:
    PowSum
    Method:
    getSum
    Parameters:
    int, int, int
    Returns:
    int
    Method signature:
    int getSum(int low, int high, int pow)
    (be sure your method is public)


    Constraints
    -
    low will be between -100 and 100, inclusive.
    -
    high will be between low and 100, inclusive.
    -
    pow will be between 1 and 10, inclusive.
    -
    The return value will fit in a signed 32 bit datatype.
    Examples
    0)


    1
    3
    2
    Returns: 20
    1^1 + 2^1 + 3^1 + 1^2 + 2^2 + 3^2 =
    1 + 2 + 3 + 1 + 4 + 9 =
    20
    1)


    -12
    12
    9
    Returns: 1637738440
    Note that intermediate values may exceed the 32 bit restriction.
    2)


    -100
    100
    2
    Returns: 676700


    Lời giải cài đặt bằng C#
    PHP Code:
    class PowSum
    {
        public static 
    int GetSum(int lowint highint pow)
        {
            
    int cnt_powcnt_inc;
            
    int sum 0;
            
    // Raise the power 
            
    for (cnt_pow 1cnt_pow <= powcnt_pow++) 
                
    // Increase the counter
                
    for (cnt_inc lowcnt_inc <= highcnt_inc++)
                    
    // Add to sum
                    
    sum += (int)Math.Pow(cnt_inccnt_pow);
            
    // return sum
            
    return sum;
        }
    }  
    class 
    Program
    {
        public static 
    void Main()
        {
            
    int result_1 PowSum.GetSum(132);
            
    int result_2 PowSum.GetSum(-12129);
            
    int result_3 PowSum.GetSum(-1001002);

            
    string _out =  "GetSum(1   ,3  ,2) = {0} \n"
                           
    "GetSum(-12 ,12 ,9) = {1} \n"
                           
    "GetSum(-100,100,2) = {2} \n";
                
    Console.WriteLine(_out,result_1,result_2,result_3);
        }

    Đã được chỉnh sửa lần cuối bởi Xcross87 : 07-02-2008 lúc 09:35 AM.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Tiếp theo là bài 2, vòng 1-16 level 1, bà con cô bác đầu năm đầu tháng cùng giải nào
    Bài 2

    Problem Statement

    A speed radar is installed in a highway zone where the maximum speed limit is maxLimit mph, and the minimum speed limit is minLimit mph. Any reading that is strictly above or below this interval is an infringement.
    Periodically, the radar readings are analyzed to make sure that the sensors are working properly. It is assumed that most drivers obey speed limits, and therefore, the radar will be considered faulty if more than 10% of its readings are infringements.
    Given the radar readings over a period of time, return the average speed of all cars that are driving within the speed limits. If the radar is faulty, return 0.0.
    Definition

    Class:
    SpeedRadar
    Method:
    averageSpeed
    Parameters:
    int, int, int[]
    Returns:
    double
    Method signature:
    double averageSpeed(int minLimit, int maxLimit, int[] readings)
    (be sure your method is public)


    Notes
    -
    The returned value must be accurate to within a relative or absolute value of 1E-9.
    Constraints
    -
    maxLimit will be between 1 and 200, inclusive.
    -
    minLimit will be between 1 and maxLimit, inclusive.
    -
    readings will contain between 1 and 50 elements, inclusive.
    -
    Each element of readings will be between 1 and 200, inclusive.
    Examples
    0)


    1
    50
    {45, 40, 50}
    Returns: 45.0
    With all drivers within the speed limits, the return value is just the average speed.
    1)


    1
    50
    {42,43,44,45,46,47,48,49,50,51}
    Returns: 46.0
    There is only one driver infringing the limit, and it represents 10% of the total readings. The average speed of the other readings is 46.0.
    2)


    1
    50
    {42,46,48,50,52}
    Returns: 0.0
    Only one reading is outside the given limits, but it represents 20% of the total number of readings. We therefore assume that the radar is not working and return 0.0.
    3)


    20
    60
    {25,45,45,43,24,9,51,55,60,34,61,23,40,40,47,49,33 ,23,47,54,54}
    Returns: 41.68421052631579
    Đã được chỉnh sửa lần cuối bởi rox_rook : 07-02-2008 lúc 09:19 AM. Lý do: Nhầm Level T_T!

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài 3 là 1 bài về chuỗi, nhưng cũng không quá khó, level 1 only.

    Bài 3

    Problem Statement

    In written languages, some symbols may appear more often than others. Expected frequency tables have been defined for many languages. For each symbol in a language, a frequency table will contain its expected percentage in a typical passage written in that language. For example, if the symbol "a" has an expected percentage of 5, then 5% of the letters in a typical passage will be "a". If a passage contains 350 letters, then 'a' has an expected count of 17.5 for that passage (17.5 = 350 * 5%). Please note that the expected count can be a non-integer value.
    The deviation of a text with respect to a language frequency table can be computed in the following manner. For each letter ('a'-'z') determine the difference between the expected count and the actual count in the text. The deviation is the sum of the squares of these differences. Blank spaces (' ') and line breaks (each element of text is a line) are ignored when calculating percentages.
    Each frequency table will be described as a concatenation of up to 16 strings of the form "ANN", where A is a lowercase letter ('a'-'z') and NN its expected frequency as a two-digit percentage between "00" (meaning 0%) and "99" (meaning 99%), inclusive. Any letter not appearing in a table is not expected to appear in a typical passage (0%). You are given a String[] frequencies of frequency tables of different languages. Return the lowest deviation the given text has with respect to the frequency tables.
    Definition

    Class:
    SymbolFrequency
    Method:
    language
    Parameters:
    String[], String[]
    Returns:
    double
    Method signature:
    double language(String[] frequencies, String[] text)
    (be sure your method is public)


    Notes
    -
    The returned value must be accurate to within a relative or absolute value of 1E-9.
    Constraints
    -
    frequencies will contain between 1 and 10 elements, inclusive.
    -
    Each element of frequencies will be formatted as described in the statement.
    -
    Each element of frequencies will contain between 6 and 48 characters, inclusive.
    -
    No letter will appear twice in the same element of frequencies.
    -
    The sum of the percentages in each element of frequencies will be equal to 100.
    -
    text will contain between 1 and 10 elements, inclusive.
    -
    Each element of text will contain between 1 and 50 characters, inclusive.
    -
    Each element of text will contain only lowercase letters ('a'-'z') and spaces (' ').
    -
    text will have at least one non-space character.
    Examples
    0)


    {"a30b30c40","a20b40c40"}
    {"aa bbbb cccc"}
    Returns: 0.0
    The first table indicates that 30% of the letters are expected to be 'a', 30% to be 'b', and 40% to be 'c'. The second table indicates that 20% are expected to be 'a', 40% to be 'b', and 40% to be 'c'. We consider the text to have length 10, as blank spaces are ignored. With respect to the first table, there are 2 'a' where 3 were expected (a difference of 1), one more 'b' than expected (again a difference of 1) and as many 'c' as expected. The sum of the squares of those numbers gives a deviation of 2.0. As for the second table, the text matches expected counts exactly, so its deviation with respect to that language is 0.0.
    1)


    {"a30b30c40","a20b40c40"}
    {"aaa bbbb ccc"}
    Returns: 2.0
    Here we use the same tables as in the previous example, but with a different text. The counts for 'b' and 'c' each differ by 1 from the expected counts in the first table, and the counts for 'a' and 'c' each differ by 1 from the expected counts in the second table. The text has a deviation of 2.0 with respect to both tables.
    2)


    {"a10b10c10d10e10f50"}
    {"abcde g"}
    Returns: 10.8
    Here, each of the letters 'a' through 'e' is expected to make up 10% of the letters (0.6 letters). Each of those letters actually appears once, so the difference is 0.4, which becomes 0.16 when squared. 50% of the letters (3 letters) are expected to be 'f', but 'f' does not appear at all. The square of this difference is 9.0. No 'g's are expected to appear, but there is one in the text. This adds 1.0 to the deviation. The final deviation for this table is: 0.16+0.16+0.16+0.16+0.16+9.0+1.0=10.8.
    3)


    {"a09b01c03d05e20g01h01i08l06n08o06r07s09t08u07x01 "
    ,"a14b02c05d06e15g01h01i07l05n07o10r08s09t05u04x01 "}
    {"this text is in english"
    ,"the letter counts should be close to"
    ,"that in the table"}
    Returns: 130.6578
    These two frequency tables correspond (roughly) to the frequencies found in the English and Spanish languages, respectively. The English passage, as expected, has a lower deviation in the first table than in the second one.
    4)


    {"a09b01c03d05e20g01h01i08l06n08o06r07s09t08u07x01 "
    ,"a14b02c05d06e15g01h01i07l05n07o10r08s09t05u04x01 "}
    {"en esta es una oracion en castellano"
    ,"las ocurrencias de cada letra"
    ,"deberian ser cercanas a las dadas en la tabla"}
    Returns: 114.9472
    The same tables again, but with Spanish passage. This time the second table, which correspond to frequencies in Spanish, gives the lowest deviation.
    5)


    {"z99y01", "z99y01", "z99y01", "z99y01", "z99y01",
    "z99y01", "z99y01", "z99y01", "z99y01", "z99y01"}
    {"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aa",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a"}
    Returns: 495050.0
    Đã được chỉnh sửa lần cuối bởi rox_rook : 07-02-2008 lúc 09:20 AM.

  5. #5
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    Cho hỏi xí, làm oop chắc là được chứ ? nhc muốn chia nhỏ chương trình ra. Nếu làm oop thì format ko giống với đề lắm :-ss
    Keep moving forward!

    ... Retired ...

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Các đề bài từ Topcoder ( Problems 1-10 )

    Class:
    SymbolFrequency
    Method:
    language
    Parameters:
    String[], String[]
    Returns:
    double
    Method signature:
    double language(String[] frequencies, String[] text)
    (be sure your method is public)
    Cái đề nó yêu cầu vậy mà nhc, với lại đây là cấp độ highschool có làm thêm chắc nó cũng ko accpet. Mình nghĩ thế thôi còn chưa applied thử. Để tí nữa làm rùi accept thử xem sao

  7. #7
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    À nếu có làm thì chỉ là để lấy kinh nghiệm thôi, ko phải để apply

    Mấy bài trên khó quá, nhc làm ko ra
    Keep moving forward!

    ... Retired ...

  8. #8
    Ngày gia nhập
    09 2006
    Nơi ở
    /usr/share/.hack@
    Bài viết
    1,433

    Bài số 2:
    Hiểu như thế này:
    - Input: min, max, int[] readings
    - Output: Nếu trong readings
    a. Không có phần tử nằm ngoài min, max thì trả về average = sum / length;
    b. Có phần tử nằm ngoài min, max:
    + Nếu số lượng phần tử đó trên tổng số phần tử > 10% thì return 0;
    + Nếu <= 10% (no more than 10 %) thì return average;

    Đáp án của Xcross viết nháp chơi nè

    PHP Code:
            class SpeedRadar
            
    {
                public 
    double GetAverageSpeed(int minint maxint[] readings)
                {
                    
    // get sum
                    
    double sum = (double)GetSum(readings);                
                    
    // get average
                    
    double average sum / (double)readings.Length;
                    
    // get number of out-of-range elements
                    
    int _out_of_range CheckOutOfRange(minmaxreadings);
                    
    // no out-of-range value
                    
    if (_out_of_range == 0)
                        return 
    average;
                    
    // otherwise
                    
    else
                    {
                        
    // percent of elements
                        
    double percent = ((double)_out_of_range / (double)readings.Length) * 10;
                        
    // more than 10 percent
                        
    if (percent 1.0)
                            return 
    0.0;
                        
    // otherwise
                        
    else
                            return 
    average;
                    }
                }           

                
    // Get sum of an integer array
                
    private int GetSum(int[] numbers)
                {
                    
    int sum 0;
                    for (
    int cnt 0cnt numbers.Lengthcnt++)
                        
    sum += numbers[cnt];
                    return 
    sum;
                }

                
    // Check whether there is an out-of-range value
                
    private int CheckOutOfRange(int minint maxint[] readings)
                {
                    
    int cnt 0;
                    foreach (
    int element in readings)
                        if (
    element min || element max)
                            
    cnt++;                
                    return 
    cnt;
                }            
            }
        class 
    Program
        
    {
            public static 
    void Main()
            {   
                
    SpeedRadar calc = new SpeedRadar();
                
                
    double result_1 calc.GetAverageSpeed(150, new int[] { 454050 });
                
    double result_2 calc.GetAverageSpeed(150, new int[] { 42434445464748495051 });
                
    double result_3 calc.GetAverageSpeed(150, new int[] { 4246485052 });
                
    double result_4 calc.GetAverageSpeed(2060, new int[] { 25454543249515560346123404047493323475454 });

                
    string _out "Result 1 : (1,50,_45,40,50_) = {0} \n"
                    
    "Result 2 : (1,50,_42,43,44,45,46,47,48,49,50,51_) = {1} \n"
                    
    "Result 3 : (1,50,_42,46,48,50,52_) = {2} \n"
                    
    "Result 4 : (20,60,_25,45,45,43,24,9,51,55,60,34,61,23,40,40,47,49,33 ,23,47,54,54) = {3} ";
                
    Console.WriteLine(_outresult_1,result_2,result_3,result_4);            
            }
        } 


    None!

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Ặc, dạo này bác Xcross máu quá T_T. Chắc Xcross xử hết đống này luôn quá hì hì T_T. Pro quá ! Bác X chắc phải chơi với Level 3 thui ! Nãy h đâm đầu vô bài 3, tui chết nghoe luôn nè hu hu ! Lâu rùi không chơi với chuỗi lằng nhằng bà cố. X có idea gì cho bài 3 không ? Không ăn tết luôn hen !

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Chẳng hiểu làm sao convert kí tự của C++ string sang số được, quái thật, dùng C string thì ok rùi. X có biết cú pháp nào ví dụ :
    std::string ss = "13345";
    int x = atoi(ss[3]); nó không chịu :( hic hic !

    Hì hì static_cast được rùi T_T.
    Đã được chỉnh sửa lần cuối bởi rox_rook : 07-02-2008 lúc 01:57 PM.

Các đề tài tương tự

  1. Trả lời: 1
    Bài viết cuối: 06-10-2011, 08:11 PM
  2. Problems : " recover tree " with input as " preorder" and "inorder"
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 10:19 PM
  3. Bài Tập TopCoder (500 Point) Marth(491)
    Gửi bởi congaco90 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 04-01-2011, 12:12 PM
  4. Các bài tập từ Topcoder ( Problems 11-20 )
    Gửi bởi rox_rook trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 20-05-2010, 06:40 PM
  5. [TopCoder] Practice Rooms => 1-Tournament => 1-Inv 2001 R1
    Gửi bởi bvKim trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 03-02-2010, 11:20 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn