태터데스크 관리자
Posted by EHXM. Posted in " 경험/알고리즘 "2009/10/27 12:09
The 30th Annual ACM International Collegiate
Programming Contest ASIA Regional - Seoul
Problem A
Score
There is an objective test result such as “OOXXOXXOOO”. An ‘O’ means a correct answer of a problem and
an ‘X’ means a wrong answer. The score of each problem of this test is calculated by itself and its just
previous consecutive ‘O’s only when the answer is correct. For example, the score of the 10th problem is 3
that is obtained by itself and its two previous consecutive ‘O’s.
Therefore, the score of “OOXXOXXOOO” is 10 which is calculated by “1+2+0+0+1+0+0+1+2+3”.
You are to write a program calculating the scores of test results.
Input
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is
given in the first line of the input. Each test case starts with a line containing a string composed by ‘O’ and
‘X’ and the length of the string is more than 0 and less than 80. There is no spaces between ‘O’ and ‘X’.
Output
Your program is to write to standard output. Print exactly one line for each test case. The line is to contain the
score of the test case.
The following shows sample input and output for five test cases.
Sample Input
5
OOXXOXXOOO
OOXXOOXXOO
OXOXOXOXOXOXOX
OOOOOOOOOO
OOOOXOOOOXOOOOX
Output for the Sample Input
10
9
7
55
30
여러분의 커뮤니케이션을 기다리고 있습니다.
Posted by EHXM. Posted in " 경험/알고리즘 "2009/10/26 01:56
With a growing desire for modernization in our increasingly larger cities comes a need for new street designs. Chris is one of the unfortunate city planners responsible for these designs. Each year the demands keep increasing, and this year he has even been asked to design a completely new city.
More work is not something Chris needs right now, since like any good bureaucrat, he is extremely lazy. Given that this is a character trait he has in common with most computer scientists it should come as no surprise that one of his closest friends, Paul, is in fact a computer scientist. And it was Paul who suggested the brilliant idea that has made Chris a hero among his peers: Fractal Streets! By using a Hilbert curve, he can easily fill in rectangular plots of arbitrary size with very little work.
A Hilbert curve of order 1 consists of one “cup”. In a Hilbert curve of order 2 that cup is replaced by four smaller but identical cups and three connecting roads. In a Hilbert curve of order 3 those four cups are in turn replaced by four identical but still smaller cups and three connecting roads, etc. At each corner of a cup a driveway (with mailbox) is placed for a house, with a simple successive numbering. The house in the top left corner has number 1, and the distance between two adjacent houses is 10 m.
The situation is shown graphically in figure 2. As you can see the Fractal Streets concept successfully eliminates the need for boring street grids, while still requiring very little effort from our bureaucrats.
(a) Order 1 (b) Order 2 (c) Order 3
Figure 2: Hilbert curves of order 1, 2 and 3, with the location of the houses indicated.
As a token of their gratitude, several mayors have offered Chris a house in one of the many new neighborhoods built with his own new scheme. Chris would now like to know which of these offerings will get him a house closest to the local city planning office (of course each of these new neighborhoods has one). Luckily he will not have to actually drive along the street, because his new company “car” is one of those new flying cars. This high-tech vehicle allows him to travel in a straight line from his driveway to the driveway of his new office. Can you write a program to determine the distance he will have to fly for each offer (excluding the vertical distance at takeoff and landing)?
On the first line of the input is a positive integer, the number of test cases. Then for each test case:
• A line containing a three positive integers, n< 16 and h,o < 231, specifying the order of the Hilbert curve, and the house numbers of the offered house and the local city planning office.
For each test case:
• One line containing the distance Chris will have to fly to his work in meters, rounded to the nearest integer.
Exampl
e
typedef struct{
int x;
int y;
}point;
point solve(long order,long num){
if(order == 1){
point a;
if(num == 1){
a.x = 1;
a.y = 1;
}
else if(num == 2){
a.x = 2;
a.y = 1;
}
else if(num == 3){
a.x = 2;
a.y = 2;
}
else if(num == 4){
a.x = 1;
a.y = 2;
}
return a;
}
long div = pow(2.0,2*(order-1));
FOR(i, 4){
if(num <= (i+1)*div){
if(i==0){
point tmp = solve(order-1, div - (num-i*div-1));
long double dx = (pow(2.0,order-1)+1)/2.0;
long double dy = dx;
long double cx = tmp.x - dx;
long double cy = dy - tmp.y;
long double fx = cy;
long double fy = -cx;
tmp.x = dx + fx;
tmp.y = dy - fy;
return tmp;
}
else if(i==1){
point tmp = solve(order-1, num-i*div);
tmp.x = tmp.x + pow(2.0,order-1);
return tmp;
}
else if(i==2){
point tmp = solve(order-1, num-i*div);
tmp.x = tmp.x + pow(2.0,order-1);
tmp.y = tmp.y + pow(2.0,order-1);
return tmp;
}
if(i==3){
point tmp = solve(order-1, div - (num-i*div-1));
long double dx = (pow(2.0,order-1)+1)/2.0;
long double dy = dx;
long double cx = tmp.x - dx;
long double cy = dy - tmp.y;
long double fx = -cy;
long double fy = cx;
tmp.x = dx + fx;
tmp.y = dy - fy;
tmp.y = tmp.y + pow(2.0,order-1);
return tmp;
}
}
}
}
int main(){
int testCase;
cin >> testCase;
FOR(testi, testCase){
long o,a,b;
cin >> o >> a >> b;
point pa = solve(o,a);
point pb = solve(o,b);
long double tmp = (pa.x-pb.x)*(pa.x-pb.x)+(pa.y-pb.y)*(pa.y-pb.y);
long result = (long)(sqrt(tmp)*10+0.5);
cout << result << endl;
}
return 0;
}
여러분의 커뮤니케이션을 기다리고 있습니다.
Posted by EHXM. Posted in " 경험/알고리즘 "2009/06/06 22:12
Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the IQ's are decreasing.
The input will consist of data for a bunch of elephants, one elephant per line, terminated by the end-of-file. The data for a particular elephant will consist of a pair of integers: the first representing its size in kilograms and the second representing its IQ in hundredths of IQ points. Both integers are between 1 and 10000. The data will contain information for at most 1000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.
Say that the numbers on the i-th data line are W[i] and S[i]. Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing an elephant). If these n integers are a[1], a[2],..., a[n] then it must be the case that
W[a[1]] < W[a[2]] < ... < W[a[n]]and
S[a[1]] > S[a[2]] > ... > S[a[n]]In order for the answer to be correct, n should be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.
6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900
4 4 5 9 7
DP로 풀었음.
W에 대해서 정렬후
if(W[i]>W[j] && S[i]<S[j]) len[j] = (Maxlen[j] + 1);
else len[j] = Maxlen[j];
Maxlen[i] = Max(len[j])
0 < i < n, 0 < j < i
헤더생략..
class piii{
public:
int num;
int W;
int S;
};
bool inputCompare(piii a, piii b){
if( a.W == b.W ){
return a.S > b.S;
}
return a.W < b.W;
}
int main(){
//input
freopen("bs.in","r",stdin);
freopen("bs.out","w",stdout);
string inputLine="";
vector inputData;
int inputCount=1;
piii tmp;
while(cin >> tmp.W && cin >> tmp.S){
tmp.num = inputCount++;
inputData.push_back(tmp);
}
sort(ALL(inputData), inputCompare);
//dp
int max_len[1000];
int prev[1000];
int max =0;
int max_pos = 0;
FOR(k, inputData.size()){
max_len[k] = 1;
prev[k] = 0;
FOR(j, k){
if(inputData[j].S > inputData[k].S){
if(inputData[j].W < inputData[k].W){
if(max_len[j] + 1 > max_len[k]){
max_len[k] = max_len[j]+1;
prev[k] = j;
if(max <= max_len[k]){
max = max_len[k];
max_pos = k;
}
}
}
}
}
}
//tracking
cout << max << endl;
stack solution;
int i = max_pos;
while(i>0){
solution.push(i);
i = prev[i];
}
while(solution.size() != 0){
cout << inputData[solution.top()].num << endl;
solution.pop();
}
return 0;
}
여러분의 커뮤니케이션을 기다리고 있습니다.
아이디어의 전쟁의 현장이었던 2010년 대한민국 매쉬업 경진대회에 다녀왔습니다. 이번 대회는 지난 2월 6일(토요일), 삼성동 코엑스 컨퍼런스룸 401에서 열렸습니다. 이번.....
2010년에 100가지가 넘는 안드로이드 폰 출시가 될 예정입니다. Mobile World Congress keynote에서 Google CEO Eric Schmidt의 연설.....
서울, 안양, 부산, 대구, 광주, 대전에 안드로이드 폰 체험 할 수 있는 곳이 있네요. 저는 코엑스 메가박스 입구에 있는 모토로라 체험 부스에서 우연히 모토로이를 만져보게 되.....
위 3D 갤러리는 http://www.fotoviewr.com/ 사이트의 Fotoviewr 입니다. Flex와 Papervision3D를 이용하여 위와같은 3D 갤러리를 구현해.....
|
Total : 115,866 Today : 222 Yesterday : 155
![[안드로이드] 영어 어학기 어플](http://cfile21.uf.tistory.com/image/206A8B274BEA66644AFA79)
![[안드로이드] 모토로이 체험할 수 있는 곳 (전국)](http://cfile25.uf.tistory.com/image/1252D6274B7028995911EC)
Posted by 우욱2010/02/15 18:08
넘 쉬운데요.. 진짜 ACM 문제 맞나요? -_-;;
<html>
<head>
<title>sol 30'th ACM prob. A</title>
<script type="text/javascript">
function calc_score()
{
var given_str = document.getElementById( 'inStr' ).value;
var sum = 0;
var sub_sum = 0;
for( var ii = 0; ii < given_str.length; ii++ )
{
var cur_char = given_str.substr( ii, 1 );
if( 'O' == cur_char )
{
sub_sum++;
sum += sub_sum;
}
else
{
sub_sum = 0;
}
}
document.getElementById( 'rst' ).value = sum;
}
</script>
<head>
<body>
<input type="text" id="inStr" />
<input type="button" onclick="javascript:calc_score();" value="calc" /><br />
<input type="text" id="rst" readonly="true" />
</body>
</html>
수정/삭제 댓글쓰기
네.. 첫문제는 보통 몸풀기죠 ㅎ
수정/삭제