首页 > ACM题库 > HDU-杭电 > hdu 2725 Rock Skipping[解题报告]hoj
2014
02-14

hdu 2725 Rock Skipping[解题报告]hoj

Rock Skipping

问题描述 :

As a member of the International Rock-Skipping League, you travel to a different lake each week and compete in a rock-skipping contest. The goal is to throw a rock so that it skips as many times as possible; the exact rules for determining the winner are given below. To make the competitions interesting, the IRSL often chooses lakes with logs, sandbars, and other obstacles. You are provided with a side-view, water-level "map" of the lake as shown in the top line of the example below. (The numbers 0..29 below the map are just for reference.) A period (".") indicates clear water, where a rock will skip; any other character indicates some kind of obstacle that will stop a rock.


...=...**..#...@....:.:.:..=..
______________________________
11111111112222222222
012345678901234567890123456789

You stand at the left end of the lake. You can throw a rock so that it lands at any position in the lake, and then skips at any fixed interval thereafter. So a throw can be defined as a pair (i,d), where i ≥ 0 is the initial landing position and d > 0 is the distance between skips. Note that d must be positive. The count of a throw is the number of times that it skips on the water. The length is the position of its last contact with either the water or an obstacle. To rank two distinct throws, use the following criteria, in order, until a winner is determined: count (highest wins); length (greatest wins); initial position (greatest wins); distance between skips (smallest wins).

For the map shown above, throw (27,2) hits the obstacle at position 27; it has count 0 and length 27. Throw (16,1) skips at positions 16, 17, 18, and 19, then hits the obstacle at position 20; it has count 4 and length 20, so it beats throw (27,2). Throw (2,7) skips at positions 2, 9, 16, and 23, then skips over the lake; it has count 4 and length 23, so it beats throw (16,1). Throw (1,4) skips at positions 1, 5, 9, 13, 17, 21, 25, and 29, then skips over the lake; it has count 8 and distance 29, and is the best possible throw for this lake.

输入:

The input consists of one or more lake maps, each 1�40 characters long and on a line by itself, followed by a line containing only "END" that signals the end of the input. Positions within a map are numbered starting with zero. Maps will only contain printable ASCII punctuation characters. A period indicates clear water and any other character indicates an obstacle.

输出:

The input consists of one or more lake maps, each 1�40 characters long and on a line by itself, followed by a line containing only "END" that signals the end of the input. Positions within a map are numbered starting with zero. Maps will only contain printable ASCII punctuation characters. A period indicates clear water and any other character indicates an obstacle.

样例输入:

...=...**..#...@....:.:.:..=..
.(+)
/^\.
*++&*
END

样例输出:

1 4
0 3
3 1
4 1

/* 
 * File:   main.cpp
 * Author: swordholy
 *
 * Created on 2011年4月13日, 下午2:55
 */

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <string>
using namespace std;
struct res
{
    int count,len,ip,sk;
    bool operator <(res & rhs) const
    {
        if (count<rhs.count) return true;
        if (count>rhs.count) return false;
        if (len<rhs.len) return true;
        if (len>rhs.len) return false;
        if (ip<rhs.ip) return true;
        if (ip>rhs.ip) return false;
        if (sk>rhs.sk) return true;
        return false;
    }
};
res ans,now;
int main(int argc, char** argv)
{
    char s[1005];
    int i,j,len,d;
    while(gets(s))
    {
        if (strcmp(s,"END")==0) break;
        len=strlen(s);
        ans.count=-1;
        for(i=0;i<len;i++)
            for(j=1;j<=len;j++)
        {
               
                now.ip=i;
                now.sk=j;
                now.count=0;            
                for(d=i;d<len;d+=j)
                {
                    if (s[d]!='.') break;
                    now.count++;
                }
                if (d>=len) d-=j;
                now.len=d;
                if (ans<now) ans=now;
        }
        cout<<ans.ip<<' '<<ans.sk<<endl;
       // cout<<ans.ip<<' '<<ans.sk<<' '<<ans.count<<' '<<ans.len<<endl;
    }
    return 0;
}

  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish