티스토리 툴바

Daum
Tistory
로그인
trynerr's blog : 힘내라 베스트송!!

실험 데이터 복구하기 - Algospot(162)

생각보다 너무 오래걸린 문제 algospot 게시판에 어떤분이 질문을 올렸던 것이 시발점이 되서 자그만치 3주가 소요되었다.
물론 이것저것 큰일들이 겹치게 되어 열심히 하지 않았던 것도 있지만...
이렇게 오래 try해본 문제는 정말 오랫만인것 같다.
이번 문제를 통해 뼈져리게 느낀점은 내가 만든 코드를 절대 맹신 하지 말자 는 것이다.
어느정도 가이드라인로 짰던 코드들은 전혀 문제가 없었고 순전히 내가 짜낸 알고리즘 코드만 문제가 있었단 사실... 디버깅만 2주;;
여러가지 testcase를 생각해보는것도 중요한듯...
계획으로 잡아놨던것도 뒤로 미루고 매달렸던 문제만큼 얻는것도 많았던것 같다.
pDNA와 비슷하게 재귀로 금방 풀었는데 바로 time limit
dp로 풀어봐야겠는데 이리저리 알아본 결과 TSP(traveling salesman problem)와 비슷하며 DP로 풀어보라는 ...
그래 이번기회에 dp공부를 좀 해보자는 생각으로 도전
처음엔 중간 중간 cost를 계산해 보겟다는 방식으로 접근했는데 문제되는게 한두가지가 아닌거 같아서 짜다가 관두고... 처음 cost를 정의할수 있는 방법으로 접근 잔여 길이으로만 weight를 정하고 마지막에 초기전체 길이를 잡아주면 될꺼 같았는데 이것역시 전부 포함 되는 것들이 문제 된다싶어서 다른방법을 생각했었는데 이게 삽질의 시작이었다. 나중에 한참 삽질하다가 어떤분한테 얘기들었던것은 전부포함되는건 그냥 제외시키면 되지 않느냐... 라는 말을 듣게 됐고;; 생각해보니 맞다... -_-;; 이것때문에 버린시간이.. ㅠㅠ
아무튼 어느정도 알고리즘은 윤곽이 잡혔는데 다음 문제되는것은 shortest path를 어떻게 저장시킬까 생각하는 것으로 한참 삽질후에 dynamic table 과 같은 table을 만들고 상위 node를 가리키는 방법으로 풀었다.
완성 됐다 싶어서 문자열들을 규칙에 맞게 조합시키는 루틴을 만들고 돌려보았다. testcase통과했는데 코드를 올려보니 WA .. 이걸로 보낸시간만 2주가 넘는다.
결정적으로 잔여 length 체크하는 부분과 조합시키는 부분을 짜내서 만들었는데 이부분에 예외처리가 아주 많이 안되었던것이었다. 결국 다양한 testcase로 디버깅 하고... 결국 오늘 Accept!!!
미칠듯한 쾌감이다!! '이제 미뤄놓은걸 할 수 있겠구나..' 라며...

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

char text[15][301];
char *mintext;
int path[15];
int weight[15][15];
int dist[15][(1 << 16)];
int via[15][1 << 16];
int idx;
int n;
int st;
int maxlen;

int length(char *st, char *ed);
int memoi(int sv, int set);
void johap(char *st, char *ed);
void get_path(int sv, int set);

