태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Notice

2011.12.17 16:03 Talk

문제좀 풀어두래니까..

내가 군대에서까지 번역을 해야겠냐 ㅡㅠㅡ?

'Talk' 카테고리의 다른 글

이런 안착한 녀석들  (1) 2011.12.17
그럼  (4) 2011.06.07
지알원 왔다감. 공공장소에 테러하다니 -_-  (2) 2011.05.01
또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
posted by Sparking
2011.08.12 13:54 Solutions/Mr.K's Solution
ㅋㅋㅋ

너무 정석대로 풀었나
뭔가 빨리 돌리는 방법이 있을텐뎈ㅋ


#include 
using namespace std;

void zeroset( int ary[][9] );
int numfind( int ary[][9], int bry[][9], int wtf );

int find[10]; // 숫자 k(k번째 원소)를 몇개나 찾았는가에 해당하는 배열

int main()
{
	char str[90];
	int a[9][9]; // 풀어야되는 스도쿠
	int b[9][9]; // 메모지
	int i, j;
	int temp;

	while(1)
	{
		gets(str);

		if( strcmp( str, "end" ) == 0 )
		{
			break;
		}

		for( i = 0; i <= 9; i++ )
		{
			find[i] = 0;
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				if( str[i*9+j] == '.' )
				{
					a[i][j] = 0;
				}
				else
				{
					a[i][j] = str[i*9+j] - '0';
					find[a[i][j]]++;
					find[0]++;
				}
			}
		}

		while( find[0] < 81 )
		{
			// 스도쿠 연산
			for( i = 1; i <= 9; i++ )
			{
				zeroset( b );
				for( j = 0; j < 2; j++ )
				{
					if( find[i] < 9 )
					{
						temp = numfind( a, b, i );
					}
					if( temp == 0 )
					{
						// 찾는 숫자가 없거나 숫자 대입을 하지 않았으면 함수를 2번 돌릴 필요가 없음
						j++;
					}
				}
			}
		}

		for( i = 0; i < 9; i++ )
		{
			for( j = 0; j < 9; j++ )
			{
				printf( "%d", a[i][j] );
			}
		}
		printf("\n");
	}

	return 0;
}

void zeroset( int ary[][9] )
{
	int i, j;

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			ary[i][j] = 0;
		}
	}
}

int numfind( int ary[][9], int bry[][9], int wtf ) // wtf : isn't what the fu*k, want to find
{
	int i, j, k, m;
	int esc = 1;
	int count;
	int tempr, tempc;

	// wtf 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] == wtf )
			{
				bry[i][j] = 2;
				esc = 0;
			}
		}
	}

	// wtf가 현재 스도쿠에 없음
	if( esc == 1 )
	{
		return 0;
	}

	// wtf가 위치할 수 없는 범위 체크
	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( bry[i][j] == 2 )
			{
				for( k = 0; k < 9; k++ )
				{
					bry[i][k] = 1;
					bry[k][j] = 1;
				}
				for( k = (i/3)*3; k < (i/3)*3+3; k++ )
				{
					for( m = (j/3)*3; m < (j/3)*3+3; m++ )
					{
						bry[k][m] = 1;
					}
				}

				bry[i][j] = 2;
			}
		}
	}

	for( i = 0; i < 9; i++ )
	{
		for( j = 0; j < 9; j++ )
		{
			if( ary[i][j] != 0 && bry[i][j] == 0 )
			{
				bry[i][j] = 1;
			}
		}
	}

	// wtf가 유일하게 들어갈 수 있으면 대입
	for( i = 0; i < 3; i++ )
	{
		for( j = 0; j < 3; j++ )
		{
			count = 0;
			for( k = i*3; k < (i+1)*3; k++ )
			{
				for( m = j*3; m < (j+1)*3; m++ )
				{
					if( bry[k][m] == 0 )
					{
						tempr = k;
						tempc = m;
						count++;
					}
				}
			}

			if( count == 1 )
			{
				ary[tempr][tempc] = wtf;
				find[wtf]++;
				find[0]++;
				esc = 1;
			}
		}
	}

	return esc;
}
 
posted by Milkskin
2011.08.11 20:04 Solutions/Dlbo's Solution
아 나

스도쿠 한번 풀기 더럽게 빡치네

이게 얼마나 걸린거야 -_- 
#include 
#include 

#define SIBAL 750
#define CIBAL 350
#define V SIBAL*CIBAL

int U[V], D[V];
int L[V], R[V];
int C[V], ROW[V];
int H[SIBAL], S[CIBAL];
int size;
char s[10][10];
int nimiral1[SIBAL], nimiral2[SIBAL], OK[87];
char nimhi[SIBAL];

void Link(int r, int c)
{
    S[c]++ ;
	C[size] = c;
    ROW[size] = r;
    U[size] = U[c];
	D[U[c]] = size;
    D[size] = c;
	U[c] = size;

    if (H[r] ==  - 1)
	{
		H[r] = L[size] = R[size] = size;
	}
    else
    {
        L[size] = L[H[r]];
		R[L[H[r]]] = size;
        R[size] = H[r];
		L[H[r]] = size;
    }

    size++ ;
}

void remove(int c)
{
    int i, j;

    L[R[c]] = L[c];
    R[L[c]] = R[c];

    for (i = D[c]; i != c; i = D[i])
    {
        for (j = R[i]; j != i; j = R[j])
        {
            S[C[j]]-- ;
            U[D[j]] = U[j];
            D[U[j]] = D[j];
        }
    }
}

void resume(int c)
{
    int i, j;

    for (i = U[c]; i != c; i = U[i])
    {
        for (j = L[i]; j != i; j = L[j])
        {
            S[C[j]]++ ;
            U[D[j]] = D[U[j]] = j;
        }
    }

    R[L[c]] = L[R[c]] = c;
}

int Jotto(int k)
{
    int i, j, Min, c;

    if (!R[0])
	{
		return 1;
	}

    for (Min = SIBAL, i = R[0]; i; i = R[i])
	{
		if (Min > S[i])
		{
			Min = S[i];
			c = i;
		}
	}

    remove(c);

    for (i = D[c]; i != c; i = D[i])
    {
        for (j = R[i]; j != i; j = R[j])
		{
            remove(C[j]);
		}

        OK[k] = ROW[i];

        if (Jotto(k + 1))
		{
			return 1;
		}

        for (j = L[i]; j != i; j = L[j])
		{
            resume(C[j]);
		}
    }

    resume(c);
    return 0;
}

