Talsu.net ::

'Study/Programming Challenges'에 해당되는 글 12건

2009/10/15 Programming Challenges - 작은 비숍(Little Bishops)
2009/10/12 Programming Challenges - 동맹 휴업 (Hartal) (1)
2009/10/12 Programming Challenges - 포커 패 (Poker Hands)

Study/Programming Challenges2009/10/15 00:46

Programming Challenges - 작은 비숍(Little Bishops)

문제 <- 클릭

이런 스타일의 문제에 약하다 생각 했는데 역시 힘들다.. 풀긴 했으나 시간 제한에 자꾸 걸린다 그것도 턱없이..

시험 몇일 남지도 않았는데 왠지 이런 스타일의 문제가 나올꺼 같아 불안 하다..
어쨋든 아직 미완..

#include <iostream>
#include <vector>
#include <deque>
//class FieldOld{
//	typedef std::pair<int, int> POS;
//	std::vector<POS> stack;
//	int fieldSize;
//public:
//	FieldOld(int size):fieldSize(size){}
//
//	int get(int x, int y){
//		if(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))
//			return -1;
//		POS pos(x,y);
//		std::vector<POS>::iterator it;
//		for(it = stack.begin(); it!= stack.end(); ++it){
//			if((*it) == pos)
//				return 1;
//		}
//		return 0;
//	}
//	void push(int x, int y){
//		POS pos(x,y);
//		stack.push_back(pos);
//	}
//	void pop(){
//		if(!stack.empty())
//			stack.pop_back();
//	}
//
//	int size(){
//		return fieldSize;
//	}
//
//	int stackSize(){
//		return stack.size();
//	}
//
//
//};

class Field{
	typedef std::pair<int, int> POS;
	std::deque<POS> stack;

//std::vector< std::vector<int> > field;
	char field[8][8];
	int fieldSize;
public:
	Field(int size):fieldSize(size){
		//field.resize(size);
		//std::vector< std::vector<int> >::iterator it;
		//for(it = field.begin(); it!=field.end(); ++it){
		//	it->resize(size);
		//	std::vector<int>::iterator iit;
		//	for(iit = it->begin(); iit!= it->end(); ++iit){
		//		*iit = 0;
		//	}
		//}
		for(int i = 0 ; i < 8; ++i){
			for(int j = 0; j < 8; ++j){
				field[i][j] = 0;
			}
		}

}

int get(int x, int y){
		if(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))
			return -1;
		//POS pos(x,y);
		//std::vector<POS>::iterator it;
		//for(it = stack.begin(); it!= stack.end(); ++it){
		//	if((*it) == pos)
		//		return 1;
		//}
		if(field[x][y] == 1)
			return 1;
		return 0;
	}
	void push(int x, int y){
		POS pos(x,y);
		stack.push_back(pos);
		field[x][y]=1;
//		attack(x,y,-1);
	}
	void pop(){
		if(!stack.empty()){
			/*POS pos(*(stack.end()));*/
			//field[pos.first][pos.second] = 0;
			POS pos = *(stack.rbegin());
			field[pos.first][pos.second] = 0;
//			attack(pos.first,pos.second,1);

stack.pop_back();
		}
	}

int size(){
		return fieldSize;
	}

int stackSize(){
		return stack.size();
	}

//void attackField(int x, int y, int damage){
	//	field[x][y]+=damage;
	//}

//int attackDirection(int x, int y, int xx, int yy, int damage) {  
	//	int value = get(x + xx, y + yy);
	//	if (value == -1)  
	//		return 0;  
	//	if (value == 0 || value == -2){
	//		attackField(x+xx, y+yy, damage);
	//		return attackDirection(x + xx, y + yy, xx, yy, damage);  
	//	}
	//	return 1;
	//}

//void attack(int x, int y, int damage){
	//	attackDirection(x,y,1,1,damage);
	//	attackDirection(x,y,1,-1,damage);
	//	attackDirection(x,y,-1,1,damage);
	//	attackDirection(x,y,-1,-1,damage);