int main(void)
{
	int T;

	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		maxlen = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> text[i];
			maxlen += strlen(text[i]);
		}

		mintext = (char *)malloc(maxlen + 1);
		char *output;
		output = (char *)malloc(maxlen + 1);

		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (strcmp(text[i], text[j]) > 0) {
					strcpy(output, text[i]);
					strcpy(text[i], text[j]);
					strcpy(text[j], output);
				}
			}
		}

		for (int i = 0; i < maxlen; i++)
			mintext[i] = 'z';
		mintext[maxlen + 1] = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) {
					weight[i][j] = 0;
				} else {
					weight[i][j] = length(text[i], text[j]);
					if (weight[i][j] == 0) {
						for (int k = j; k < n - 1; k++) {
							strcpy(text[k], text[k + 1]);
						}
						n--;
						i = -1;
						break;
					}
				}
			}
		}

		int wmin = 100000;
		int start = -1;
		for (int i = 0; i < n; i++) {
			memset(dist, -1, sizeof(dist));
			memset(via, -1, sizeof(via));
			idx = 0;

			st = i;
			int temp = strlen(text[i]) + memoi(i, (1 << n) - 1 - (1 << i));
			if (temp < wmin) {
				wmin = temp;
				start = i;

				path[idx++] = i;
				get_path(i, (1 << n) - 1 - (1 << i));
				
				//cout << "mintext1:" << mintext << endl;
				memset(mintext, 0, sizeof(mintext));
				//cout << "< " << i << endl;
				for (int i = 0; i < n; i++) {
					//cout << path[i] << ":";
					johap(mintext, text[path[i]]);
				}
				//cout << endl;
				//cout << "mintext2:" << mintext << endl;
			} else if (temp == wmin) {
				start = i;
				path[idx++] = i;
				get_path(i, (1 << n) - 1 - (1 << i));

				memset(output, 0, sizeof(output));
				//cout << "== " << i << endl;
				for (int k = 0; k < n; k++) {
					//cout << path[k] << ":";
					johap(output, text[path[k]]);
				}
				//cout << endl;
				//cout << "mintext:" << mintext << endl;
				//cout << "output:" << output << endl;

				if (strcmp(mintext, output) > 0) {
					start = i;
					strcpy(mintext, output);
				}
			}
		}

		cout << mintext << endl;	
		/*
		cout << wmin << endl;

		for (int i = 0; i < n; i++) {
			cout << text[i] << endl;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << weight[i][j] << " ";
			}
			cout << endl;
		}
		*/
	}

	return 0;
}

void get_path(int sv, int set)
{
	//cout << "[" << sv << "Path:" << via[sv][set] << "]" << endl;

	path[idx++] = via[sv][set];

	if (set == 0)
		return;

	get_path(via[sv][set], set - (1 << via[sv][set]));
}

int memoi(int sv, int set)
{
	// 노드를 전부 돌았을때
	if (set == 0) {
		//return dist[sv][set] = weight[st][sv];
		return dist[sv][set] = 0; 
	}
	// 이미 돌았던 노드와 같은 상황이 온다면 저장되어있는 값을 리턴
	if (dist[sv][set] != -1)
		return dist[sv][set];

	int tmin = 100000;
	for (int i = 0; i < n; i++) {
		if (((set & (1 << i)) != 0) && (i != sv)) {
			//int temp = memoi(i, set - (1 << i));
			int temp = weight[sv][i] + memoi(i, set - (1 << i));

			if (temp < tmin) { 
				tmin = temp;
				via[sv][set] = i;
			}
		}
	}
	return (dist[sv][set] = tmin);
}

int length(char *st, char *ed)
{
	int st_len = strlen(st);
	int ed_len = strlen(ed);

	int i, j, k;
	k = j = 0;
	for (i = 0; i < st_len && j < ed_len; i++) {
		if (st[i] == ed[j])
			j++;
		else {
			if (j > 0)
				i = k++;
			j = 0;
		}
	}

	//return st_len + (ed_len - j);
	return (ed_len - j);
}

void johap(char *st, char *ed)
{
	int st_len = strlen(st);
	int ed_len = strlen(ed);

	int i, j, k;
	k = j = 0;
	for (i = 0; i < st_len && j < ed_len; i++) {
		if (st[i] == ed[j])
			j++;
		else {
			if (j > 0)
				i = k++;
			j = 0;
		}
	}

	for (int k = j; k < ed_len; k++) {
		st[i++] = ed[k];
	}
	st[i] = 0;
}

실행 시간/메모리 제한

실행 시간: 2000ms, 메모리 제한: 65536KB

문제 설명

토요일에 출근해서 연구실에서 놀고 있던 조교 A군은 실수로 실험에 사용하던 데이터를 삭제하고 말았다. 복사본도 없는 터라 이대로라면 교수님의 진노를 한 몸에 받을 것은 자명한 일, 따라서 A군은 그럴 듯해 보이는 데이터를 위조하여 (주: 실제로 이러면 안 됩니다) 교수님의 분노를 피해 가기로 한다.