int main()
{
    int i, j, k, r;
    char st[87];

    while (gets(st))
    {
		if (st[0] == 'e')
		{
			break;
		}

        i = 0;

        for (j = 1; j <= 9; j++)
		{
            for (k = 1; k <= 9; k++)
			{
                s[j][k] = st[i++];
			}
		}
        for (i = 0; i <= 324; i++)
        {
            S[i] = 0;
            D[i] = U[i] = i;
            L[i + 1] = i;
			R[i] = i + 1;
        }

		R[324] = 0;
        size = 325;
        r = 0;
        memset(H,  - 1, sizeof(H));

        for (i = 1; i <= 9; i++)
        {
            for (j = 1; j <= 9; j++)
            {
                if (s[i][j] != '.')
                {
                    r++ ;
                    nimiral1[r] = i;
                    nimiral2[r] = j;
                    nimhi[r] = s[i][j];
                    Link(r, (i - 1)*9 + j);
                    Link(r, 81 + (i - 1)*9 + s[i][j] - '0');
                    Link(r, 162 + (j - 1)*9 + s[i][j] - '0');
                    Link(r, 243 + ((i - 1)/3)*27  + ((j - 1)/3)*9  + s[i][j] - '0');    
                }
                else 
                {
                    for (k = 1; k <= 9; k++)
                    {
                        r++ ;
                        nimiral1[r] = i;
                        nimiral2[r] = j;
                        nimhi[r] = k + '0';
                        Link(r, (i - 1)*9 + j);
                        Link(r, 81 + (i - 1)*9 + k);
                        Link(r, 162 + (j - 1)*9 + k);
                        Link(r, 243 + ((i - 1)/3)*27  + ((j - 1)/3)*9  + k );        
                    }
                }
            }
        }

        Jotto(0);

        for (i = 0; i<81; i++)
		{
            s[nimiral1[OK[i]]][nimiral2[OK[i]]] = nimhi[OK[i]];
		}
        for (i = 1; i<= 9; i++)
		{
            for (j = 1; j <= 9; j++)
			{
                printf("%d", s[i][j] - '0');
			}
		}
        puts("");
    }

    return 0;
}
지금쯤 훈련소를 나왔을 지군에게 이 코드를 바침 -_-
posted by Lonewolf dlbo
TAG 스도쿠
2011.06.07 00:00 Talk

다녀오겠습니다.

이놈들은 내가 군대가는날까지 풀이도 안하네..

'Talk' 카테고리의 다른 글

이런 안착한 녀석들  (1) 2011.12.17
그럼  (4) 2011.06.07
지알원 왔다감. 공공장소에 테러하다니 -_-  (2) 2011.05.01
또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
posted by Sparking
2011.05.01 23:15 Talk
시망....

띠어내느라 죽는줄 알았네 -_-

보니까 그래피티 같이 몰래 그리거나 붙여놓고 튀는 종류 같은데

아무리 그래도 그렇지 공공장소에 어떻게 이렇게 개념없이 해놨는지 원...

누군진 모르겠지만 전국 곳곳마다 하고 다니는거 같은데 걍 콱 신고해버릴까보다 -_-;

그나저나, 스도쿠 이거 속도내서 푸는 로직을 만들라 했는데 빡시구먼

Mr.Prec은 아직 솔루션 안나왔나염?

나 좀만 더 짱구 굴려보고 안되면 걍 2차원 배열 쌔려서 풀어버릴래 ㄱ-

'Talk' 카테고리의 다른 글

이런 안착한 녀석들  (1) 2011.12.17
그럼  (4) 2011.06.07
지알원 왔다감. 공공장소에 테러하다니 -_-  (2) 2011.05.01
또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
posted by Lonewolf dlbo
2011.04.30 06:16 Talk

안풀기 시작함

'Talk' 카테고리의 다른 글

그럼  (4) 2011.06.07
지알원 왔다감. 공공장소에 테러하다니 -_-  (2) 2011.05.01
또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
잠수가 길었습니다.  (0) 2011.03.02
posted by Sparking

스도쿠
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5294 Accepted: 1578

설명

스도쿠에서는 9 × 9 크기의 격자가 3 × 3 크기의 더 작은 격자들로 나뉘어져있습니다. 예를 들면,

. 2 7 3 8 . . 1 .
. 1 . . . 6 7 3 5
. . . . . . . 2 9
3 . 5 6 9 2 . 8 .
. . . . . . . . .
. 6 . 1 7 4 5 . 3
6 4 . . . . . . .
9 5 1 8 . . . 7 .
. 8 . . 6 5 3 4 .

격자 안에 몇몇개의 숫자가 주어졌을 때,  당신은 남은 칸들에 1부터 9까지의 숫자들을 집어넣어야 하는데 이때 1부터 9까지의 각 숫자들은 (1) 9개의 3 × 3 격자 안에 1개씩, (2) 9개의 가로 줄 안에 1개씩, (3) 9개의 세로 줄 안에 1개씩 들어가야 합니다.

입력

테스트 파일의 입력은 복수의 테스트 케이스들로 구성될 수 있습니다. 각 테스트 케이스는 81개의 문자를 한 줄로 나타내는데 이것은 스도쿠 격자의 81개의 칸을 나타내며, 위에서부터 가로 한 줄씩 표기합니다. 각 문자는 1부터 9까지의 숫자 혹은 채워지지 않은 칸을 나타내는 점으로 나타냅니다. 입력된 스도쿠에 대해 단 하나의 정답만이 존재한다는 것을 명심하세요. 파일의 끝을 표기할 때는 한 줄에 “end” 라고 입력하시면 됩니다.

출력

각 테스트 케이스에 대해, 완성된 스도쿠 퍼즐을 한 줄로 출력하시면 됩니다.

입력 예시

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

출력 예시

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking
Sudoku
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5294 Accepted: 1578

Description

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

