گزارش سوالات مسابقه ی ZOJ Monthly, October 2006

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2764

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2765

نوع سوال: جستجو

توضیح راه حل : چون سایز مساله نسبتا کوچک است، می توان از جستجوی ساده استفاده کرد. راه حل جستجوی من در 0.02 ثانیه Accepted شد. برای درک بهتر، کد تابع جستجوی زیر را نگاه کنید:

void bt( int x, int y, int dir, int moves = 0 ) {
	if( moves >= result )
		return;
	visited[x][y] = true;
	if( x == tx && y == ty )
		result <?= moves;
	else {
		int nx = dx[dir] + x;
		int ny = dy[dir] + y;
		if( nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] ) {
			if( board[nx][ny] == 0 )
				bt( nx, ny, dir, moves );
			else if( board[nx][ny] < 5 ) {
				bt( nx, ny, ( dir + 1 ) % 4, moves + (piece[(dir+1)%4][(dir+2)%4] != board[nx][ny] ) );
				bt( nx, ny, ( dir + 3 ) % 4, moves + (piece[(dir+3)%4][(dir+2)%4] != board[nx][ny] ) );
			}
			else
				bt( nx, ny, dir, moves + (piece[(dir+2)%4][dir] != board[nx][ny]) );
		}
	}
	visited[x][y] = false;
}

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2766

نوع سوال: ریاضی

توضیح راه حل : رابطه ی بازگشتی سوال به صورت زیر خواهد بود:

function F( n ):
  if n == 0:
    return 0
  result = 0
  for i in [0,n-1]:
    result += result + F( i ) + 1
  return result / n;
end;

اگر رابطه ی بالا را بررسی کنیم، به دست می آوریم که ، پس برابر عدد هارمونیک i-ام می باشد. فرمول دقیقی برای محاسبه ی این تابع وجود ندارد، ولی تقریب زير، برای n های بزرگ، مثلا بزرگتر از 100 دقت کافی را دارا می باشد و تا 8 رقم مورد نیاز دقت کافی را دارد:

که در آن برابر با ثابت ثابت اویلر-ماشرونی می باشد و مقدار تقریبی آن برابر است با: .

پس جواب را برای n های کوچک با for حساب می کنیم و برای n های بزرگ با استفاده از رابطه ی بالا.

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2767

نوع سوال: تکرار ساده

توضیح راه حل : برای رسیدن از t به m دو راه وجود دارد:

• یا اینکه با کلیدهای بالا و پائین مستقیما به m برویم.
• یا ابتدا به یک کانال خاص برویم، و سپس از کلید های بالا و پائین استفاده کنیم.

برای حالت دوم، صفحاتی که برنامه ی من در نظر گرفته است و آن ها را چک کرده است، به صورت است که در آن بخشی از ابتدای m، و دو رقم می باشند. برای درک بهتر، به بخشی از کد Accept شده نگاه کنید:

int64 length( int64 n )
{
	if( n == 0 )
		return inf;
	int64 result = 0;
	while( n ) {
		result ++;
		if( bad[n % 10] )
			return inf;
		n /= 10;
	}
	return result;
}
 
int64 join( int64 n, int64 x, int64 y )
{
	for( int64 i = 0; i < x; i ++ )
		n = n * 10 + y;
	return n;
}
 
void check( int n )
{
	result <?= length(n) + 1 + abs( n - m );
}
 
void check()
{
	int64 r = 0;
	for( int64 i = 0; i < M.length(); i ++ )
	{
		for( int j = 0; j < 10; j ++ )
			for( int k = 0; k < 10; k ++ )
				check( join( r * 10 + j, M.length() - i - 1, k ) );
		r = r * 10 + M[i] - '0';
	}
}

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2768

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2769

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2770

نوع سوال: حریصانه

توضیح راه حل : بازه ها را بر حسب انتهایشان مرتب می کنيم، و ابتدا بازه ی را پردازش می کنيم که زودتر به پایان می رسد. در هنگام پردازش هر بازه، سعی می کنیم در خانه های انتهایی آن بازه سرباز قرار دهيم. پيچيدگی زمانی اين راه حل خواهد شد.

لینک سوال: http://acm.zju.edu.cn/show_problem.php?pid=2771

نوع سوال: برنامه سازی پویا + اعداد صحیح با دقت بالا

توضیح راه حل : هر زير مساله را به صورت سه تایی (تعداد بازتابش ها، سطح جاری، جهت) در نظر می گیریم. فقط دقت کنید که جواب در بدترین حالت در 64 بیت جا نمی شود، و اینکه نیازی نیست آرایه ی برنامه سازی پویا را به ازای هر ورودی از اول بسازیم.