2009 정보올림피아드 지역본선 문제 2

from Programming/algorithm 2009/07/26 20:23

탑
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선상에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각 각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
실행파일의 이름은 TOWER.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

입력과 출력의 예

입력 (INPUT.TXT)

5
6 9 5 7 4

출력 (OUTPUT.TXT)

0 0 2 2 4

반복문만 쓸 줄 알면 풀만한 문제네요.

27~31행과 send함수만 보면 됩니다.

하나 입력받고 send함수에서 왼쪽에 높이가 같거나 높은 탑을 찾아서 위치를 리턴합니다.

이 글이 유익하다면 (굽신굽신) ->

Tag // Koi

Trackback(1) : Comment(1)

Trackback Address >> http://zfanta.com/trackback/457

Subject: 2009 정보올림피아드 지역본선 문제 Review (2)-1
Tracked from There Ain't Just Unlogical - #pragma pack (the UNique subroutine) 2009/08/17 02:03 delete
2번 문제는...ㅅㅂ 작년에 처음 정올 나갔을 때 메모리 관리하다가 병신이 된 까닭에 (그 때 malloc 쓰는 다 된 코드였는데 얘가 오버플로. 안 했으면 통과였다.) 그래서 올해는 아예 메모리 관리는 생각도 안 하고 나갔다. 근데 낭패. 탑 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각..

ZZZ 2009/08/13 19:18 address modify / delete reply
다운 바꼬싶어요~~! 자료올려주시면 감사 저도 쓰고 싶은

2009 정보올림피아드 지역본선 문제 나도 풀어보기

from Programming/algorithm 2009/06/07 22:55

문제는 여기서

2009 정보올림피아드 지역본선 문제 Review (1)

난 이번에 정올에 안나갔다.

이렇게 일찍 하는 줄 몰랐음 ㅇㅅㅇ

내년에 나가야하나.

이 글이 유익하다면 (굽신굽신) ->

Tag // 정보올림피아드

Trackback(1) : Comment(4)

Trackback Address >> http://zfanta.com/trackback/450

Subject: 2009 정보올림피아드 지역본선 문제 Review (1)
Tracked from There Ain't Just Unlogical - #pragma pack (the UNique subroutine) 2009/06/08 23:08 delete
현재 난 고2다. 고로 난 고등부 정올에 나갔다(-_-;) 중딩 때부터 나갔으면 전국본선을 노릴 만하다고 생각하지만... 올해가 고작 2년째라서 상당히 병맛이다. 결과는 6월 5일에 나온다는군. 잡설은 집어치우고 각설. 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하라. 예를 들어 세 개의 숫..

Un-i-que 2009/06/08 23:12 address modify / delete reply
트랙백 드리고 갑니다^^
그런데 string.h의 strlen을 쓰셨으면 될 것 같습니다만?
- address modify / delete 2009/06/11 23:50 　환타
  그냥 8자리라서 이렇게 풀어보았습니다. ^^
  정해져있는 데 굳이 strlen을 쓸 필요는 없죠
- address modify / delete 2009/06/13 00:50 Un-i-que
  아차-_-;; len이라는 함수 보고 좀 잘못 생각했습니다.
  환타 님이랑 저랑 방식이 좀 다르군요.
  제 방식을 순차 접근으로 보자면 환타 님은 토큰 분리??
- address modify / delete 2009/06/13 00:59 　환타
  네. 한 구간끼리 길이를 비교하죠. ㅎ

UVa. 101 - The Blocks Problem 번역

from Programming/algorithm 2009/02/26 19:48

원문링크

101.pdf

블록 문제

배경

과감히 생략.

문제

로봇의 팔이 평평한 테이블에 있는 블럭을 명령어대로 움직이게 하는 문제.

처음엔 아래처럼 n개의 블록(0부터 n-1까지)들이 있고 $0 \leq i < n-1$ 의 범위 내에 모든 i에 대해 b_i 와 b_{i+1은 인접해있다.}

그림 : 아름다운 초기의 블럭나라

로봇의 팔에 하사하는 명령어 :

*a와 b는 블럭번호.

move a onto b
a와 b에 있는 블록들을 제자리에 돌려놓고 a블럭을 b블럭 위로 옮긴다.
move a over b
a위에 있는 블록들을 제자리에 돌려놓고 b블럭이 있는 블럭 기둥의 꼭대기로 a를 옮긴다.
pile a onto b
b위에 있는 블록들을 제자리에 돌려놓고 a블록 위에 있는 블록기둥( a를 포함하여)을 b위로 옮긴다. 옮길 때 블록의 순서는 유지한다.
pile a over b