. 2 7 3 8 . . 1 .
. 1 . . . 6 7 3 5
. . . . . . . 2 9
3 . 5 6 9 2 . 8 .
. . . . . . . . .
. 6 . 1 7 4 5 . 3
6 4 . . . . . . .
9 5 1 8 . . . 7 .
. 8 . . 6 5 3 4 .

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

Sample Output

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3074. Sudoku  (0) 2011.04.18
PKU 3364. Black and white painting  (0) 2011.04.05
UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
posted by Sparking
2011.04.14 22:33 Solutions/Mr.K's Solution



사뿐하게 AC
어려운 문제인줄 알았는데 아니었구만 :)

#include 
using namespace std;

int main()
{
	int n, m, c;
	int temp;

	cin >> n >> m >> c;

	while( (n != 0) || (m != 0) || (c != 0) )
	{
		temp = (n - 7) * (m - 7);

		if( (temp % 2 == 1) && (c == 1) )
		{
			cout << temp / 2 + c << endl;
		}
		else
		{
			cout << temp / 2 << endl;
		}

		cin >> n >> m >> c;
	}

	return 0;
}
posted by Milkskin
2011.04.09 15:48 Solutions/Dlbo's Solution
#include 

using namespace std;

int main()
{
	int n, m, c;

	while(cin >> n >> m >> c)
	{
		if (n == 0 && m == 0 && c == 0)
		{
			break;
		}

		if(n < 8 || m < 8)
		{
			cout << 0 << endl;
			continue;
		}

		if(n % 2 != 0 || m % 2 != 0)
		{
			if (c >= 1)
			{
				cout << (m - 7) * (n - 7) / 2 << endl;
				continue;
			}
			else
			{
				cout << (m - 7) * (n - 7) / 2 << endl;
				continue;
			}
		}
		else
		{
			if(c >= 1)
			{
				cout << (m - 8) * (n - 8) / 2 + 1 + (n - 8) / 2 + (m - 8) / 2 << endl;
				continue;
			}
			else
			{
				cout << (n - 8) * (m - 8) / 2 + (n - 8) / 2 + (m - 8) / 2 << endl;
			}
		}
	}
}



부어어어어

귀차니즘. 
posted by Lonewolf dlbo
2011.04.06 20:45 Solutions/Dlbo's Solution
#include 
#include 

char words[101][300], input[10000];
int n, m, now, tot;
int out[10];

void fuck(int x)
{
    int i, k;
    if (x == tot)
    {
        k = 0;

        for (i = 0; input[i]; i++)
        {
            if (input[i] == '#')
			{
                printf("%s", words[now]);
			}
            else
			{
                putchar(out[k++] + '0');
			}
        }

        putchar('\n');

        return;
    }
   

    for (i = 0; i < 10; i++)
    {
        out[x] = i;
        fuck(x + 1);
    }
}

int main()
{
    int i, j;
    while (~scanf("%d", &n))
    {
        getchar();

        for (i = 0; i < n; i++)
		{
            gets(words[i]);
		}

        puts("--");
        scanf("%d", &m);
        getchar();

        for (i = 0; i < m; i++)
        {
            gets(input);
            tot = 0;

            for (j = 0; input[j]; j++)
            {
                if (input[j] == '0')
				{
                    tot++;
				}
            }

            for (j = 0; j < n; j++)
            {
                now = j;
                fuck(0);
            }
        }
    }

    return 0;
}  


ㄹㄹㄹㄹ

걍 단어사전 만들어서

갔다가 이어붙이기 ㄹㄹㄹ
posted by Lonewolf dlbo
흑백 채색
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2092 Accepted: 1396

설명

당신은 현대 그림이 많이 전시되어 있는 Centre Pompidou 를 방문중입니다. 특히 당신은 마치 체스판처럼 오로지 검은색과 흰색의 사각형들로만 이루어진 한 그림을 주목합니다 (맞닿은 사각형들은 같은 색이 아닙니다). 그런데 이 그림을 그린 화가는 그림을 그릴 때 problem A 의 도구를 사용하지 않았습니다.

너무도 심심했던 당신은, 이 작품 속에 얼마나 많은  8 × 8 크기의 체스판이 들어갈 수 있는지 알고 싶어졌습니다. 체스판의 오른쪽 제일 아래칸은 반드시 흰 색이어야 합니다.

입력

입력은 여러 개의 테스트 케이스들로 이루어집니다. 각 테스트 케이스들은 한 줄에 세 개의 정수  n, m 그리고 c. 를 포함하는데(8 ≤ n, m ≤ 40000), n 은 그림의 가로줄의 수를, m 은 그림의 세로줄의 수를 의미합니다. c 는 언제나 0 또는 1인데, 0은 오른쪽 제일 아래칸이 검은색인걸 의미하고 1은 오른쪽 제일 아래칸이 흰색인걸 의미합니다.

입력의 마지막을 의미하는 테스트 케이스에는 3 개의 0을 입력합니다.

출력

각 테스트 케이스에 대해서 얼마나 많은 체스판이 주어진 그림의 크기에 들어갈 수 있는지를 출력하면 됩니다.

입력 예시

8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0

출력 예시

0
1
2
799700028

Source

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking
Black and white painting
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2092 Accepted: 1396

Description

You are visiting the Centre Pompidou which contains a lot of modern paintings. In particular you notice one painting which consists solely of black and white squares, arranged in rows and columns like in a chess board (no two adjacent squares have the same colour). By the way, the artist did not use the tool of problem A to create the painting.

Since you are bored, you wonder how many 8 × 8 chess boards are embedded within this painting. The bottom right corner of a chess board must always be white.

Input

The input contains several test cases. Each test case consists of one line with three integers n, m and c. (8 ≤ n, m ≤ 40000), where n is the number of rows of the painting, and m is the number of columns of the painting. c is always 0 or 1, where 0 indicates that the bottom right corner of the painting is black, and 1indicates that this corner is white.

The last test case is followed by a line containing three zeros.

Output

For each test case, print the number of chess boards embedded within the given painting.

Sample Input

8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0

Sample Output

0
1
2
799700028

Source

'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3074. Sudoku  (0) 2011.04.18
PKU 3364. Black and white painting  (0) 2011.04.05
UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
posted by Sparking
2011.03.31 14:45 Talk
안풀다니

'Talk' 카테고리의 다른 글