우리가 데이터에 대해 알고 있는 것은, 데이터가 K개의 문자열을 부분 문자열로 포함한다는 것밖에 없다. 어떤 문자열의 부분 문자열은 해당 문자열의 연속된 일부분이라고 가정하자. 이 문자열들은 모두 알파벳 소문자로 구성된다. 이들을 모두 부분 문자열로 포함하는 문자열 중 가장 짧은 것을 계산하는 프로그램을 작성하라. 만약 이와 같은 문자열이 여러 개 있다면 이 중 가장 사전 순으로 앞에 오는 것을 찾도록 한다.

입력 설명

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어진다. 각 테스트 케이스의 첫 줄에는 부분 문자열의 수 K (<= 15) 가 주어진다. 그 후 K 줄에 하나씩, 알파벳 소문자로만 구성된 부분 문자열이 주어진다.

원래 문자열의 길이는 300 이하이다.

출력 설명

각 테스트 케이스마다 한 줄로, 해당 문자열을 모두 포함하는 가장 짧은 문자열들 중 사전 순으로 가장 앞에 있는 것을 출력한다.

예제 입력

3
3
geo
oji
jing
2
world
hello
3
abrac
cadabra
dabr

예제 출력

geojing
helloworld
cadabrac
저작자 표시 비영리

'Algorithm > Algospot' 카테고리의 다른 글

실험 데이터 복구하기 - Algospot(162)  (0) 2010/01/16
콘서트 - Algospot(224)  (0) 2009/12/20
눈치게임 - Algospot(262)  (0) 2009/12/18
Yulo.K 선생님의 고민 - Algospot(252)  (0) 2009/12/18
URI Decoding - Algospot(110)  (0) 2009/12/18
Weird Numbers - Algospot(101)  (0) 2009/12/05
Tag
162, algorithm, Algospot, trynerr, 실험 데이터 복구하기
Response
0 Trackback , 0 Comment

콘서트 - Algospot(224)

처음 문제를 본순간 재귀로 풀면 되겠거니 싶어서 거침없이 코딩해서 바로 올려봤는데 바로 time limit이 떨어졌다. 역시 쉬운 문제가 아니었구나..
재귀상태에서 최대한 최적화를 시켜봤으나 그정도로 풀릴 것이 아니었다.
testcase를 최대치를 주고 돌려본결과... 프로그램이 먹통이 된다 ;)
(예)
1
50 5 200
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

생각끝에 전에 풀어봤던 Weird number 문제와 컨셉을 비슷하게 해서 풀어봤다... 결과는 Accept !!
이것도 DP맞나...??(사실 DP에 대해서 잘 모른다...)
이렇게 배우면서 푸는 문제들이 재미있다.
비슷하게 많이 풀어봤던 문제들은 도전하는 맛이 좀 떨어지는게 있어서 ... 역시 새로운게 좋다 ㅎㅎ
막판에 string.h 컴파일 에러는 안습..

마킹 배열 2개에 계산 된 값들을 번갈아가며 저장한다
검색하는 배열과 계산된 값 저장하는 배열이 있고(마킹배열) 이것들은 입력된 조절 볼륨과 계산한다.
계산이 끝나고 다시 루핑을 돌며 가장 큰수를 출력하면 끝!

소스 코드

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, vs, vm;
int *vi;
int vol_max;

void solve(int vol, int idx);

