[codeforces] Codeforces Round #280(Div.2) 물문제 특집

전송문: [codeforces] Codeforces Round #280(Div. 2)
492A. Vanya and Cubes
최대 i를 찾으면 1+2+3+...+i가 n보다 작고 i를 출력합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;

int n ;

void solve () {
	int cnt = 0 , i = 1 , sum = 1 ;
	while ( n >= sum ) {
		++ cnt ;
		n -= sum ;
		++ i ;
		sum += i ;
	}
	printf ( "%d
" , cnt ) ;;
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

492B. Vanya and Lanterns
정렬하고 두 점 사이의 거리를 2로 나누면 첫 번째 램프에서 시작, 마지막 램프에서 끝까지의 거리가 가장 커진다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const double eps = 1e-10 ;

int n , m ;
int a[MAXN] ;

int dcmp ( double x ) {
	return ( x > eps ) - ( x < -eps ) ;
}

void solve () {
	For ( i , 1 , n ) scanf ( "%d" , &a[i] ) ;
	sort ( a + 1 , a + n + 1 ) ;
	double maxv = max ( a[1] , m - a[n] ) ;
	rep ( i , 1 , n ) maxv = max ( maxv , ( a[i + 1] - a[i] ) / 2.0 ) ;
	printf ( "%.10f
" , maxv ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}

492C. Vanya and Exams
정렬하고 시뮬레이션합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 100005 ;
const double eps = 1e-10 ;

struct Node {
	LL a , b ;
	bool operator < ( const Node& t ) const {
		return b < t.b ;
	}
} a[MAXN] ;

LL n , r , avg ;

int dcmp ( double x ) {
	return ( x > eps ) - ( x < -eps ) ;
}

void solve () {
	LL sum = 0 ;
	LL ans = 0 ;
	LL tot = n * avg ;
	For ( i , 1 , n ) {
		scanf ( "%I64d%I64d" , &a[i].a , &a[i].b ) ;
		sum += a[i].a ;
	}
	if ( sum >= tot ) {
		printf ( "0
" ) ;
		return ;
	}
	sort ( a + 1 , a + n + 1 ) ;
	LL need = n * avg - sum ;
	For ( i , 1 , n ) {
		if ( need <= r - a[i].a ) {
			ans += need * a[i].b ;
			printf ( "%I64d
" , ans ) ;
			return ;
		}
		need -= r - a[i].a ;
		ans += ( r - a[i].a ) * a[i].b ;
	}
}

int main () {
	while ( ~scanf ( "%I64d%I64d%I64d" , &n , &r , &avg ) ) solve () ;
	return 0 ;
}

492D. Vanya and Computer Game
1/x, 1/y는 유저에게 1/y초에 약간의 데미지를 입히고 유저는 2/x초에 약간의 데미지를 입힙니다.
그리고 2분의 시간축은 몬스터를 처치하는 데 필요한 시간을 얻을 수 있고 이 시간은 반드시 x나 y를 제거할 수 있다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson l , m
#define rson m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

int n , x , y ;

void solve () {
	int a ;
	For ( i , 1 , n ) {
		scanf ( "%d" , &a ) ;
		LL l = 1 , r = 1e15 ;
		while ( l < r ) {
			LL m = mid ;
			LL atk = m / y + m / x ;
			if ( atk >= a ) r = m ;
			else l = m + 1 ;
		}
		if ( l % x == 0 && l % y == 0 ) printf ( "Both
" ) ;
		else if ( l % x == 0 ) printf ( "Vova
" ) ;
		else printf ( "Vanya
" ) ;
	}
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &x , &y ) ) solve () ;
	return 0 ;
}

492E. Vanya and Field
gcd(dx, n)=gcd(dy, n)=1이기 때문에 (0, 0)~(0, n-1)에서 출발점을 선택하면 서로 교차하지 않는 경로를 벗어나고 (여기서 교차하지 않는 것은 점만 중복 사용하지 않는다) 경로의 길이는 반드시 n이며 x축과 y축은 일일이 비치는 관계가 존재한다.
우리가 그 중의 한 경로를 구할 때, 우리는 이 경로로 다른 경로를 내놓을 수 있다.
편의를 위해 우리는 시뮬레이션 경로를 (0,0)점에서 출발하는 것으로 선택하고 f[x]=y를 x로 Y축에 비추는 (즉 좌표(x,y))로 설정하면 f[i*dx%n]=i*dy%n은 (0,0)점에서 출발하면 만나는 모든 점이다.
그러면 (0,k)에서 출발하는 경로는 f[x]+k=y+k=y', 즉 k=(y'-f[x]+n)%n이다.그러면 모든 점을 우리는 O(1)로 나누어 그것이 속하는 경로에 넣을 수 있다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson l , m
#define rson m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )

const int MAXN = 1000005 ;

int f[MAXN] ;
int n , m , dx , dy ;
int num[MAXN] ;

void solve () {
	int x = 0 , y = 0 , ans , maxv = 0 ;
	clr ( num , 0 ) ;
	For ( i , 0 , n ) {
		f[x] = y ;
		x = ( x + dx ) % n ;
		y = ( y + dy ) % n ;
	}
	For ( i , 1 , m ) {
		scanf ( "%d%d" , &x , &y ) ;
		++ num[( y - f[x] + n ) % n] ;
	}
	rep ( i , 0 , n ) {
		if ( num[i] > maxv ) {
			maxv = num[i] ;
			ans = i ;
		}
	}
	printf ( "%d %d
" , 0 , ans ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d%d" , &n , &m , &dx , &dy ) ) solve () ;
	return 0 ;
}