지알원 왔다감. 공공장소에 테러하다니 -_-  (2) 2011.05.01
또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
잠수가 길었습니다.  (0) 2011.03.02
티스토리 블로그 다시 쓰기로 결ㅋ정ㅋ  (0) 2011.02.02
posted by Sparking

628 - Passwords

Time limit: 3.000 seconds

여러 서버에 여러개의 계정을 둔 사람은 당연히 여러 가지의 비밀번호를 기억해야 합니다. 그리고 어떤 사람이 비밀번호를 잊어버린 상황을 충분히 상상할 수 있을겁니다. 그/그녀 가 기억하고 있는 것은 오직 단어 x, y 그리고 z 와 두 개의 숫자입니다: 하나는 시작하는 숫자이고 다른 하나는 끝나는 숫자입니다.


당신은 이제 주어진 단어와 규칙을 기반으로 하여 비밀번호의 가능성이 있는 모든 것을 찾아내는 프로그램을 작성해야 합니다. 예를 들어 주어진 3 개의 단어:
x, y, z 와 주어진 규칙이 0#0 라면, 이 규칙은 <숫자><사전식 단어><숫자> 의 형태로 나타나야 합니다.

입력 

첫 번째 줄은 사전에 있는 단어들의 숫자를 나타냅니다(n). 각 단어들은 n 개의 연속적인 줄로 나타냅니다. 그 다음 줄은 규칙의 개수를 나타냅니다(m). 비슷하게, 각 규칙 역시 m 개의 연속적인 줄로 나타냅니다. 각 규칙에는 특수문자 `#' 와 `0' 가 임의로 나오게 됩니다. 특수문자 `#' 는 사전상의 단어를 나타내며 특수문자 `0' 는 숫자를 나타냅니다.

입력할 데이터는 여러 개의 사전식 단어들과 거기에 따른 규칙들을 포함합니다.

출력 

각 경우의 '사전 + 규칙' 에 따라 2개의 하이픈으로 구분되도록 선을 긋고, 그 뒤에 가능성이 있는 모든 비밀번호들을 연속적인 줄 형식으로 나타나도록 출력합니다. 이 때, 규칙이 여러개 있는 경우엔 첫번째 규칙에 대해 분류된 비밀번호들을 전부 나열한 후 두번째 규칙에 대해 분류된 비밀번호들을 전부 나열하는, 규칙의 순서에 따라 정렬시켜야 합니다. 또한 단어과 규칙에 따라 정렬할 때 숫자가 포함된다면, 반드시 오름차순으로 정렬시켜야 합니다.


가정: 사전에 있는 단어의 수는 0 보다 크고 100보단 작거나 같습니다 ( $0 < n \le 100$). 단어의 길이는 0 보다 크고 256 보단 작습니다. 단어들은 `
A'..`Z',`a'..`z',`0'..`9' 과 같은 문자들을 모두 포함할 수 있습니다. 규칙의 개수는 1000 보다 작으며, 규칙은 256 개의 문자보다 짧습니다. 문자 `0' 는 규칙에 있어서 7번 이상 나오지 않지만, 최소한 1번은 나와야만 합니다. 문자 `#' 는 필수적이지 않기 때문에 규칙에 꼭 나와야 할 필요는 없습니다.

입력 예시 

2
root
2super
1
#0
1
admin
1
#0#

출력 예시 

--
root0
root1
root2
root3
root4
root5
root6
root7
root8
root9
2super0
2super1
2super2
2super3
2super4
2super5
2super6
2super7
2super8
2super9
--
admin0admin
admin1admin
admin2admin
admin3admin
admin4admin
admin5admin
admin6admin
admin7admin
admin8admin
admin9admin

 


Miguel A. Revilla
2000-01-10

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3074. Sudoku  (2) 2011.04.18
PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
posted by Sparking

628 - Passwords

Time limit: 3.000 seconds

Having several accounts on several servers one has to remember many passwords. You can imagine a situation when someone forgets one of them. He/she remembers only that it consisted of words x, y and z as well as two digits: one at the very beginning and the other one at the end of the password.


Your task is to write a program which will generate all possible password on the basis of given dictionary and set of rules. For the example given above the dictionary contains three words:
x, y, z, and the rule is given as 0#0 what stands for SPMamp<digit><word_from_the_dictionary><digit>&.

Input 

First line contains a number of words in the dictionary (n). The words themselves are given in n consecutive lines. The next line contains number of rules (m). Similarly consecutive m lines contain rules. Each rule consists of characters `#' and `0' given in arbitrary order. The character `#' stands for word from the dictionary whilst the character `0' stands for a digit.

Input data may contain many sets of dictionaries with rules attached two them.

Output 

For each set `dictionary + rules' you should output two hyphens followed by a linebreak and all matching passwords given in consecutive lines. Passwords should be sorted by rules what means that first all passwords matching the first rule and all words must be given, followed by passwords matching the second rule and all words, etc. Within set of passwords matching a word and a rule an ascending digit order must be preserved.


Assumptions: A number of words in the dictionary is greater than 0 and smaller or equal to 100 ( $0 < n \le 100$). Length of the word is greater than 0 and smaller than 256. A word may contain characters `
A'..`Z',`a'..`z',`0'..`9'.A number of rules is smaller than 1000, and a rule is shorter that 256 characters. A character `0' may occur in the rule no more than 7 times, but it has to occur at least once. The character `#' is not mandatory meaning there can be no such characters in the rule.

Sample Input 

2
root
2super
1
#0
1
admin
1
#0#

Sample Output 

--
root0
root1
root2
root3
root4
root5
root6
root7
root8
root9
2super0
2super1
2super2
2super3
2super4
2super5
2super6
2super7
2super8
2super9
--
admin0admin
admin1admin
admin2admin
admin3admin
admin4admin
admin5admin
admin6admin
admin7admin
admin8admin
admin9admin

 


Miguel A. Revilla
2000-01-10

'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3074. Sudoku  (0) 2011.04.18
PKU 3364. Black and white painting  (0) 2011.04.05
UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
posted by Sparking
2011.03.23 01:10 Talk
[PKU 3176. Cow Bowling - 최근번역문제]과

[PKU 1163. The Triangle - 예전번역문제]