//}

};

class LittleBishops{

int numberOfBishops;
	unsigned long long counter;
	Field field;

int checkDirection(int x, int y, int xx, int yy) {  
		int value = field.get(x + xx, y + yy);
		if (value == -1)  
			return 0;  
		if (value == 0 ) {
			return checkDirection(x + xx, y + yy, xx, yy);  
		}
		return 1;
	}

bool isAttack(int x, int y){
		//for (int i = -1; i <= 0; i++) {  
		//	for (int j = -1; j <= 1; j++) {  
		//		if (i != 0 && j != 0)  
		//			if (checkDirection(x, y, i, j) == 1)  
		//				return true;  
		//	}  
		//}

if (checkDirection(x, y, -1, 1) == 1)  
						return true;  
			if (checkDirection(x, y, -1, -1) == 1)  
						return true;  
		
		return false;
	}

void print(){
		for(int x = 0; x < field.size(); ++x){
			for( int y = 0; y < field.size(); ++y){
				std::cout<<field.get(x,y)<<" ";
			}
			std::cout<<std::endl;
		}
		std::cout<<std::endl;
	}

public:
	LittleBishops(int fieldSize, int numberOfBishops)
		:field(fieldSize),
		numberOfBishops(numberOfBishops),
		counter(0)
	{

}

int run(int startX, int startY){
		
		if(field.stackSize() == numberOfBishops){
			counter++;
			//print();
			field.pop();
			return 0;
		}
		for(int x = startX; x < field.size(); ++x){
			if(x != startX)
				startY = 0;
			for( int y = startY; y < field.size(); ++y){
				
				if(field.get(x,y) == 0 && !isAttack(x,y)){
					field.push(x,y);
					run(x,y);

}

}
		}
		field.pop();

return 1;
	}

unsigned long long getCount(){
		return counter;
	}

};