int main(void)
{
	int tc;
	short *vm_vec1;
	short *vm_vec2;
	short *temp;
	vector<int> output;
	
	cin >> tc;

	while (tc--) {
		cin >> n >> vs >> vm;

		vi = (int *)malloc(sizeof(int) * n);
		for (int i = 0; i < n; i++) {
			cin >> vi[i];
		}

		vm_vec1 = (short *)malloc(sizeof(short) * (vm + 1));
		memset(vm_vec1, 0, sizeof(short) * (vm + 1));
		vm_vec2 = (short *)malloc(sizeof(short) * (1 + vm));
		memset(vm_vec2, 0, sizeof(short) * (1 + vm));

		vm_vec1[vs] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= vm; j++) {
				if (vm_vec1[j] == 1) {
					vm_vec1[j] = 0;
					int plus = j + vi[i];
					int minus = j - vi[i];
					if (plus <= vm)
						vm_vec2[plus] = 1;

					if (minus > -1)
						vm_vec2[minus] = 1;
				}
			}
			temp = vm_vec1;
			vm_vec1 = vm_vec2;
			vm_vec2 = temp;
		}
		
		int sw = 0;
		for (int i = vm; i >= 0; i--) {
			if (vm_vec1[i] == 1) {
				output.push_back(i);
				sw = 1;
				break;
			}
		}
		if (sw == 0)
			output.push_back(-1);
		
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << endl;

	return 0;
}

실행 시간/메모리 제한

실행 시간: 2000ms, 메모리 제한: 65536KB

문제 설명

용재는 교내의 밴드 'Algorhythm'의 멤버이며 기타를 맡고 있다. 이번에 Algorhythm은 축제를 맡아 알고리즘 강의 시간에 공연을 하게 되었다. 용재는 특이한 기타 리스트 인데, 같은 볼륨으로 모든 곡을 연주 하는걸 원치 않는다. 따라서 용재는 다음과 같은 방법으로 매 곡마다 볼륨을 바꾸려고 한다.

공연 전에 준비 때 볼륨은 용재가 직접 정하고, 나머지는 전체적인 볼륨을 조절하는 당신에게 맡겼다. 준비 할 때의 볼륨은 VS이다. 용재는 당신에게 메모에 N개의 숫자 V = { V1, V2, ..., VN}을 적어줬는데, i번째 곡이 연주되기 전에 현재 볼륨에 Vi 만큼 더하거나 빼달라고 요청했다. 그리고 덧붙여서 마지막 곡이 연주될 때에는 클라이막스 부분이기 때문에 반드시 소리를 최대한 크게 조절해달라고 부탁했다. 또한 절대로 볼륨은 0보다 작을 경우가 발생해서는 안되고, VM를 넘지 말아야 한다는 것도 당부하였다.

예를 들어 VS = 5이고 V = { 5, 3, 7} 일 경우 처음에 5를 빼서 볼륨을 0을 만든 다음, 3을 더해서 볼륨을 3으로 만들고 마지막에 7을 더할 경우 볼륨은 10이 되고, 이 경우는 가능한 모든 경우 중에 마지막의 볼륨을 최대화 한 경우이다.

용재의 부탁대로 볼륨을 조절할 때 N번째 곡을 연주 할 때의 볼륨의 최대를 구하는 프로그램을 작성하라.

입력 설명

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 T가 주어진다. (1<=T<=100) 테스트 케이스의 첫번째 줄에는 N(1<=N<=50)과 VS(0<=VS<=VM)와 VM(0<=VM<=1,000)가 주어진다. 그리고 두번째 줄에는 V1, V2, ..., VN(1<=Vi<=VM)이 차례대로 입력된다.

출력 설명

각 테스트 케이스의 순서대로 곡을 연주할 때의 볼륨의 최대를 한줄에 하나씩 출력하며, 만약 도중에 볼륨이 0미만으로 떨어지거나 VM를 초과 할 수 밖에 없는 경우가 발생할 경우에는 -1을 출력한다.

예제 입력

3
3 5 10
5 3 7
4 8 20
15 2 9 10
14 40 243
74 39 127 95 63 140 99 96 154 18 137 162 14 88

예제 출력

10
-1
238
저작자 표시 비영리

'Algorithm > Algospot' 카테고리의 다른 글

실험 데이터 복구하기 - Algospot(162)  (0) 2010/01/16
콘서트 - Algospot(224)  (0) 2009/12/20
눈치게임 - Algospot(262)  (0) 2009/12/18
Yulo.K 선생님의 고민 - Algospot(252)  (0) 2009/12/18
URI Decoding - Algospot(110)  (0) 2009/12/18
Weird Numbers - Algospot(101)  (0) 2009/12/05
Tag
224, algorithm, Algospot, trynerr, 콘서트
Response
0 Trackback , 0 Comment