문제 중복 신고합니당 :)


어쩐지 ㅋㅋ 처음 봤을 때 한번 풀어봤다 싶었는데//


아 그리고
개인 홈피? 링크 수정할거면

http://mr-prec.tistory.com/
으로 수정좀 :) 

'Talk' 카테고리의 다른 글

또다시  (1) 2011.04.30
일주일이 지났는데도  (1) 2011.03.31
ㅋㅋ 기분탓이 아니었구만  (1) 2011.03.23
잠수가 길었습니다.  (0) 2011.03.02
티스토리 블로그 다시 쓰기로 결ㅋ정ㅋ  (0) 2011.02.02
해킨토시 오라질 안올라가네요 -_-  (0) 2011.01.24
posted by Milkskin
2011.03.23 00:44 Solutions/Mr.K's Solution
소점프건은 들보의 코드를 꼼꼼히 읽어보지 않은 내 실수였소 -_-

대충 설명해놓은 뉘앙스라 좀 찜찜하지만, 어쨌든 저게 최상의 풀이인 것 같아 난 손떼기로 ㅋ…
( 일단은 AC 받았기 때문이기도 하고, 가끔은 내가 쓴 코드지만 건드릴 엄두가 안난다 ㅋㅋㅋ )




{ 1000, 10 }에 대한 답을 출력하는데 1분 이상, 5분 이하의 시간이 소요되는듯//
( 엔터쳐놓고 잠깐 보고있다가 이닦고 왔더니 답이 출력되어있어서 그렇게 추정 )

일단 현재 코드는 recursion으로 쓴 상태이고, 
{ 1000, 10 }에 대한 답이 잘 나오는 것으로 보아
이 recursion을 iteration으로 잘 바꾸면 AC 받을듯//

코드는 요 근래 작성한 것 중에 가장 무식하게 작성해놓아서 공개하기가 부끄럽구려 ㅋㅋㅋ
그래도 AC받으면 공개함 ㅋㅋ 
posted by Milkskin
2011.03.19 18:43 Solutions/Dlbo's Solution
#include 
#include 

using namespace std;

set tool;
set::iterator sit;
int tot, n, k, cnt, checker[15][1121];

void maketool()
{
	int i;
	bool isPrime;

	tool.insert(2);
	tool.insert(3);

	for (i = 5; i <= 1120; i += 2)
	{
		isPrime = true;
		for (sit = tool.begin(); sit != tool.end(); sit++)
		{
			if (i % *(sit) == 0)
			{
				isPrime = false;
				break;
			}
		}

		if (isPrime)
		{
			tool.insert(i);
		}
	}
}

int main()
{
	int i, j, k, l;
	set::iterator dit;
	maketool();

	while (cin >> n >> k)
	{
		if (n == 0 && k == 0)
		{
			break;
		}

		memset(checker, 0, sizeof(checker));
		checker[0][0] = 1;

		for(j = 0, dit = tool.begin(); j < tool.size() && *(dit) <= n; j++, dit++)
		{
			for(i = k; i >= 1; i--)
			{
				for(l = n; l >= *(dit); l--)
				{
					checker[i][l] += checker[i - 1][l - *(dit)];
				}
			}
		}
		cout << checker[k][n] << endl;
	}
}

이런 쒯

짜증나게 더럽네 ㄱ-

고생 더럽게 했음요.

처음엔 소수를 tool 셋을 이용해 DFS로 탐색했으나,

100 5만 해도 거의 안드로메다급 탐색시간을 보여줘서 GG

그리고 다시 곰곰히 생각해보니 k가 커봐야 14라는 점을 기억해내고, 저런 알고리즘을 짜내봤습니다.

checker의 k, n번째 있는게 답이고,

소수의 리스트를 전부 싹다 더해보고 비벼보고 하면서 checker 배열에 가능한 갯수들을 체크해

넣어보되, 그 탐색 범위를 소수 내에서, k개 골라서, n보다 작고 현재 검사중인 소수보다 큰 놈을 이용해서

뭐 이거 설명하기도 더럽네 -_-

여튼 그렇게 비비고 볶고 해서 맵을 만들어서(자기 자신만으로 답인거, 2개 합해서 되는거, 3개 해서 되는거, .... k개 해서 되는거) 

로 최종 결산해 답을 가져오는 코드입니다.

진짜 더럽다 ㄱ- 
posted by Lonewolf dlbo
2011.03.16 00:10 Solutions/Mr.K's Solution



정말 간만에 문제를 푼다는 느낌을 제대로 받는구만 ㅋㅋ


그리고 들보자식이 어느정도 사기(?)를 치고 있었다는 것도 알게 되었고//

최근에 올라온 [소점프 ac get] 글은
문제에 나온 예시만 돌려도 답을 얻을 수 없으니까
가급적 빠른 시일 내에 수정하도록 -_-;


// PKU 2181. Jumping Cows

#include 
using namespace std;

int s[150000];
int indexbound;

int calc( int start, int end, int isreverse )
{
	int i;
	int temp;
	int max, maxindex;
	int min, minindex;
	int result = 0;

	max = min = s[start];
	maxindex = minindex = start;
	for( i = start; i <= end; i++ )
	{
		if( max < s[i] )
		{
			max = s[i];
			maxindex = i;
		}
		if( min > s[i] )
		{
			min = s[i];
			minindex = i;
		}
	}

	if( start > end ) { return 0; }

	if( maxindex > minindex && !isreverse )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex, end, 0 );
	}
	else if( maxindex < minindex && !isreverse )
	{
		result += calc( start, maxindex-1, 0 );
		result += calc( maxindex+1, minindex-1, 1 );
		result += calc( minindex+1, end, 0 );
		result += max - min;
	}
	else if( maxindex > minindex && isreverse )
	{
		result += calc( start, minindex-1, 1 );
		result += calc( minindex+1, maxindex-1, 0 );
		result += calc( maxindex+1, end, 1 );
		result += max - min;
	}
	else if( maxindex < minindex && isreverse )
	{
		result += calc( start, maxindex, 1 );
		result += calc( maxindex+1, end, 1 );
	}
	else if( maxindex == minindex )
	{
		if( indexbound < maxindex )
		{
			indexbound = maxindex;
		}
	}

	return result;
}

