Accepted: 2515 Description This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect. It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? Input Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100. Output For each n, print in a single line the number of ways to connect the 2n numbers into pairs. Sample Input
2
3
-1
Sample Output
2
5
Source Shanghai 2004 Preliminary
/* 카틀란수+대수 연산, 처음에 스스로 공식을 밀어서 얻은 결론은 f(2*n)= f(0)* f(2*n-2)+ f(2)* f(2*n-4)+ f(4)* f(2*n-6)+...+f(2 * n - 2) * f(0); 그리고 순전히 점차적으로 계산한 결과 결과는 맞았지만 속도가 너무 느려서 시간을 초과했다.나중에 생각해 보니, 이게 바로 카틀란드 수가 아닌가?허허, 문제가 해결되었습니다 F (n) = F (0) * F (n - 1) + F (1) * F (n - 2) +... +F (n - 1) * F (0) = C (2 * n, n)/(n + 1), F (0) = 1 코드는 매우 길고 대부분 자신이 쓴 대수 연산 도구 템플릿입니다.정말 JAVA 물을 쓰고 싶지 않아요. 재미없어요. 하하*/#include#include#define BIGINTEGER_LEN_TYPE int #define MAX_N 201 using namespace std; string num[MAX_N]; string cval[MAX_N][MAX_N];//대수 덧셈string bigIntegerAdd(const string left, const string right) {BIGINTEGER_LEN_TYPE lenl = static_cast(left.size(), BIGINTEGER_LEN_TYPE lenr = static_cast(right.size(), std::string res = ";/get the minimum length of the two string BIGINTEG_ LEN_TYPE minLen = (lenl <=lenr)? lenl: lenr; BIGINTEGER_LEN_TYPE maxLen = (lenl <=lenr) ? lenr : lenl; std::string longerStr = (lenl <= lenr) ? right : left; int residue = 0, sum = 0, quotient = 0;//add operation, first part BIGINTEGER_LEN_TYPE pos1; for(pos1 = 0; pos1 <= minLen - 1; pos1++) { sum = (left[pos1] - '0') + (right[pos1] - '0') + quotient; quotient = sum/10; residue = sum % 10; res += residue + '0'; }//add operation, second part for(BIGINTEGER_LEN_TYPE pos2 = pos1; pos2 <= maxLen - 1; pos2++) { sum = (longerStr[pos2] - '0') + quotient; quotient = sum/10; residue = sum % 10; res += residue + '0'; }//add the extra carry while(quotient != 0) { residue = quotient % 10; quotient = quotient/10; res += residue + '0'; }//std::cout<<"res size:"<(left.length();BIGINTEGER_LEN_TYPE maxLen=static_cast(right.length();std::string longerStr =";std::string shorterStr ="; std::stringres = "";/get the longer and shortstrings and corresponded length if (left.length () <= right.length()) { minLen = static_cast(left.length()); maxLen = static_cast(right.length()); shorterStr = left; longerStr = right; } else { minLen = static_cast(right.length()); maxLen = static_cast(left.length()); shorterStr = right; longerStr = left; } BIGINTEGER_LEN_TYPE pos1 = 0; BIGINTEGER_LEN_TYPE pos2 = 0;//start from the first digit of the shorter string for(pos1 = 0; pos1 <= minLen - 1; pos1++) {//multiply each digit of the longer string int residue = 0, product = 0, quotient = 0; BIGINTEGER_LEN_TYPE curPos = 0; for(pos2 = 0; pos2 <= maxLen - 1; pos2++) { curPos = pos1 + pos2;//new space if(res.length() == 0 || curPos > int(res.length() - 1)) { product = (shorterStr[pos1] - '0') * (longerStr[pos2] - '0') + quotient; quotient = product/10; residue = product % 10; res += residue + '0'; }//space already exists, just add the original value to product else { product = (shorterStr[pos1] - '0') * (longerStr[pos2] - '0') + quotient + (res[curPos] - '0'); quotient = product/10; residue = product % 10; res[curPos] = residue + '0'; } }//process the extra quotient//start position curPos = maxLen + pos1; while(quotient != 0) { if(res.length() == 0 || curPos > int(res.length() - 1)) { residue = quotient % 10; quotient = quotient/10; res += residue + '0'; } else { quotient = quotient + (res[curPos] - '0'); residue = quotient % 10; quotient = quotient/10; res[curPos] = residue + '0'; } curPos++; } }//std::cout<(str.length()-1;for(;pos>= 0;pos--)revStr +=str[pos];return revStr;}//두 개의 큰 수의 크기 비교 int bigIntegerCmp(const string left, const string right) {BIGINTEGER_LEN_TYPE lenl = static_cast(left.length); BIGINTEGER_LEN_TYPE lenr = static_cast(right.length); if(lenllenr) return 1; return strcmp (getReverse (left).c_str (), getReverse (right).c_str ();}//대수 감법string bigIntegerSub(const string left, const string right) {std:string biggerStr =""; std:string smallerStr =""; std:string res =""; BIGINTEGER_LEN_TYPE minLen = 0; BIGINTEGER_LEN_TYPE maxLen = 0;/get the bigger integer and smaller integer intcmpres = bigIntegerCmp(left, right); if(. cmpres ==-1|cmpres == 0) {smallerStr = left;biggerStr = right;}else { smallerStr = right; biggerStr = left; }//get related size minLen = static_cast(smallerStr.length()); maxLen = static_cast(biggerStr.length()); int extra = 0, temp = 0, subRes = 0;//subtraction operation, first part BIGINTEGER_LEN_TYPE pos1; for(pos1 = 0; pos1 <= minLen - 1; pos1++) { int curL = biggerStr[pos1] - '0'; int curR = smallerStr[pos1] - '0'; temp = 0; while((subRes = (curL - curR + 10 * temp - extra)) < 0) temp++; res += subRes + '0'; extra = temp; }//subtraction operation, second part for(BIGINTEGER_LEN_TYPE pos2 = pos1; pos2 <= maxLen - 1; pos2++) { int curL = biggerStr[pos2] - '0'; temp = 0; while((subRes = (curL + 10 * temp - extra)) < 0) temp++; res += subRes + '0'; extra = temp; }//remove the zero at head while(res[res.length() - 1] == '0' && res.length() >= 2) res = res.substr(0, res.length() - 1);//std::cout<<"res size:"< right//initialize the related data quotient = ""; residual = ""; std::string dividend = left; std::string divisor = right; BIGINTEGER_LEN_TYPE lenDend = static_cast(left.length()); BIGINTEGER_LEN_TYPE lenDsor = static_cast(right.length()); std::string temp = ""; std::string curStr = ""; std::string tryStr = ""; BIGINTEGER_LEN_TYPE curPos = 0; int choice = 0; bool visitedFirst = false;//start from the head of the dividend for(curPos = lenDend - 1; curPos >= 0; curPos--) { curStr = dividend[curPos] + curStr;//curStr > divisor, can be processed if(bigIntegerCmp(curStr, divisor) >= 0) {//try the quotient from 1 to 10 until the result of choice * divisor is the biggest less than curStr for(choice = 1; choice <= 10; choice++) { temp = ""; temp += char(choice + '0'); tryStr = bigIntegerMult(divisor, temp); if(bigIntegerCmp(tryStr, curStr) > 0) { choice--; break; } }//right now, choice is just the current quotient and should be appended ahead to quotient quotient = char(choice + '0') + quotient; temp = ""; temp += char(choice + '0');//update curStr curStr = bigIntegerSub(curStr, bigIntegerMult(divisor, temp)); if(curPos == 0) residual = curStr;//set visitedFirst, visitedFirst is used to prevent producing '0' quotient visitedFirst = true; }//curStr is not enough to be divided by divisor, so the current quotient is '0' and should be appended to 'quotient' else if(visitedFirst) quotient = '0' + quotient; if(curPos == 0) { residual = curStr; break; } if(curStr == "0") curStr = ""; } residual = curStr; return; } string getCval(int p, int q) { if(p == q || q == 0) return "1"; if(q == 1) return getReverse(getStr(p)); if(cval[p][q] != "0") return cval[p][q]; return cval[p][q] = bigIntegerAdd(getCval(p - 1, q - 1), getCval(p - 1, q)); }//k의 카드란 수를 계산하고 다음 표는 0부터string solve1(intk) {if(num[k]!="0)return num[k];string quotient,residual;bigIntegerDiv(getCval(2*k,k), getReverse(getStr(k+1),quotient,residual);return quotient;}int main() { int i, j, p; for(i = 1; i < MAX_N; i++) { num[i] = "0"; for(j = 1; j < MAX_N; j++) cval[i][j] = "0"; } num[1] = "1"; while(scanf("%I64d", &p) && p != -1) cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
