#include <iostream> #include <stdlib.h> #include <time.h> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int a[100000],n; int quick(int low,int high){ int m,i,j,t,pivot; if(high-low>5) m=low+rand()%(high-low+1); else m=(int)((low+high)/2); pivot=a[m]; if(low < high){ i=low-1; j=high+1; while(1){ do{ i++; }while(pivot>a[i]); do{ j--; }while(pivot<a[j]); if(i>j) break; else{ t=a[i]; a[i]=a[j] ; a[j]=t; } } } return m; } main(){ int i,k,low,high,s; srand(time(NULL)); fin >> n; for(i=0;i<n;i++) fin >> a[i]; low=0; high=n-1; s=int(n*0.2+0.5); while(1){ k=quick(low,high); int m,i,j,t,pivot; if(high-low>5) m=low+rand()%(high-low+1); else m=(int)((low+high)/2); pivot=a[m]; if(low < high){ i=low-1; j=high+1; while(1){ do{ i++; }while(pivot>a[i]); do{ j--; }while(pivot<a[j]); if(i>j) break; else{ t=a[i]; a[i]=a[j] ; a[j]=t; } } } if(m==n-s) break; else if(m>n-s) high=m-1; else low=m+1; } fout << a[n-s] << endl; }
Algorithm
- 퀵소트-파레토의법칙 2009.07.29
- 하노이의 탑 2009.07.29
- 10189, Minesweeper 2008.10.16
- 102, Ecological Bin Packing 2008.10.15
- 101, The Blocks Problem 2008.10.15
- 100, The 3n + 1 problem 2008.10.15 2
- ACM-ICPC 본선진출 !!! 2008.09.30
퀵소트-파레토의법칙
하노이의 탑
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int cnt; void hanoi(int n,char a,char b,char c){ cnt++; if(n>0){ hanoi(n-1,a,b,c); cout << n << "번째 판을"<< a << " ---> " << c << endl; hanoi(n-1,b,a,c); } } main(){ int n; cnt=0; n=3; hanoi(n,'A','B','C'); printf("%d\n",cnt); } /* //다른방법 int m=0; void hanoi(int n,int a,int b){ if(n>0){ hanoi(n-1,a,6-a-b); m++; cout << m << "번째 판을"<< a << " ---> " << b << endl; hanoi(n-1,6-a-b,b); } } main(){ int n; n=3; hanoi(n,1,3); } */
10189, Minesweeper
쉬운문제부터 공략하자 ~! ㅋ
아무래도 UVA중에 가장 쉬운 문제라고 생각한다. ㅎ
초보인 나에게 이러한 문제는 정말 반갑기 그지없다 ~~ ㅎ
출력때문에 황당했지만 ㅠ
#include <stdio.h>
int x[8]={-1,0,1,1,1,0,-1,-1};
int y[8]={1,1,1,0,-1,-1,-1,0};
int n,m;
char mine[100][100];
int minesweeper(int mx,int my){
int i,cnt=0;
for(i=0;i<8;i++){
if(mx+x[i] > -1 && mx+x[i] < n && my+y[i] > -1 && my+y[i] < m){
if(mine[mx+x[i]][my+y[i]]=='*')
cnt++;
}
}
return cnt;
}
int main(){
int i,j,minecnt,programcnt=0;
char buffer;
n=m=1;
while(n!=0 && m!=0){
scanf("%d %d",&n,&m);
scanf("%c",&buffer);
if(n==0 && m==0)
break;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%c",&mine[i][j]);
}
scanf("%c",&buffer);
}
if(programcnt==0)
printf("Field #%d:\n",++programcnt);
else
printf("\nField #%d:\n",++programcnt);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(mine[i][j]=='*')
printf("%c",mine[i][j]);
else{
minecnt=minesweeper(i,j);
printf("%d",minecnt);
}
}
printf("\n");
}
}
return 0;
}
102, Ecological Bin Packing
나같이 초보인 사람에게는 연습문제 같은 좋은 문제 ㅎㅎㅎ
101, The Blocks Problem
100, The 3n + 1 problem
100 | The 3n + 1 problem |
UVA에서 처음 풀어본 문제...
int로 계속하다가 연이은 WA.. ㅠ
간단한건데 시간만 조넨 낭비한 느낌...
동적으로도 나중에 풀어봐야지 ^^
ACM-ICPC 본선진출 !!!
예선 38등 !!!
본선진출이 목표였는데,,, 막상 본선진출을 확정지으니 더 걱정된다. ㅎㅎ
꼭 입상해서 NHN, 넥슨... 둘 중 하나라도 붙었으면 ㅎ
열심히 해야겠군 ㅋㅋ