int main()
{
	int p;
	int i;
	int height;

	scanf( "%d", &p );

	for( i = 0; i < p; i++ )
	{
		scanf( "%d", &s[i] );
	}

	if( p == 1 )
	{
		printf( "%d\n", s[0] );
	}
	else
	{
		height = calc( 0, p-1, 0 );
		
		// correction
		if( indexbound == 0 )
		{
			height += s[0];
		}
		else
		{
			int i;
			int max, maxindex;
			int min, minindex;

			max = min = s[indexbound];
			maxindex = minindex = indexbound;
			for( i = indexbound; i < p; i++ )
			{
				if( max < s[i] )
				{
					max = s[i];
					maxindex = i;
				}
				if( min > s[i] )
				{
					min = s[i];
					minindex = i;
				}
			}

			if( maxindex == p-1 )
			{
				height += max;
			}
			else
			{
				height += min;
			}
		}

		printf( "%d\n", height );
	}
	
	return 0;
}


풀이를 쓰다가,
내가 만들었던 예시에서 안맞는 부분이 발생하여

일단 풀이는 중단하고 코드만 올려놓았음//

그럼에도 AC가 나온건
아마 pku 서버 내의 테스트케이스를 모두 통과했기 때문이겠지 -_-;;
posted by Milkskin
2011.03.14 20:11 Solutions/Dlbo's Solution
#include 
#include 

int cal[1000];

int chk(const void * a,const void * b)
{
	if (*(int*)a > *(int*)b)
	{
		return -1;
	}
	else if (*(int*)a == *(int*)b)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int main()
{
	int cases, n, t, w, i, j, max;

	scanf("%d", &cases);
	while(cases--)
	{
		max = 0;
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d", &cal[i]);
			if (cal[i] > max)
			{
				max = cal[i];
			}
		}

		qsort(cal, n, sizeof(int), chk);

		for (i = n - 1; i >= 0; i--)
		{
			if (cal[i] * (i + 1) > max)
			{
				max = cal[i] * (i + 1);
			}
		}

		printf("%d\n", max);
	}

	return 0;
}


우쒸 몸 열라리 아프네요

숨을 못쉬어 -_-

그냥 간단합니다.

제일 약한 로프만큼만 걸 수 있으니까

큰 숫자부터 소트 때려버리고

가장 작은 숫자부터 버틸 수 있는 무게 * 밧줄 갯수

한 값이 가장 크면 그게 답입니다.

간단히 말해서 10 1 15면

15 10 1로 소트해놓고

1부터 역으로 1 * 3은 3이니 최대 3,

10 * 2는 20이니 최대 20

15 * 1은 15니 최대 15

이중 답은 20

요렇게 풀어나가면 간단.
posted by Lonewolf dlbo
서로 다른 두 소수의 합
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 2398 Accepted: 1474

설명

어떤 양정수는 한 가지 이상의 서로 다른 소수들의 합으로 나타낼 수 있습니다. 주어진 두 개의 양정수 n 과 k 를 놓고 볼 때, 당신은 n 이라는 양정수를 k 개의 서로 다른 소수들의 합으로 나타내는 방법을 찾아내야 합니다. 다음에 나오는 예시를 보면 확실하겠지만, 같은 소수 집합으로 합의 순서만 바꾸는 것은 같은 방법을 썼다고 간주합니다. 예를 들어 8 은 3 + 5 와 5 + 3 으로 표현 될 수 있지만 이 두 방법은 구별할 수 없기 때문에 하나의 방법입니다.

만약 n 과 k 가 각각 24 와 3 이라면 답은 2가 되는데 그 이유는 {2, 3, 19} 라는 소수집합과 {2, 5, 17} 라는 소수집합, 이 두 집합의 원소들의 합이 24로 같기 때문입니다. 그리고 이 두 집합의 원소들을 제외한 다른 세 개의 소수들의 합으론 24를 만들 수 없습니다. 예를 들어 n = 24 와 k = 2,가 주어졌다면 답은 3개가 되는데 그 이유는 세 개의 집합 {5, 19}, {7, 17} 그리고 {11, 13} 이 있기 때문입니다. 또 n = 2 와 k = 1,이 주어졌다면 답은 1이 되는데 그 이유는 단 하나의 집합{2} 만 이 합이 가능하기 때문입니다. 한편 n = 1 이고 k = 1,이면 답은 0 이 됩니다. 1 은 소수가 아니기 때문에 이런 방식으로 셀 수 없기 때문이지요. 그리고 n = 4 이고 k = 2,라면 그 역시 답이 0이 되는데, 그 이유는 서로 다른 두 개의 소수의 합으로 4를 나타낼 수 없기 때문에 그렇습니다.

주어진 n 과 k 에 대해서 위와 같은 방식으로 답을 찾는 프로그램을 작성하는 것이 당신이 해야 할 일입니다.

입력

입력할 때 데이터셋은 하나의 줄에 두 개의 양정수 n 과 k 를 포함하는데, 이 두 수 사이에는 공백을 두어 입력합니다. 이 때  n ≤ 1120 까지, 그리고 k ≤ 14 까지 가능합니다. 입력을 종료할 때는 두 양정수의 위치에 0 을 각각 넣어서 종료합니다.

출력

입력된 각 데이터셋에 대해서 연관된 한 줄로 출력합니다. 출력할때는 하나의 음이 아닌 정수를 내보내는데, 이 정수는 입력에서 주어진 두 양정수 n 과 k 를 놓고 표현 가능한 방법의 가지수를 나타냅니다. 출력하는 값은 231 보다 작습니다.

입력 예시

24 3 
24 2 
2 1 
1 1 
4 2 
18 3 
17 1 
17 3 
17 4 
100 5 
1000 10 
1120 14 
0 0

출력 예시

2 
3 
1 
0 
0 
2 
1 
0 
1 
55 
200102899 
2079324314

Source

Japan 2006

p.s: 입력 부분 해석이 저만 이상한가요? 일단 문제에 맞게 해석해서 올려봅니다.. Lonewolf dlbo의 조언을 통해 의문을 해결하였습니다.(-)

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3364. Black and white painting  (1) 2011.04.05
UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
posted by Sparking
Sum of Different Primes
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 2398 Accepted: 1474

