좌표평면에자연수좌표를갖는점하나로구성된집합 가주어진다. 에속하는점으로부터아래의세가지생성규칙중하나를적용하여새로운점을만들고, 그점을집합 에추가한다. 이과정을반복적으로수행하면, 매번새로운점을집합 에계속추가할수있다. ( 규칙 1) 점 가 에속해있다면, 점 을 에추가한다. ( 규칙 2) 점 가 에속해있고, 와 가모두짝수이면, 점 를 에추가한다. ( 규칙 3) 두점 와 가 에속해있다면, 점 를 에추가한다. 예를들어, 일때, 규칙 1을점 에적용하여만들어진점 을 에추가하면, 이된다. 다시점 에규칙 1을적용하면, 이된다. 다음에점 에규칙 2를적용하면 이된다. 또두점 와 에규칙 3을적용하면, 이된다. 문제는집합 를구성하는점 가주어질때, 이집합에위의세가지규칙을임의의순서로반복적용하여새로운점 가 에추가될수있는지를판명하는것이다. 실행파일의이름은 POINT.EXE로하고, 실행시간은 1초를넘을수없다. 부분점수는없다. 입력파일의이름은 INPUT.TXT이다. 첫째줄에는처음에 에속하는점 의좌표인두자연수 와 가하나의공백을두고순서대로주어진다. 그리고그다음다섯줄에는각줄마다한개의점 의두자연수 와 가하나의공백을두고순서대로주어진다. 입력되는모든점의좌표는 1 이상 100,000 이하의자연수이다. 출력파일의이름은 OUTPUT.TXT이다. 출력파일의첫째줄에는입력파일에제시된다섯개의점에대하여, 각점이세개의규칙을반복적용하여만들어질수있는지의여부를출력한다. 가능하면 Y를, 불가능하면 N을한줄에하나씩순서대로출력한다. 3 5 4 6 2 3 1 1 2 5 4 7 Y Y N Y Y
풀이이문제는점의집합을확장하는규칙과시작점이주어졌을때, 목표로하는점을만들수있는지의여부를판단하는문제이다. 가능한모든점을직접만들어보는식으로는해결할수없으므로, 점을생성하는규칙에대해서수학적으로분석하는방식으로처리해야한다. 먼저시작점이 (a, a+x) 라고하면, 규칙 1을반복적용해서 a a' 인모든 a' 에대해 (a', a'+x) 를만들어낼수있음을확인할수있다. 여기에규칙 3을적용하면, 모든자연수 n에대해 (a', a'+n x) 도만들어낼수있다. 이제 a 인적당한 N에대해 (, + x) 를만들어낼수있으므로, 여기에규칙2를 N번적용하면 (1, 1+x) 를만들어낼수있다. 이를정리하면, 즉차이가 x인모든점을만들어낼수있음을확인할수있다. 마찬가지로만일 x = k라면 (k는홀수 ) (1, 1+k) 를만들어낼수있으므로, (g, g+y) 를생성할수있을필요충분조건은 y가 k의자연수배인것이다. 만일 x가 0인경우, 즉시작점이 (a, a) 인경우는 x좌표와 y좌표가같은모든점들만만들어낼수있으며, x가음수인경우는뒤집어서생각해주면마찬가지로처리할수있다.
#include <cstdio> #include <algorithm> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) using namespace std; int64 a, b; int64 x, y; int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); scanf("%i64d %I64d", &a, &b); int g = abs(a - b); while (g && (1 - (g % 2))) g /= 2; REP(i, 5) { scanf("%i64d %I64d", &x, &y); string ret = "NO"; if (a == b) { if (x == y) ret = "YES"; else { if (!((x == y) ((a - b) * (x - y) < 0))) { if (abs(x - y) % g == 0) ret = "YES"; printf("%c\n", ret[0]);
최고속력 600 km/h로운행하는것을목표로하는 한국형초고속철도사업 이순조롭게진행되고있다. 이미초고속철도의시험선로를구축하였고열차를시험운행하고있다. 그리고선로의상태를검사하기위하여, 선로의지정된검사구간을담당하는로봇을설치하였다. 그런데검사구간이서로겹치는로봇사이에는빈번한데이터교환이필요하다. 따라서이를지원할데이터송수신장치를모든로봇에설치할뿐만아니라, 특별한데이터처리장치를로봇에부착하기로하였다. 그러나이처리장치는모든로봇에부착하지않아도되지만, 두로봇이담당하고있는검사구간이서로겹치면이두로봇중에서적어도하나에는반드시부착되어야한다. 아래그림과같은시험선로에서네개의로봇 a, b, c, d가있고, 각로봇의검사구간은아래와같다고하자. 로봇 a 와 b는담당하는선로의검사구간이겹치므로둘중최소한하나에처리장치가부착되어야한다. 로봇 b와 c, b와 d, 그리고 c와 d의경우도마찬가지이다. 위의조건을만족하면서처리장치를부착하는것은여러가지경우가있을수있다. 위그림의예에서 {a, b, c, d 모두에부착할수도있고, {b, c 에부착할수도있다. 우리팀에서는어떤로봇 에처리장치를부착하는것이좋은지를연구하고있는데, 우선위조건을만족하면서처리장치를부착할수있는모든경우의수를구하여보기로하였다. 위의예에서가능한경우를모두나열해보면 {a, b, c, d, {a, b, c, {a, b, d, {a, c, d, {b, c, d, {b, d, {b, c, 총일곱가지경우가있다. 시험선로를눈금이매겨진직선으로나타내며, 로봇의검사구간은이직선위에있다고할때, 로봇들이담당하는선로의검사구간을입력받아로봇에처리장치를부착할수있는모든경우의수를출력하는프로그램을작성하시오. 실행파일의이름은 KTX.EXE로하고, 실행시간은 1초를초과할수없다. 부분점수는없다. 입력파일의이름은 INPUT.TXT이다. 첫째줄에로봇의개수 ( ) 이입력된다. 둘째줄부터 개의줄에한줄에하나씩로봇이담당하는검사구간의왼쪽끝점의좌표와오른쪽끝점의좌표가빈칸을사이에두고주어진다. 이들좌표는모두 0 이상 10,000,000 이하인정수이다. 각검사구간의왼쪽끝점의좌표가오른쪽끝점의좌표보다항상작다. 또한검사구간들의끝점들의좌표는모두서로다르다. 다시말하면, 어떤좌표값에도두개이상의검사구간의끝점이위치하지않는다. 출력파일의이름은 OUTPUT.TXT이다. 첫째줄에문제의조건을만족하면
서처리장치를부착할수있는경우의수를출력한다. 만약경우의수가 20,070,713 이상일때에는 20,070,713 으로나눈나머지를출력한다. 또한계산도중오버플로우가발생할수있음을유의하라. 4 6 20 13 49 29 41 34 55 7
풀이이문제는검사구간에대한정보가주어졌을때, 가능한모든경우의수를구하여출력하는문제이다. 이때문제에도주어져있듯경우의수가매우커질수있음을알수있고, 따라서가능한경우를실제로하나하나씩생성해보는식으로처리해서는안된다. 이를처리하기위한좋은방법으로는, 동적계획법을이용하여여러경우의수를한번에구하는것이적절하다. 이를위해서구간들을정렬한뒤동적계획법을이용하면문제를해결할수있다. 이제 1부터 k까지의구간만을이용해서구한해를 vc(k) 라고하자. 이제, 1에서 k-1 까지의구간중 k번째구간과겹치지않으면서가장번호가가장큰구간의번호를 x(k) 라하면, 다음과같은관계식을세울수있다. 모든 k에대한 x(k) 의값은한번의스캔으로미리구해놓을수있다. k번째구간에통신장치를설치하지않는경우의가짓수는 vc(k-1) 가지와같고, 설치하는경우는 vc(x(k)) 경우와같다. 이두가지경우뿐이고서로중복되는경우가없으므로 vc(k) 는 vc(k-1)+vc(x(k)) 가된다. 전체시간복잡도는정렬이결정하고나머지과정은선형시간에해결되므로, 전체시간복잡도는 O( log ) 이다.
#include <cstdio> #include <algorithm> using namespace std; const int Maxn = 100005; class ktx { public: int a, b; bool operator < (const ktx &c) const { return b < c.b; ; int n; ktx train[maxn]; ktx nl[maxn]; // number, left int x[maxn]; int64 res[maxn]; int main() { FILE *fin = fopen("input.txt", "r"); int i; fscanf(fin, "%d", &n); for(i = 0; i < n; i++) { fscanf(fin, "%d%d", &train[i].a, &train[i].b); fclose(fin); sort(train, train + n); for(i = 0; i < n; i++) { nl[i].a = i; nl[i].b = train[i].a; sort(nl, nl + n); int t = -1; for(i = 0; i < n; i++) { x[nl[i].a] = n; if (train[0].b <= nl[i].b) break; if (i!= n) { t = 0; for(i = i; i < n; i++) { while(t < n && train[t].b <= nl[i].b) { t++; x[nl[i].a] = t - 1;
res[n] = 1; res[0] = 2; for(i = 1; i < n; i++) { res[i] = (res[i - 1] + res[x[i]]) % 20070713; FILE *fout = fopen("output.txt", "w"); fprintf(fout, "%I64d\n", res[n - 1]); fclose(fout); return 0;
N개의행과 M개의열로구성된격자판의각칸에숫자들이들어있다. 정수 K (K 2) 가주어진다. K는 N보다작고, M보다도작다. 격자판에서 R개의행과 C개의열을 R + C = K가만족하도록선택하고, 선택된행과열을제외한나머지칸에있는숫자들가운데가장큰숫자가최소가되도록하려고한다. N = 4, M = 5인경우의격자판의예가다음그림과같이주어졌다고하자. 1 2 3 4 5 1 3 1 7 6 3 2 3 4 2 8 2 3 8 6 4 2 4 4 3 5 1 2 1 위의예에서 K = 3인경우, 1행, 3행과 4열을선택하면다음그림과같이선택된행과열을제외한나머지칸에있는숫자들가운데제일큰숫자는 5이다. 3행, 3열과 4열을선택하여도선택된행과열을제외한나머지칸가운데제일큰숫자는 5이다. 그러나달리선택하여나머지칸에있는숫자들이모두 5 보다작게만들수는없다. 숫자들이들어있는격자판과선택할수있는행의개수와열의개수의합이주어졌을때, 선택한행과열을제외한나머지칸에있는숫자들가운데가장큰숫자가최소가되도록행과열을선택하기위한프로그램을작성하시오. 실행파일의이름은 GRID.EXE로하고, 실행시간은 2초를초과할수없다. 부분점수는없다. 입력파일의이름은 INPUT.TXT이다. 첫줄에는격자판의크기를나타내는정수 N과 M이주어진다. N과 M은 3 이상이며, 300 이하인정수이다. 둘째줄에는선택할수있는행과열의개수의합 K (K < N, K < M) 가주어진다. 셋째줄부터격자판에들어있는양의정수들이한줄에한행씩 1행부터차례대로주어진다. 격자판에들어있는각숫자는 1 이상 500,000 이하의정수이다. 같은줄에입력되는각정수들사이에는한개의공백이있다. 출력파일의이름은 OUTPUT.TXT이다. 첫번째줄에 R + C = K를만족하는 R개의행과 C개의열을선택하여, 선택된행과열을제외한나머지칸에있는숫자들가운데가장큰숫자의최소값을출력한다. 둘째줄에는선택한행의개수와이어서행번호를오름차순으로출력한다. 셋째줄에는선택한열의개수와이어서열번호를오름차순으로출력한다. 행의개수나열의개수가 0인경우에는해당하는줄에 0만출력한다. 같은줄에출력되는각정수들사이에는
한개의공백을둔다. 조건을만족하는답이여러개인경우에는그중에서하나만출력하면된다. 4 5 3 3 1 7 6 3 3 4 2 8 2 8 6 4 2 4 3 5 1 2 1 5 2 1 3 1 4
풀이이문제는격자판에대한정보가주어졌을때, 주어진답을최소로하는행과열을선택하는방법을구하는문제이다. 이문제는이진탐색을이용해해결할수있다. 제거하고남은수들중의최대값이 X가되도록할수있는지를결정하는문제를푼뒤, X의범위를이분탐색을통해탐색해가며가장작은값을구하는것이다. 바꾼결정문제는결국 X보다큰수들을 k개이하의행과열로모두덮을수있는지를판단하는문제이다. 주어진행렬과 X를바탕으로이분그래프 (bipartite graph) 를구성하는데, 각각행의개수와열의개수만큼정점을만든뒤, 그사이의간선은행과열이만나는칸에있는수가 X보다클때만들어준다. 이렇게구성된이분그래프에서임의의최소정점커버 (minimum vertex cover) 를구했을때그수가 k보다작으면 X보다큰값을모두 k개의행과열로충분히덮을수있는것이다. 이분그래프에서최소정점커버의수는최대매칭 (maximum matching) 의수와같으며, 최대매칭을찾은뒤간단한너비우선탐색 (BFS) 을통해실제로어떤정점을선택하면되는지를판단할수있으므로, 전체문제를해결할수있다.
#include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <fstream> #include <iostream> #include <set> using namespace std; #define N 1100 int nr,nc; int rc; int num[n][n]; vector<int> candi; set<int> repch; int ans; int row[n]; int rowc; int col[n]; int colc; vector< vector<int> > bpg; int sel[n]; int visit[n]; int matched[n]; vector<int> path; void input() { int i,j; ifstream in ("input.txt"); in >> nr >> nc; in >> rc; for(j=0;j<nc;j++) { in >> num[i][j]; if ( repch.find(num[i][j]) == repch.end() ) { repch.insert(num[i][j]); candi.push_back(num[i][j]); in.close(); void init_graph() { int i;
vector<int> tmp; bpg.push_back(tmp); void clear_graph() { vector< vector<int> >::iterator it; for(it=bpg.begin();it!=bpg.end();it++) { it->clear(); void set_edge(int a,int b) { bpg[a].push_back(b); void make_graph(int target) { int i,j; clear_graph(); for(j=0;j<nc;j++) { if (num[i][j]>target) { set_edge(i,j); int find_augment_path(int p) { int b,c; if (visit[p]==1) return 0; visit[p]=1; vector<int>::iterator it; for(it=bpg[p].begin();it!=bpg[p].end();it++) { b=*it; c=sel[b]; path.push_back(p); path.push_back(b); if (c==-1) return 1; if (find_augment_path(c)==1) return 1; path.pop_back(); path.pop_back(); return 0; int match() { int i,j; int b,c; int match_num;
match_num=0; for(i=0;i<nc;i++) { sel[i]=-1; for(j=0;j<nr;j++) { visit[j]=0; path.clear(); find_augment_path(i); if (path.size()==0) continue; vector<int>::iterator it; for(it=path.begin();it!=path.end();it+=2) { b=*it; c=*(it+1); sel[c]=b; match_num++; return match_num; void dfs(int p) { int b,c; if (visit[p]==1) return; visit[p]=1; vector<int>::iterator it; for(it=bpg[p].begin();it!=bpg[p].end();it++) { b=*it; c=sel[b]; if (c==-1) { cout << "there may be bug." << endl; exit(0); col[b]=1; dfs(c); void get_cover() { int i; visit[i]=0; matched[i]=0; row[i]=0;
for(i=0;i<nc;i++) { if (sel[i]!=-1) { matched[sel[i]]=1; col[i]=0; if (matched[i]==0) { dfs(i); if (matched[i]==1 && visit[i]==0) { row[i]=1; int possible(int target) { int cover; make_graph(target); cover=match(); if (cover<=rc) return 1; return 0; int count(int a[],int ac) { int i; int sum; sum=0; for(i=0;i<ac;i++) { if (a[i]==1) sum++; return sum; void get_ans(int a) { int i; int diff; ans=candi[a]; rowc=count(row,nr); colc=count(col,nc); diff=rc-rowc-colc; if (diff<0) { cout << "there be bug. rowc+colc>rc" << endl; diff=0; exit(0);
if (diff==0) break; if (row[i]==0) { row[i]=1; rowc++; diff--; void proc() { int m; int a,b; if (rc>=nr rc>=nc) { ans=-1; // we can cover all the number; return; sort(candi.begin(),candi.end()); init_graph(); a=0; b=candi.size(); while(a!=b) { m=(a+b)/2; if (possible(candi[m])) { b=m; get_cover(); get_ans(b); else { a=m+1; void output() { int i; ofstream out ("output.txt"); out << ans << endl; out << rowc << " "; if (row[i]==1) { out << i+1 << " "; out << endl; out << colc << " ";
for(i=0;i<nc;i++) { if (col[i]==1) { out << i+1 << " "; out << endl; out.close(); int main() { input(); proc(); output(); return 0;