태터데스크 관리자
Posted by EHXM. Posted in " 경험/알고리즘 "2009/10/27 12:13
The 30th Annual ACM International Collegiate
Programming Contest ASIA Regional -Seoul
Problem B
Digit Generator
For a positive integer N, the digit-sum of N is defined as the sum of N itself and its digits. When M is the digit-
sum of N, we call N a generator of M.
For example, the digit-sum of 245 is 256(= 245 + 2+ 4+ 5). Therefore, 245 is a generator of
256.
Not surprisingly, some numbers do not have any generators and some numbers have more than one generator.
For example, the generators of 216are 198and 207.
You are to write a program to find the smallest generator of the given integer.
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 takes one line containing an integer N,1 ≤
N ≤
100,000.
Output
Your program is to write to standard output. Print exactly one line for each test case. The line is to contain a
generator of N for each test case. If N has multiple generators, print the smallest. If N does not have any
generators, print 0.
The following shows sample input and output for three test cases.
Sample Input
3
216
121
2005
Output for the Sample Input
198
0
1979
여러분의 커뮤니케이션을 기다리고 있습니다.
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 우욱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>
여러분의 커뮤니케이션을 기다리고 있습니다.
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;
}
여러분의 커뮤니케이션을 기다리고 있습니다.
Posted by EHXM. Posted in " 경험/알고리즘 "2009/06/06 21:57
Judge status:
| 2007-04-20 03:43:06 | Accepted | 0.002 | Minimum | EHXM | C++ | 132 Bumpy Objects |
| Bumpy Objects |
Consider objects such as these. They are polygons, specified by the coordinates of a centre of mass and their vertices. In the figure, centres of mass are shown as black squares. The vertices will be numbered consecutively anti-clockwise as shown.
An object can be rotated to stand stably if two vertices can be found that can be joined by a straight line that does not intersect the object, and, when this line is horizontal, the centre of mass lies above the line and strictly between its endpoints. There are typically many stable positions and each is defined by one of these lines known as its base line. A base line, and its associated stable position, is identified by the highest numbered vertex touched by that line.
Write a program that will determine the stable position that has the lowest numbered base line. Thus for the above objects, the desired base lines would be 6 for object 1, 6 for object 2 and 2 for the square. You may assume that the objects are possible, that is they will be represented as non self-intersecting polygons, although they may well be concave.
Successive lines of a data set will contain: a string of less than 20 characters identifying the object; the coordinates of the centre of mass; and the coordinates of successive points terminated by two zeroes (0 0), on one or more lines as necessary. There may be successive data sets (objects). The end of data will be defined by the string '#'.
Output will consist of the identification string followed by the number of the relevant base line.
Object2
4 3
3 2 5 2 6 1 7 1 6 3 4 7 1 1 2 1 0 0
Square
2 2
1 1 3 1 3 3 1 3 0 0
#
Object2 6
Square 2
line object class
class line{
public:
line(int verNum1, float x1, float y1,int verNum2, float x2, float y2);
bool isVertexIn(float x1, float y1, float x2, float y2);
bool isVertexIn(float x1, float y1);
float pstCheck(float _x, float _y);
float _pstCheck(float line_X, float line_Y, float _x, float _y);
void addVertex(int verNum, float _x, float _y);
bool checkMass(float mass_X, float mass_Y);
int ID();
//line 두vertex로 이루어진 line 생성
//isVertexIn if the two vertex on the extension of line
//isVertexIn if the vertex in the line
//pstCheck 직선에서의 점의 위치(음수, 0, 양수)
//_pstCheck 수직한 line_X,line_Y를 지나는 직선에서의 _x, _y 점의 위치(음수, 0, 양수)
//addVertex add the vertex on the line
//checkMass mass가 line의 끝점 사이에 있는지 check
private:
int lineID; // line의 identifier, vertex 중 가장 큰 번호
float vertex[1000][2]; // line에 포함되는 vertex
int numOfVertex;
float dx, dy;
};
BumpyObject class
class lineList{
public:
string objectName;
float mass_X, mass_Y;
lineList();
~lineList();
int getBaseLine();
void addLine(int verNum1, float x1, float y1, int verNum2, float x2, float y2);
void addVertex(float x1, float y1);
void makeLine();
void checkInter();
// objectName 범피의 object Name
// mass 범피의 mass 좌표
// getBaseLine object의 line에서 가장작은 base line의 ID를 리턴
// addVertex object를 이루는 vertex의 좌표
// makeLine 두 vertex이루어진 line을 모두 생성한다.
// checkInter if line intersects the object.
private:
line *listElement[1000]; // 두 vertex로 이루어진 모든 line
bool inter_Flag[1000]; // line의 intersection check flag
int numOfElement;
float lineVertex[2000][2]; // object를 이루는 vertex
int numOfVertex;
};
cin >> _X2 >> _Y2;
while(_X2!=0 || _Y2!=0){
baseLine.addVertex(_X2,_Y2);
cin >> _X2 >> _Y2;
}
baseLine.makeLine();
cout << baseLine.objectName << baseLine.getBaseLine() << endl;
cin >> objectID;
}
return 0;
}
class 구현
lineList::lineList(){
numOfElement=0;
numOfVertex=0;
}
lineList::~lineList(){
int i=0;
for(i=0; i<numOfElement; i++){
delete listElement[i];
}
}
void lineList::addLine(int verNum1, float x1, float y1, int verNum2, float x2, float y2){
int i=0;
for(i=0; i<numOfElement; i++){
if( listElement[i]->isVertexIn(x1, y1, x2, y2) ){ //이미있는 line의 수평선에 두점이 포함되면
// 그 line에 없는 vertex만 추가한다.
if(!listElement[i]->isVertexIn(x1,y1))
listElement[i]->addVertex(verNum1, x1, y1);
if(!listElement[i]->isVertexIn(x2,y2))
listElement[i]->addVertex(verNum2, x2, y2);
return;
}
}
// 두점을 포함하는line이 없으면 line을 생성하여 object에 추가
listElement[numOfElement++] = new line(verNum1, x1, y1, verNum2, x2, y2);
}
void lineList::addVertex(float x1, float y1){
//vertex 추가
lineVertex[numOfVertex][0] = x1;
lineVertex[numOfVertex++][1] = y1;
}
void lineList::makeLine(){
for(int i=0; i<numOfVertex-1; i++){
for(int j=i+1; j<numOfVertex; j++){
//object를 이루는 모든 두 vertex으로 addLine을 call
addLine(i+1, lineVertex[i][0], lineVertex[i][1], j+1, lineVertex[j][0], lineVertex[j][1] );
}
}
}
void lineList::checkInter(){
for(int i=0; i<numOfElement; i++){
inter_Flag[i]=false;
int k=0;
float flag=0;
while(flag==0){
flag = listElement[i]->pstCheck(lineVertex[k][0], lineVertex[k][1]);
k++;
}
for(int j=k+1; j<numOfVertex; j++){
//object의 vertex중 위 치가 다른점이 있으면 flag를 true
if( flag * (listElement[i]->pstCheck(lineVertex[j][0], lineVertex[j][1]))<0){
inter_Flag[i]=true;
break;
}
}
}
}
int lineList::getBaseLine(){
int minNum=10000;
checkInter(); //intersection여부 체크
for(int i=0; i<numOfElement; i++){
//intersection 되지 않고, mass가 선분의 끝점 사이에 있는 line중 최소를 minNum에 assign
if( minNum > listElement[i]->ID() && inter_Flag[i]==false && listElement[i]->checkMass(mass_X, mass_Y))
minNum = listElement[i]->ID();
}
return minNum;
}
//
// line class
int line::ID(){
return lineID;
}
line::line(int verNum1, float x1, float y1,int verNum2, float x2, float y2){
vertex[0][0]=x1;
vertex[0][1]=y1;
vertex[1][0]=x2;
vertex[1][1]=y2;
dx = x2-x1;
dy = y2-y1;
if(verNum1 > verNum2)
lineID = verNum1;
else
lineID = verNum2;
numOfVertex=2;
}
float line::pstCheck(float _x, float _y){
return dy* ( _x - vertex[0][0]) - dx* ( _y - vertex[0][1]);
}
float line::_pstCheck(float line_X, float line_Y, float _x, float _y){
return dy* ( _y - line_Y) + dx* ( _x - line_X);
}
bool line::checkMass(float mass_X, float mass_Y){
for(int i=0; i<numOfVertex-1; i++){
for(int j=i+1; j<numOfVertex; j++){
//line에 수직하고 끝점 사이의 평면에 mass가 있으면 return true
if( _pstCheck( vertex[i][0], vertex[i][1], mass_X, mass_Y )
* _pstCheck( vertex[i][0], vertex[i][1], vertex[j][0], vertex[j][1] ) >= 0 ){
if( _pstCheck( vertex[j][0], vertex[j][1], mass_X, mass_Y )
* _pstCheck( vertex[j][0], vertex[j][1], vertex[i][0], vertex[i][1] ) >= 0 ){
return true;
}
}
}
}
return false;
}
bool line::isVertexIn(float x1, float y1, float x2, float y2){
int i=0;
int flag=0;
/*
for(i=0; i<numOfVertex; i++){
if(vertex[i][0]==x1 && vertex[i][1]==y1)
flag++;
else if(vertex[i][0]==x2 && vertex[i][1]==y2)
flag++;
if(flag >=2)
return true;
}
*/
if( pstCheck(x1, y1) == 0){
if( pstCheck(x2, y2) == 0){
return true;
}
}
return false;
}
bool line::isVertexIn(float x1, float y1){
int i=0;
int flag=0;
for(i=0; i<numOfVertex; i++){
if(vertex[i][0]==x1 && vertex[i][1]==y1)
return true;
}
return false;
}
void line::addVertex(int verNum, float _x, float _y){
vertex[numOfVertex][0]=_x;
vertex[numOfVertex][1]=_y;
numOfVertex++;
if(verNum > lineID)
lineID = verNum;
}
// /line class
여러분의 커뮤니케이션을 기다리고 있습니다.
아이디어의 전쟁의 현장이었던 2010년 대한민국 매쉬업 경진대회에 다녀왔습니다. 이번 대회는 지난 2월 6일(토요일), 삼성동 코엑스 컨퍼런스룸 401에서 열렸습니다. 이번.....
2010년에 100가지가 넘는 안드로이드 폰 출시가 될 예정입니다. Mobile World Congress keynote에서 Google CEO Eric Schmidt의 연설.....
서울, 안양, 부산, 대구, 광주, 대전에 안드로이드 폰 체험 할 수 있는 곳이 있네요. 저는 코엑스 메가박스 입구에 있는 모토로라 체험 부스에서 우연히 모토로이를 만져보게 되.....
위 3D 갤러리는 http://www.fotoviewr.com/ 사이트의 Fotoviewr 입니다. Flex와 Papervision3D를 이용하여 위와같은 3D 갤러리를 구현해.....
|
Total : 126,963 Today : 91 Yesterday : 114
![[안드로이드] 영어 어학기 어플](http://cfile21.uf.tistory.com/image/206A8B274BEA66644AFA79)
![[안드로이드] 모토로이 체험할 수 있는 곳 (전국)](http://cfile25.uf.tistory.com/image/1252D6274B7028995911EC)
Posted by 우욱2010/02/15 17:49
저는 O(N) = log_10 N 으로 구해지는데, 혹시 더 빠르게도 가능한가요?
수정/삭제 댓글쓰기
저는 빨리풀려고 많은 생각은 안하고 아마 그냥 풀어서 N정도로 했던 것 같네요.
문제만 올려놓고 아직 정리를 못했네요.
이번에 공부하면서 풀었던 것을 다시 정리를 해봐야겠어요.
수정/삭제