Description

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5 + 3 but the are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are not other sets of three primes that sum up to 24. For n = 24 and k = 2, the answer is three, because there are three sets {5, 19}, {7, 17} and {11, 13}. For n = 2 and k = 1, the answer is one, because there is only one set {2} whose sum is 2. For n = 1 and k = 1, the answer is zero. As 1 is not a prime, you shouldn’t count {1}. For n = 4 and k = 2, the answer is zero, because there are no sets of two different primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the given n and k.

Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integers n and kseparated by a space. You may assume that n ≤ 1120 and k ≤ 14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of the ways for n and k specified in the corresponding dataset. You may assume that it is less than 231.

Sample Input

24 3 
24 2 
2 1 
1 1 
4 2 
18 3 
17 1 
17 3 
17 4 
100 5 
1000 10 
1120 14 
0 0

Sample Output

2 
3 
1 
0 
0 
2 
1 
0 
1 
55 
200102899 
2079324314

Source

'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3364. Black and white painting  (0) 2011.04.05
UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
posted by Sparking
2011.03.11 23:00 Solutions/Mr.K's Solution

이것은 마치

2차방정식의 극한값(최대값)을 찾는 문제와 같구려 ㄲㄲ

처음에 정렬함수 만들기가 귀찮아서 라이브러리함수 갖다 쓰려고 잔머리 굴렸다가 wa ㅋㅋㅋㅋ


// PKU 2291. Rotten Ropes

#include 
using namespace std;

void bbsort( int *ary, int length )
{
	int i, j;

	for( i = 0; i < length-1; i++ )
	{
		for( j = length-2; j >= i; j-- )
		{
			if( ary[j] > ary[j+1] )
			{
				swap( ary[j], ary[j+1] );
			}
		}
	}
}

int main()
{
	int t;
	int n;
	int w[1000];
	int i;
	int max;

	scanf( "%d", &t );

	while( t > 0 )
	{
		scanf( "%d", &n );

		for( i = 0; i < n; i++ )
		{
			scanf( "%d", &w[i] );
		}

		bbsort( w, n );

		max = 0;
		for( i = 1; i <= n; i++ )
		{
			if( max < i * w[n-i] )
			{
				max = i * w[n-i];
			}
		}

		printf( "%d\n", max );

		t--;
	}

	return 0;
}

아, 하나 덧붙여서

[소 점프]는 열심히 풀고있음 -_-; 알고리즘은 대강 다 만들었고 수정·보완중//
posted by Milkskin
썩은 밧줄
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4023 Accepted: 2620

설명

어떤 무거운 물체를 들어올리기 위해서 같은 길이인 n 개의 밧줄이 있다고 생각해봅시다. 이 때 각 밧줄들과 연결시켜 물체를 들어올리기 때문에 각 밧줄이 버틸수 있는 무게인 t 를 넘는 물건을 들어올리려고 하면 밧줄은 끊어집니다. 그러나 우리는 무거운 물체를 여러 개의 밧줄로 평행하게 묶어서 모든 밧줄을 끌어올리는 방법을 쓰면 무거운 물체도 들어올릴 수 있습니다. w 의 무게를 가진 무거운 물건을 들어올리기 위해 k 개의 밧줄을 사용한다면, 각 밧줄에 w/k 만큼의 무게가 주어진다고 가정합니다. 하지만 밧줄이 버틸수 있는 무게인 t 를 놓고 볼 때, w/k > t 가 된다면 밧줄은 끊어지게 됩니다. 예를 들어 3 개의 밧줄이 각각 버틸수 있는 무게가 1, 10, 15 라고 치면, 3 보다 무거운 무게를 가진 물건을 이 3 개의 밧줄을 묶어서 들어올리려 할 경우 가장 약한 밧줄이 끊어지기 때문에 3개의 밧줄을 전부 묶어서 들어올릴 수 없습니다. 그러나 두번째 밧줄은 그 자체만으로 10의 무게까지 들어올릴 수 있습니다. 각 밧줄이 버틸 수 있는 무게를 알려주면 당신은 주어진 밧줄들의 부분집합을 하나 골라서, 부분집합에 속한 밧줄들이 하나도 끊어지지 않고 물건을 들어올릴 수 있는 가장 무거운 무게를 알아내는 것입니다.

입력

입력의 첫 번째 줄은 하나의 정수 t (1 <= t <= 10) 를 쓰는데 뒤에 나올 테스트 케이스들의 개수를 나타냅니다. 각 테스트 케이스들의 첫 번째 줄은 하나의 정수 n (1 <= n <= 1000) 을 입력하는데, 이 n 은 밧줄의 개수를 나타냅니다. 그 다음으로 나오는 줄에는 1부터 10000까지의 범위 안에 있는 n 개의 정수들이 나오는데 각각은 밧줄이 끊어지지 않는 최대한의 무게를 나타내고, 각 무게들은 사이에 공백으로 띄어서 나타냅니다.

출력

테스트 케이스에서 주어진 밧줄들이 하나도 끊어지지 않는 최대한의 무게를 한 줄로 출력합니다.

입력 예시

2
3
10 1 15
2
10 15

출력 예시

20
20

Source

Tehran 2003

p.s: 일부분 수정했습니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

UVa 628. Passwords  (5) 2011.03.23
PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
posted by Sparking
Rotten Ropes
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4023 Accepted: 2620

Description

Suppose we have n ropes of equal length and we want to use them to lift some heavy object. A tear-off weight t is associated to each rope, that is, if we try to lift an object, heavier than t with that rope, it will tear off. But we can fasten a number of ropes to the heavy object (in parallel), and lift it with all the fastened ropes. When using k ropes to lift a heavy object with weight w, we assume that each of the k ropes, regardless of its tear-off weight, is responsible for lifting a weight of w/k. However, if w/k > t for some rope with tear-off weight of t, that rope will tear off. For example, three ropes with tear-off weights of 1, 10, and 15, when all three are fastened to an object, can not lift an object with weight more than 3, unless the weaker one tears-off. But the second rope, may lift by itself, an object with weight at most 10. Given the tear-off weights of n ropes, your task is to find the weight of the heaviest object that can be lifted by fastening a subset of the given ropes without any of them tearing off.

Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 1000) which is the number of ropes. Following the first line, there is a single line containing n integers between 1 and 10000 which are the tear-off weights of the ropes, separated by blank characters.