눈치게임 - Algospot(262)

역시 전에 동아리에서 풀어본 문제... 문제 이해하는데만 한세월이었으며 이또한 얘들끼리 의견이 분분했다. 
내 가정이 사실이었던것!
사실 문제가 살짝 이해하기 힘들었다. 제공된 input도 약간좀 이상하고...
결국 쓰이지 않는 정보들도 들어있다고 가정했고 그게 적중했다.
문제만 이해했다면 생각보다 문제는 쉽다. 각 번호 순서대로 먼저부른 사람을 체크하고 동시에 부르면 출력 그런 사람이 없다면 마지막 부른 사람이 출력된다.
이것 또한 한번에 Accept!!


소스 코드(C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	int testCase, col, row, min, doublecount;
	int **w;
	int *mark, *t_mark;
	vector<int> output;
	
	cin >> testCase;
	for (int index = 0; index < testCase; index++) {
		doublecount = 0;
		cin >> row;
		cin >> col;
		
		w = (int **)malloc(sizeof(int *) * row);
		for (int q = 0; q < row; q++) {
			w[q] = (int *)malloc(sizeof(int) * col);
		}

		mark = (int *)malloc(sizeof(int) * row);
		t_mark = (int *)malloc(sizeof(int) * row);

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				cin >> w[i][j];
			}
		}
		
		for (int i = 0; i < col; i++) {
			min = 10000;
			doublecount = 0;
			// 각숫자당 min 값을 찾는다
			for (int j = 0; j < row; j++) {
				t_mark[j] = 0;
				if (min > w[j][i] && mark[j] == 0) {
					min = w[j][i];
				}
			}
			
			// 부른값이 중복되었는지 검사한다
			for (int j = 0; j < row; j++) {
				if (min == w[j][i] && mark[j] == 0) {
					doublecount++;
					t_mark[j] = 1;
				}
			}
			
			// 중복되었다면 중복된 값을 출력후에 두번째 루핑을 빠져나온다
			for (int j = 0; j < row; j++) {
				if (t_mark[j] == 1) {
					if (doublecount > 1) {
						output.push_back(j + 1);
					} else
						mark[j] = t_mark[j];
				}
			}
		
			if (doublecount > 1) {
				output.push_back(-1);
				break;
			}
		}
		
		// 중복된것도 없고 각숫자도 잘 불려 졌다면 못부른사람이 진사람
		if (doublecount == 1) {
			for (int i = 0; i < row; i++) {
				if (mark[i] == 0) {
					output.push_back(i + 1);
				}
			}
			output.push_back(-1);
		} 
		
		/*
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				System.out.print(w[i][j]);
			}
			System.out.println();
		}
		*/
	}
	
	int temp;
	for (int i = 0; i < output.size(); i++) {
		temp = output[i];
		if (temp == -1)
			cout << endl;
		else
			cout << temp << " ";
	}
}

소스 코드(Java)

import java.util.ArrayList;
import java.util.Scanner;


public class B {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int testCase, col, row, min, doublecount;
		int[][] w;
		int[] mark, t_mark;
		ArrayList<Integer> output = new ArrayList<Integer>();
		
		testCase = sc.nextInt();
		for (int index = 0; index < testCase; index++) {
			doublecount = 0;
			row = sc.nextInt();
			col = sc.nextInt();
			
			w = new int[row][col];
			mark = new int[row];
			t_mark = new int[row];
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					w[i][j] = sc.nextInt();
				}
			}
			
			for (int i = 0; i < col; i++) {
				min = 10000;
				doublecount = 0;
				// 각숫자당 min 값을 찾는다
				for (int j = 0; j < row; j++) {
					t_mark[j] = 0;
					if (min > w[j][i] && mark[j] == 0) {
						min = w[j][i];
					}
				}
				
				// 부른값이 중복되었는지 검사한다
				for (int j = 0; j < row; j++) {
					if (min == w[j][i] && mark[j] == 0) {
						doublecount++;
						t_mark[j] = 1;
					}
				}
				
				// 중복되었다면 중복된 값을 출력후에 두번째 루핑을 빠져나온다
				for (int j = 0; j < row; j++) {
					if (t_mark[j] == 1) {
						if (doublecount > 1) {
							output.add(j + 1);
							//System.out.print((j + 1) + " ");
						} else
							mark[j] = t_mark[j];
					}
				}
			
				if (doublecount > 1) {
					//System.out.println();
					output.add(-1);
					break;
				}
			}
			
			// 중복된것도 없고 각숫자도 잘 불려 졌다면 못부른사람이 진사람
			if (doublecount == 1) {
				for (int i = 0; i < row; i++) {
					if (mark[i] == 0) {
						output.add(i + 1);
						//System.out.print((i + 1) + " ");
					}
				}
				output.add(-1);
				//System.out.println();
			} 
			
			/*
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					System.out.print(w[i][j]);
				}
				System.out.println();
			}
			*/
		}
		
		int temp;
		for (int i = 0; i < output.size(); i++) {
			temp = output.get(i);
			if (temp == -1)
				System.out.println();
			else
				System.out.print(temp + " ");
		}
	}
}