int main(){
	int size, number;
	while(true){
		std::cin>>size;
		std::cin>>number;
		if(size == 0 && number == 0)
			break;
		LittleBishops lb(size,number);
		//		lb.run();
		lb.run(0,0);
		std::cout<<lb.getCount()<<std::endl;
	}

return 0;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Study > Programming Challenges' 카테고리의 다른 글

Programming Challenges - 작은 비숍(Little Bishops) (0)	2009/10/15
Programming Challenges - 동맹 휴업 (Hartal) (1)	2009/10/12
Programming Challenges - 포커 패 (Poker Hands) (0)	2009/10/12
Programming Challenges - 유쾌한 점퍼(Jolly Jumpers) (0)	2009/10/11
Programming Challenges - 호주식 투표법(Australian Voting) (0)	2009/10/08
Programming Challenges - 체크 확인 (Check the Check) (1)	2009/10/05

Posted by 탈수

TAG Algorithm, Little Bishops, Programming Challenges, 알고리즘, 작은 비숍, 재귀

Trackback 0 Comment 0

Study/Programming Challenges2009/10/12 11:16

Programming Challenges - 동맹 휴업 (Hartal)

문제 <- 클릭

간단하다. 왜 레벨 2인지 모르겠고 왜 자료구조문제로 분류되어 있는지 잘 모르겠다. 의도한 방법으로 푼게 아닐지도..;.

#include <iostream>
#include <vector>

class PoliticalParty { //정당
	int hartalParameter; //휴업지수
public:
	PoliticalParty(int _hartalParameter) {
		hartalParameter = _hartalParameter;
	}

bool isHartal(int day) {
		if ((day % 7 == 0) || (day % 7 == 6))
			return false;
		if (day % hartalParameter == 0)
			return true;
		return false;
	}

};

class Hartal {
	int days;
	std::vector<PoliticalParty> politicalPartys;
public:
	Hartal(int _days) {
		days = _days;
	}

void input(int hartalParameter) {
		PoliticalParty pp(hartalParameter);
		politicalPartys.push_back(pp);
	}

bool isHartal(int day) {
		std::vector<PoliticalParty>::iterator it;
		for (it = politicalPartys.begin(); it != politicalPartys.end(); ++it) {
			if ((*it).isHartal(day))
				return true; //어느정당이든 발견되면 그날은 휴업
		}
		return false;
	}

int getNumberOfHartalDays() {
		int counter = 0;
		for (int i = 1; i <= days; ++i)
			if (isHartal(i))
				counter++;
		return counter; //휴업일수를 세어봄
	}

};

int main() {
	int numberOfCase;
	std::cin >> numberOfCase;
	for (int i = 0; i < numberOfCase; ++i) {

int days;
		std::cin >> days;
		Hartal hartal(days);

int numberOfPartys;
		std::cin >> numberOfPartys;

for (int j = 0; j < numberOfPartys; ++j) {
			int hartalParameter;
			std::cin >> hartalParameter;
			hartal.input(hartalParameter);
		}

std::cout << hartal.getNumberOfHartalDays() << std::endl;
	}

return 0;
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Study > Programming Challenges' 카테고리의 다른 글

Programming Challenges - 작은 비숍(Little Bishops) (0)	2009/10/15
Programming Challenges - 동맹 휴업 (Hartal) (1)	2009/10/12
Programming Challenges - 포커 패 (Poker Hands) (0)	2009/10/12
Programming Challenges - 유쾌한 점퍼(Jolly Jumpers) (0)	2009/10/11
Programming Challenges - 호주식 투표법(Australian Voting) (0)	2009/10/08
Programming Challenges - 체크 확인 (Check the Check) (1)	2009/10/05

Posted by 탈수

TAG Algorithm, Hartal, Programming Challenges, 동맹 휴업, 알고리즘, 파업

Trackback 1 Comment 1

Study/Programming Challenges2009/10/12 02:01

Programming Challenges - 포커 패 (Poker Hands)

문제 <- 클릭

별로 어렵진 않은데 시간이 많이 걸리는 예제 였다. 입출력이 까답롭지 않아서 인지 금방 성공 하긴 했지만 시간 날때 좀더 다듬고 싶다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>

struct _Card {
	int pattern;
	int value;
	bool operator==(const _Card& rhs) {
		return (*this).value == rhs.value;
	}
};

typedef struct _Card Card;
typedef std::vector<Card> CardSet;

class CompareValue {
public:
	bool operator()(const Card& lhs, const Card& rhs) {
		return lhs.value > rhs.value;
	}
};

class PokerCardSet {
private:
	enum {
		CLUB,
		DIAMOND,
		HEART,
		SPADE,
		TEN = 10,
		JACK = 11,
		QUEEN = 12,
		KING = 13,
		ACE = 14
	};
	enum {
		BLACK, WHITE
	};

CardSet cardSet;
	int score;

void setCard(char value, char pattern) {
		Card card;
		switch (pattern) {
		case 'C':
			card.pattern = CLUB;
			break;
		case 'D':
			card.pattern = DIAMOND;
			break;
		case 'H':
			card.pattern = HEART;
			break;
		case 'S':
			card.pattern = SPADE;
			break;
		default:
			card.pattern = pattern - '0';
			break;
		}

switch (value) {
		case 'T':
			card.value = TEN;
			break;
		case 'J':
			card.value = JACK;
			break;
		case 'Q':
			card.value = QUEEN;
			break;
		case 'K':
			card.value = KING;
			break;
		case 'A':
			card.value = ACE;
			break;
		default:
			card.value = value - '0';
			break;
		}
		cardSet.push_back(card);
	}

int highCard() {
		return score = highCard(cardSet);
	}

int highCard(CardSet& cardSet) {
		std::sort(cardSet.begin(), cardSet.end(), CompareValue());
		int sumCardValue = 0;
		int digit = 0;
		for (CardSet::reverse_iterator it = cardSet.rbegin(); it
				!= cardSet.rend(); ++it) {
			sumCardValue += (*it).value * std::pow((double) 15,
					(double) digit++);
		}
		return sumCardValue;
	}

int onePair() {
		int compareCounter = 0;
		Card currentCard;
		int pairCounter = 0;
		CardSet diffrentSet;
		CardSet sameSet;
		CardSet returnCardSet;
		std::sort(cardSet.begin(), cardSet.end(), CompareValue());

for (CardSet::iterator it1 = cardSet.begin(); it1 != cardSet.end(); ++it1) {
			compareCounter = 0;
			currentCard = *it1;
			for (CardSet::iterator it2 = cardSet.begin(); it2 != cardSet.end(); ++it2) {
				if (*it1 == *it2)
					++compareCounter;
			}

if (compareCounter == 2) {
				sameSet.push_back(currentCard);
				pairCounter++;
			} else if (compareCounter == 1) {
				diffrentSet.push_back(currentCard);
			}
		}
		diffrentSet.insert(diffrentSet.begin(), sameSet.begin(), sameSet.end());

if (pairCounter == 2)
			return score = 2000000 + highCard(diffrentSet);
		else
			return 0;
	}

int twoPair() {
		int compareCounter = 0;
		Card currentCard;
		int pairCounter = 0;
		CardSet returnCardSet;
		std::sort(cardSet.begin(), cardSet.end(), CompareValue());
		Card diffrentCard;

for (CardSet::iterator it1 = cardSet.begin(); it1 != cardSet.end(); ++it1) {
			compareCounter = 0;
			for (CardSet::iterator it2 = cardSet.begin(); it2 != cardSet.end(); ++it2) {
				if (*it1 == *it2) {
					++compareCounter;
					currentCard = *it1;
				} else {
					diffrentCard = *it1;
				}
			}
			if (compareCounter == 2) {
				returnCardSet.push_back(currentCard);
				pairCounter++;
			}
		}
		returnCardSet.push_back(diffrentCard);

if (pairCounter == 4)
			return score = 3000000 + highCard(returnCardSet);
		else
			return 0;
	}

int threeOfAKind() {
		int compareCounter = 0;
		int currentCard = 0;
		for (CardSet::iterator it1 = cardSet.begin(); it1 != cardSet.end(); ++it1) {
			compareCounter = 0;
			currentCard = (*it1).value;
			for (CardSet::iterator it2 = cardSet.begin(); it2 != cardSet.end(); ++it2) {
				if (*it1 == *it2)
					++compareCounter;
			}
			if (compareCounter == 3) {
				return score = 4000000 + currentCard;
			}
		}
		return 0;
	}

int straight() {
		std::sort(cardSet.begin(), cardSet.end(), CompareValue());
		CardSet::iterator it;
		it = cardSet.begin();
		int value = (*it++).value;
		int bigCard = value;
		for (; it != cardSet.end(); ++it) {
			if (--value != (*it).value)
				return 0;
		}
		return score = 5000000 + bigCard;
	}

int flush() {
		CardSet::iterator it;
		it = cardSet.begin();
		int pattern = (*it++).pattern;
		for (; it != cardSet.end(); ++it) {
			if (pattern != (*it).pattern)
				return 0;
		}
		return score = 6000000 + highCard(cardSet);
	}

int fullHouse() {
		int threeCard = 0;
		int twoCard = 0;
		int compareCounter = 0;
		int currentCard = 0;
		for (CardSet::iterator it1 = cardSet.begin(); it1 != cardSet.end(); ++it1) {
			compareCounter = 0;
			currentCard = (*it1).value;
			for (CardSet::iterator it2 = cardSet.begin(); it2 != cardSet.end(); ++it2) {
				if (*it1 == *it2) {
					++compareCounter;

}
			}
			if (compareCounter == 3) {
				threeCard = currentCard;
			}
			if (compareCounter == 2) {
				twoCard = currentCard;
			}
		}

if (threeCard && twoCard)
			return score = 7000000 + threeCard;
		else
			return 0;
	}

int fourOfAKind() {

for (CardSet::iterator it1 = cardSet.begin(); it1 != cardSet.end(); ++it1) {
			int compareCounter = 0;
			int returnCard = (*it1).value;
			for (CardSet::iterator it2 = cardSet.begin(); it2 != cardSet.end(); ++it2) {
				if (*it1 == *it2)
					++compareCounter;
			}
			if (compareCounter == 4)
				return score = 8000000 + returnCard;
		}
		return 0;
	}

int straightFlush() {
		CardSet::iterator it;
		it = cardSet.begin();
		int pattern = (*it).pattern;
		for (; it != cardSet.end(); ++it) {
			if (pattern != (*it).pattern)
				return 0;
		}

std::sort(cardSet.begin(), cardSet.end(), CompareValue());

it = cardSet.begin();
		int value = (*it).value;
		int bigCard = value;
		++it;
		for (; it != cardSet.end(); ++it) {
			if (--value != (*it).value)
				return 0;
		}

return score = 9000000 + bigCard;
	}

void getScore() {

if (straightFlush())
			return;
		else if (fourOfAKind())
			return;
		else if (fullHouse())
			return;
		else if (flush())
			return;
		else if (straight())
			return;
		else if (threeOfAKind())
			return;
		else if (twoPair())
			return;
		else if (onePair())
			return;
		else if (highCard())
			return;
		else
			return;

}
public:
	PokerCardSet() :
		score(0) {
	}

PokerCardSet(std::string str) {
		setCards(str);
	}

void setCards(std::string str) {
		std::stringstream ss(str);
		std::string strCard;
		for (int i = 0; i < 5; ++i) {
			ss >> strCard;
			setCard(strCard[0], strCard[1]);
		}
		getScore();
	}

bool operator>(const PokerCardSet& rhs) {
		return (*this).score > rhs.score;
	}

bool operator<(const PokerCardSet& rhs) {
		return (*this).score < rhs.score;
	}

bool operator==(const PokerCardSet& rhs) {
		return (*this).score == rhs.score;
	}

};

class Poker {
	PokerCardSet blackSet;
	PokerCardSet whiteSet;
public:
	Poker(std::string str) {
		blackSet.setCards(str.substr(0, 14));
		whiteSet.setCards(str.substr(15, str.length()));
	}

void play() {
		if (blackSet > whiteSet)
			std::cout << "Black wins." << std::endl;
		else if (whiteSet > blackSet)
			std::cout << "White wins." << std::endl;
		else if (blackSet == whiteSet)
			std::cout << "Tie." << std::endl;
	}

};

int main() {
	std::string buffer;

while (true) {
		std::getline(std::cin, buffer);
		if (buffer.empty())
			break;
		Poker poker(buffer);
		poker.play();
	}
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'Study > Programming Challenges' 카테고리의 다른 글

Programming Challenges - 작은 비숍(Little Bishops) (0)	2009/10/15
Programming Challenges - 동맹 휴업 (Hartal) (1)	2009/10/12
Programming Challenges - 포커 패 (Poker Hands) (0)	2009/10/12
Programming Challenges - 유쾌한 점퍼(Jolly Jumpers) (0)	2009/10/11
Programming Challenges - 호주식 투표법(Australian Voting) (0)	2009/10/08
Programming Challenges - 체크 확인 (Check the Check) (1)	2009/10/05

Posted by 탈수

TAG Algorithm, poker, Programming Challenges, stl, 알고리즘, 포커

Trackback 0 Comment 0

«이전 1 2 3 4 다음»

일	월	화	수	목	금	토
				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

태터데스크 관리자

태터데스크 메시지

Talsu.net

'Study/Programming Challenges'에 해당되는 글 12건

Programming Challenges - 작은 비숍(Little Bishops)

'Study > Programming Challenges' 카테고리의 다른 글

TRACKBACK http://talsu.net/trackback/128

Programming Challenges - 동맹 휴업 (Hartal)

'Study > Programming Challenges' 카테고리의 다른 글

TRACKBACK http://talsu.net/trackback/125

Programming Challenges - 포커 패 (Poker Hands)

'Study > Programming Challenges' 카테고리의 다른 글

TRACKBACK http://talsu.net/trackback/124

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크