Output

Each line of the output should contain a single number, which is the largest weight that can be lifted in the corresponding test case without tearing off any rope chosen.

Sample Input

2
3
10 1 15
2
10 15

Sample Output

20
20

Source

'PKU & UVa problems > Original problem' 카테고리의 다른 글

UVa 628. Passwords  (0) 2011.03.23
PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (0) 2010.11.01
posted by Sparking
2011.03.06 13:17 Solutions/Dlbo's Solution
#include 

using namespace std;

int main()
{
	int n, i, j, cnt = 1, sum = 0, total = 0, temp = 0;
	int buf[150000];

	cin >> n ;

	for (i = 0; i < n; i++)
	{
		cin >> buf[i];
	}


	for(j = 1; j <= n; j++)
	{
		if(cnt % 2 != 0)
		{
			if(buf[j - 1] > buf[j])
			{
				temp = buf[j - 1];
				cnt++;
				sum += temp;
			}
		}
		else
		{
			if(buf[j] > buf[j - 1])
			{
				temp = buf[j - 1];
				cnt++;
				sum -= temp;
			}
		}
	}

	cout << sum << endl;

	return 0;
}

시망 -_- 스파킹 이자식 번역 한참 안하더니 이상해졌어

홀수번 포션을 마시면 +, 짝수번 포션을 마시면 -가 아니고, 실제 마신 순서대로 홀수번째 마시면 +, 짝수번째 마시면 -가 됩니다. 어떤 포션이던간에.

거기에, 한번 패스한 포션, 마신 포션은 무조건 패스.

앞에서부터 순차탐색으로 하나하나 오면서, 숫자 큰놈 하나 마시고,

먼저 마신놈보다 작은 숫자 하나 집어마시고,

그다음 다시 또 마시고,

다시 또 먼저 마신것보다 작은 숫자 하나 집어마시면서 진행하면 최대값 나옵니다.
posted by Lonewolf dlbo
점프하는 소들
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4560 Accepted: 2761

설명

농부 John의 소들은 동요에 나오는 것 처럼 달을 뛰어넘고 싶어합니다. 그러나 불행하게도 소들은 뛸 수 없습니다.

그 지역에 사는 주술사가 달을 뛰어넘고 싶어하는 소들의 부탁을 들어주기 위해 P (1 <= P <= 150,000) 개의 물약을 만들었습니다. 이 물약들은 조제된 순서대로 투약되는데 개중에 투약되지 않고 다음 물약으로 넘어가는 경우도 있습니다.

각 물약은 소들이 점프할 수 있는 'strength'  (1 <= strength <= 500)를 증가시켜줍니다. 각 소들이 물약을 마시는 순서를 놓고 볼 때, 홀수번째로 먹는 물약은 소의 점프능력을 증가시켜주고; 짝수번째로 먹는 물약은 소의 점프능력을 감소시킵니다. 물약을 먹기 전의 소의 점프능력은 당연히 0입니다.

모든 소는 자신에게 주어진 물약들 중 한 개 이상은 마셔야 합니다. 이 때, 물약의 성능에 따라 마실지 마시지 않을지를 판단하여 다음 물약으로 넘길 수 있고, 한 번 마셨거나 넘긴 물약은 다시 마실 수 없습니다.

어떤 물약을 투여했을 때 가장 높게 점프할 수 있는지를 알아내세요.

입력

* 첫번째 줄: 하나의 양정수 P 

* 두번째 줄부터 P+1번째 줄: 각 줄은 하나의 양정수가 들어가는데, 물약의 strengh 를 의미합니다. 2번째 줄은 첫번째 로 주어진 물약의 strength 이고; 3번째 줄은 두번째로 주어진 물약의 strength 이고; 이하 동일합니다.

출력

* 첫번째 줄: 최대로 점프할 수 있는 하나의 양정수. 

입력 예시

8
7
2
1
8
4
3
5
6

출력 예시

17

Source

USACO 2003 U S Open Orange


p.s: 미친소도 아니고 왜 동요에서 소들이 달로 뛰는거람 도대체..
p.s2: Lonewolf dlbo의 의견을 수렴하여 일부분 수정합니다.

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 3132. Sum of Different Primes  (3) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (2) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (1) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
posted by Sparking
Jumping Cows
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 4560 Accepted: 2761

Description

Farmer John's cows would like to jump over the moon, just like the cows in their favorite nursery rhyme. Unfortunately, cows can not jump. 

The local witch doctor has mixed up P (1 <= P <= 150,000) potions to aid the cows in their quest to jump. These potions must be administered exactly in the order they were created, though some may be skipped. 

Each potion has a 'strength' (1 <= strength <= 500) that enhances the cows' jumping ability. Taking a potion during an odd time step increases the cows' jump; taking a potion during an even time step decreases the jump. Before taking any potions the cows' jumping ability is, of course, 0. 

No potion can be taken twice, and once the cow has begun taking potions, one potion must be taken during each time step, starting at time 1. One or more potions may be skipped in each turn. 

Determine which potions to take to get the highest jump.

Input

* Line 1: A single integer, P 

* Lines 2..P+1: Each line contains a single integer that is the strength of a potion. Line 2 gives the strength of the first potion; line 3 gives the strength of the second potion; and so on. 

Output

* Line 1: A single integer that is the maximum possible jump. 

Sample Input

8
7
2
1
8
4
3
5
6

Sample Output

17

Source

'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3132. Sum of Different Primes  (0) 2011.03.13
PKU 2291. Rotten Ropes  (0) 2011.03.10
PKU 2181. Jumping Cows  (0) 2011.03.02
PKU 3032. Card Trick  (0) 2010.12.24
PKU 3176. Cow Bowling  (0) 2010.11.01
PKU 3085. Quick Change  (0) 2010.10.05
posted by Sparking
2011.03.02 02:56 Talk
그리고 팀블로그를 보는데 왜이리 슬프지..
새글이 별로 없네..
내탓인가(..)

그나저나 Mr.K,
닉 바꿨으면 미리 얘기를 해
그래야 게시판 이름 바꿔주지

posted by Sparking