실행 시간/메모리 제한

실행 시간: 5000ms, 메모리 제한: 65536KB

문제 설명


Random Backoff - Network에서의 눈치게임

ICU Programming Club RUN은 ICPC 시즌을 맞아, 대전 근교 장태산으로 엠티를 갔다. 밤이 되고 함께 술을 마시며 놀다가, 그들은 눈치 게임을 시작했다. 눈치게임은 다음과 같은 방식으로 진행한다.

N명의 사람이 있다. 편의상 각 사람을  1...N 번 사람이라고 부른다.
이들은 서로 눈치를 보며 1부터 K까지 순서대로 숫자를 외친다. K는 N보다 작다
두 사람 이상이 동시에 같은 숫자를 외치면 그 사람들은 게임에 지게 된다. 
한 번 숫자를 외친 사람은 더 이상 다른 숫자를 외치지 않는다.
K 까지 숫자를 외치는 동안 패자가 없으면, 숫자를 외치지 못한 나머지 사람들이 지게 된다.

게임이 시작하면 1을 외칠 수 있고, 누군가 j를 외치면 그 순간부터 j+1을 외칠 수 있다. i번 사람은 숫자 j를 외칠 수 있는 순간부터 W(i,j) 시간만큼 기다리며 눈치를 본다. 그리고 그 시간동안 아무도 숫자를 외치지 않으면 j를 외친다.

N명이 각각 숫자에 대해서 기다리는 시간이 주어졌을 때 눈치게임에서 지는 사람은 누구인가?

입력 설명

첫 줄에는 게임의 회수 T가 주어진다. (1 ≤ T ≤ 100 )
각 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다. (1 ≤ K < N ≤ 500)
다음 줄부터 N 줄에 걸쳐서 N x K 의 행렬이 주어진다.
i행의 j열에 있는 수는 W(i,j)를 나타낸다. (0 ≤ W(i,j) ≤ 60, 1 ≤ i ≤ N, 1 ≤ j ≤ K)

출력 설명

각각의 게임에 대하여 지는 사람의 목록을 오름차순으로 한 줄에 출력한다.
각 사람은 한 칸의 공백으로 구분하도록 한다.

예제 입력

3
4 3
0 1 3
7 0 1
5 1 3
1 2 3
3 2
1 1
1 2
1 3
5 3
0 1 2
2 0 1
1 2 0
1 2 3
1 1 1

예제 출력

3 4
1 2 3
4 5
저작자 표시 비영리

'Algorithm > Algospot' 카테고리의 다른 글

실험 데이터 복구하기 - Algospot(162)  (0) 2010/01/16
콘서트 - Algospot(224)  (0) 2009/12/20
눈치게임 - Algospot(262)  (0) 2009/12/18
Yulo.K 선생님의 고민 - Algospot(252)  (0) 2009/12/18
URI Decoding - Algospot(110)  (0) 2009/12/18
Weird Numbers - Algospot(101)  (0) 2009/12/05
Tag
262, algorithm, Algospot, trynerr, 눈치게임
Response
0 Trackback , 0 Comment
« Previous : 1 : 2 : 3 : 4 : 5 : ... 6 : Next »