a블록 위에 있는 블록기둥( a를 포함하여)을 b가 있는 블록기둥위로 옮긴다. 옮길 때 블록의 순서는 유지한다.
quit
종료.

a = b일 때나 a와 b가 같은 블록기둥에 있을 때는 잘못된 명령이므로 무시한다.

입력

첫 줄은 블록나라의 블록 개수를 나타내는 n(0 < n < 25)이 입력된다.

두 번째 줄부터 한 줄에 하나의 명령어가 입력되며 quit명령어가 입력될 때 까지 실행한다.

잘못된 문법의 명령어는 없다.

출력

블록나라의 최종모습을 출력한다.

각 줄의 처음에는 블록기둥 위치의 번호 i ( $0 \leq i < n$ , n은 블록의 개수)를 출력하고 바로 다음에 콜론(:)을 출력한다 .

공백문자 하나를 출력한다.

블록이 있다면 공백문자로 구분하여 출력하고 없다면 출력하지 않는다.

줄 끝에는 공백이 있으면 안된다.

입력 예시

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

출력 예시

AC

#include <iostream>
#include <vector>

using namespace std;
int n;
vector< int > blocks[25];

void init()
{
	int i;
	for(i=0; i<n; i++)
		blocks[i].push_back(i);
}

int find_block(int block)
{
	int i,j;
	
	for(i=0; i<n; i++)
		for(j=0; j<blocks[i].size(); j++)
			if(block==blocks[i][j])
				return i;
}

void returning(int a)
{
	int i, index;
	
	index=find_block(a);
	for(i=blocks[index].size()-1; blocks[index][i]!=a; i--)
	{
		blocks[blocks[index][i]].push_back(blocks[index][i]);
		blocks[index].pop_back();
	}
}

void move()
{
	int a, b;
	int index_a, index_b;
	char option[5];
	
	scanf(" %d %s %d", &a, option, &b);

index_a=find_block(a);
	index_b=find_block(b);

if(index_a == index_b)
		return;

if(a==b)
		return;
	if( strcmp(option, "onto")==0 )
	{
		returning(b);
	}	
	returning(a);
	
	blocks[index_b].push_back(blocks[index_a][blocks[index_a].size()-1]);
	blocks[index_a].pop_back();
}

void pile()
{
	int a, b;
	int index_a, index_b, i;
	char option[5];
	vector<int> tmp;
	
	scanf(" %d %s %d", &a, option, &b);

index_a=find_block(a);
	index_b=find_block(b);

if(index_a == index_b)
		return;

if( strcmp(option, "onto")==0 )
	{
		returning(b);
	}
	
	for(i=blocks[index_a].size()-1; ; i--)//
	{
		tmp.push_back(blocks[index_a][i]);
		blocks[index_a].pop_back();
		if(tmp[tmp.size()-1]==a)
			break;
	}
	for(i=tmp.size()-1; tmp.empty()==0; i--)//
	{
		blocks[index_b].push_back(tmp[i]);
		tmp.pop_back();
	}
}

int get_com()
{
	char com[5];
	
	scanf("%s", com);
	if( strcmp(com, "quit")==0 )
		return 0;
	
	else if( strcmp(com, "move")==0 )
		move();
	else
		pile();
	return 1;
}

void print()
{
	int i,j;
	for(i=0; i<n; i++)
	{
		printf("%d:",i);
		for(j=0; j<blocks[i].size(); j++)
		{
			printf(" %d",blocks[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	scanf("%d",&n);

init();	
	while( get_com() );
	print();
}

이 글이 유익하다면 (굽신굽신) ->

Tag // UVA, 프로그래밍

Trackback(0) : Comment(2)

Trackback Address >> http://zfanta.com/trackback/442

Lonewolf dlbo 2009/03/25 00:49 address modify / delete reply
헛. 이건 저 귀찮아서 안풀고 있던 문제군요 ㅋㅋㅋㅋㅋ
- address modify / delete 2009/04/04 18:51 　환타
  저도 금방풀릴 줄 알고 귀찮아서 미뤘는데 예상외로 오래걸렸어요 ㅋㅋ

지환태

'Programming/algorithm'에 해당되는 글 7건

2009 정보올림피아드 지역본선 문제 2

Trackback Address >> http://zfanta.com/trackback/457

Subject: 2009 정보올림피아드 지역본선 문제 Review (2)-1

2009 정보올림피아드 지역본선 문제 나도 풀어보기

Trackback Address >> http://zfanta.com/trackback/450

Subject: 2009 정보올림피아드 지역본선 문제 Review (1)

UVa. 101 - The Blocks Problem 번역

블록 문제

배경

문제

입력

출력

출력 예시

Trackback Address >> http://zfanta.com/trackback/442

Category

Tags

Recent Post

Recent Comment

Link