연습 문제 168: 고양이 쥐 잡기 ★ ★

1853 단어 알고리즘vc++6.0
사나 운 고양이 한 마리 가 쥐 를 많이 잡 아 왔 습 니 다. 그리고 이 고양 이 는 큰 식 사 를 하기 시 작 했 습 니 다.그러나 남 들 과 다 르 게 보이 기 위해 특별한 식사 순 서 를 사용 했다. 먼저 걸음 길이 k 를 정 한 다음 에 첫 번 째 자리 에 있 는 것 을 먹 은 다음 에 k 마다 쥐 한 마 리 를 한 번 더 먹 은 후에 첫 번 째 자리 부터 계속 먹 었 고 마지막 에 쥐 한 마리 만 남 을 때 까지 먹었다.그리고 이 마지막 쥐 는 이 고양 이 를 놓 아 줄 것 이다. 생태 균형 을 깨 고 싶 지 않 기 때문에 이 쥐 가 내년 에 n 마 리 를 만 들 기 를 바란다...(물론 짝 을 어떻게 찾 든 상관 하지 않 습 니 다...) 하지만 이 쥐 들 중 한 마 리 는 아주 똑똑 합 니 다. 죽지 않 기 를 바 랍 니 다. 계산 을 통 해 처음부터 특별한 위치 에 서 있 었 습 니 다. 마지막 으로 죽지 않 고 풀 려 났 습 니 다. 어느 위치 에 서 있 는 지 아 세 요?입력: 여러 그룹의 테스트 데이터, 각 줄 마다 두 개의 정수 n 과 k (1 < = n, k < = 1000000) n 과 k 의 의 미 를 설명 합 니 다.          1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1 라운드:  0   0   0   0   0 2 라운드:    0       0        0 3 라운드:        0 2 라 운 드 를 거 친 후 8 번 만 먹 히 지 않 았 습 니 다. 62 를 예 로 들 면:          1, 2, 3, 4, 5, 6 1 라운드:  0     0 2 라운드:    0       0 3 라운드:      0 3 라 운 드 를 지나 고 5 번 만 남 았 습 니 다.
난이도: 쉬 움
http://www.yzfy.org/dis/listpost.php?tid=1076&extra=page%3D1
// catchmouse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define PB_ID 168
#define CP_VC6

#include "string.h"
#include "stdio.h"
#define MAXN 1000
int num[MAXN];

int main(int argc, char* argv[])
{

	int n, k, i, j, ans, g;
	while( scanf("%d%d", &n, &k) != EOF)
	{
		ans =0;
		memset(num, 0, sizeof(num));
		for(i=0; i<=n-1; i++)
		{
			if(num[i]) continue;              //i       
			num[i] = 1;
			if(ans == n-1)			break;
			ans++;
			if(ans == n-1)			break;
			g = 0;
			for(j=i+1; j<=n-1; j++)
			{
				if(num[j]) {g++;continue;}
				else if((j-i-g)%(k+1) == 0)
				{
					num[j] = 1;
					if(ans == n-1) break;
					ans++;
					if(ans == n-1) break;
				}
			
			}
		if(ans == n-1)	break;
		}
		i = 0;
		while(num[i++]);
		printf("%d
", i); } return 0; }

좋은 웹페이지 즐겨찾기