hogemaru　さわやか日記

PKU 1001　solved

study, アルゴリズム | 05:23

PKUというサイトがある。

細かい解説はPKU Wiki*が詳しいですが、簡単に言えば北京大学によってアルゴリズムの問題一式が公開されており、世界中のプログラマが腕試しをしているらしい。

ソースを貼り付ければ自動で採点してくれる点が面白い。ちなみに、言語はC++, Java, Pascal, Fortranしか使えない。

まあちょっとやってみようか、と思って数日前にやりはじめたのですが、1001 -- Exponentiationでいきなり詰んで悔しい思いをしました。

今日リトライして無事Acceptされました。

• Acceptされたコード。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>

#define PROD
#ifndef PROD
#include "test.h"
#endif

using namespace std;
#ifndef _HOGE
#define _HOGE
const int MAX = 200;
typedef struct _hogenum {
	char ans[MAX];
	char dotn;
}hogenum_t;
#endif

void hogenumInit(hogenum_t* hoge)
{
	memset(hoge->ans, -1, MAX);
	hoge->dotn = 0;
}

void setHogenum(hogenum_t* hoge, int val, char dotpos){
	int i = 0;
	while(val != 0){
		int ans = val % 10;
		hoge->ans[i++] = ans;
		val = val / 10;
	}
	hoge->dotn = dotpos;
}

void rightShift(hogenum_t* hoge, int n)
{
	hogenum_t tmp;
	hogenumInit(&tmp);
	for(int i=0; i<MAX-n; i++){
		tmp.ans[i] = hoge->ans[i+n];
	}
	hoge->dotn -= n;
	memcpy(hoge->ans, tmp.ans, MAX);
}
void rightShiftIfZero(hogenum_t* hoge)
{
	int zeroNum = 0;
	for(int i=0; i<MAX; i++){
		if(hoge->ans[i] == 0){
			zeroNum++;
		}else{
			break;
		}
	}

	if(zeroNum != 0 && hoge->dotn > 0){
		if(zeroNum > hoge->dotn){
			rightShift(hoge, hoge->dotn);
		}else{
			rightShift(hoge, zeroNum);
		}
	}
}

void leftShiftIfZero(hogenum_t* hoge)
{
	for(int i=MAX-1; i>-1; i--){
		if(hoge->ans[i] == 0){
			hoge->ans[i] = -1;
		}else{
			if(hoge->ans[i] == -1){
				continue;
			}else{

				break;
			}
		}
	}
}

void dumpHogenum(hogenum_t* hoge){
	
	bool bdot = false;

	rightShiftIfZero(hoge);
	leftShiftIfZero(hoge);

	for(int i=MAX-1; i > -1; i--){
		char val = hoge->ans[i];

		if(i == hoge->dotn-1){
			printf(".");
			bdot = true;
		}

		if(val != -1){
			printf("%d", val);
		}else{
			if(bdot){
				printf("0" );
			}
		}



	}
	printf("\n");
}

void dotHogeN(hogenum_t* hoge, hogenum_t* hogeans, char n)
{
	int j = 0;
	char up = 0;
	for(int i = 0; i < MAX-1; i++){
		if(hoge->ans[i] != -1 || up != 0){
			
			int val = 0;
			int ans = -1;

			if(hoge->ans[i] > 0){
				val = hoge->ans[i]*n + up;
			}else{
				val = up;
			}

			if(val >= 10){
				ans = val % 10;
				up = val / 10;
			}else{
				ans = val;
				up = 0;
			}
			hogeans->ans[j++] = ans; 
		}
	}
	hogeans->dotn = hoge->dotn;
}

// pad 0, value is not change
void leftShift(hogenum_t* hoge, int n)
{
	hogenum_t tmp;
	hogenumInit(&tmp);

	for(int i=0; i < MAX; i++){
		if(n > i){
			tmp.ans[i] = 0;
		}else{
			tmp.ans[i] = hoge->ans[i-n];
		}
	}
	memcpy(hoge->ans, tmp.ans, MAX);
	hoge->dotn = hoge->dotn+n;
}

// pad 0, value is change
void leftShiftDotNoChange(hogenum_t* hoge, int n)
{
	hogenum_t tmp;
	hogenumInit(&tmp);

	for(int i=0; i < MAX; i++){
		if(n > i){
			tmp.ans[i] = 0;
		}else{
			tmp.ans[i] = hoge->ans[i-n];
		}
	}
	memcpy(hoge->ans, tmp.ans, MAX);
}

void adjustDotPos(hogenum_t* hoge,hogenum_t* moge)
{
	if(hoge->dotn != moge->dotn)
	{
		if(hoge->dotn > moge->dotn){
			int diff = hoge->dotn - moge->dotn;
			leftShift(moge, diff);
		}else{
			int diff =moge->dotn - hoge->dotn;
			leftShift(hoge, diff);
		}
	}

}

void plusHoge(hogenum_t* hoge,hogenum_t* moge, hogenum_t* hogeans)
{
	//keta awase
	adjustDotPos(hoge, moge);

	char up = 0;
	for(int i = 0; i < MAX; i++){

		if(up <= 0 && (hoge->ans[i] == -1 && moge->ans[i]==-1 )){
			break;
		}
		if(hoge->ans[i] == -1 ){
			hoge->ans[i] = 0;
		}
		if(moge->ans[i] == -1){
			moge->ans[i] = 0;
		}

		char val = hoge->ans[i] + moge->ans[i] + up;
		up = val / 10;
		val = val - up*10;

		hogeans->ans[i] = val;
	}
	hogeans->dotn = hoge->dotn;
}



void dotHogeHoge(hogenum_t* hoge, hogenum_t* huga, hogenum_t* ans)
{
	hogenum_t tmp;
	hogenum_t tmpsum;
	hogenum_t sum;
	hogenumInit(&tmp);
	hogenumInit(&tmpsum);
	hogenumInit(&sum);

	for(int i =0; i< MAX; i++){
		if(huga->ans[i] <0){
			break;
		}
		dotHogeN(hoge, &tmp, huga->ans[i]);
		leftShiftDotNoChange(&tmp, i);

		plusHoge(&tmp, &sum, &tmpsum);

		memcpy(&sum, &tmpsum, sizeof(hogenum_t));
		hogenumInit(&tmpsum);
		hogenumInit(&tmp);
	}
	ans->dotn = hoge->dotn+huga->dotn;
	memcpy(&ans->ans, &sum.ans, MAX);
}


void exponentialHoge(hogenum_t* hoge, int n, hogenum_t* hogeans)
{
	hogenum_t ans;
	hogenum_t tmp;

	if(n == 1){
		memcpy(hogeans, hoge, sizeof(hogenum_t));
		return;
	}

	dotHogeHoge(hoge, hoge, &ans);
	memcpy(&tmp, &ans, sizeof(hogenum_t));

	for(int i=0; i<n-2; i++){
		dotHogeHoge(&tmp, hoge, &ans);
		memcpy(&tmp, &ans, sizeof(hogenum_t));
	}

	memcpy(hogeans, &ans, sizeof(hogenum_t));
	//dumpHogenum(&ans);
}


void inputValue()
{
	char s[MAX];
	int n = 0;
	hogenum_t hoge;
	hogenum_t ans;
	memset(s, -1, MAX);

	while(cin>>s>>n){
		hogenumInit(&hoge);
		hogenumInit(&ans);
		//char tmp[MAX];
		int j = 0;
		for(int i=MAX-1; i > -1; i--){
			if(s[i]!=-1 ){
				if(s[i] != '.' && s[i] != 0){
					char str = s[i];
					hoge.ans[j++] = atoi(&str);
				}else{
					hoge.dotn = j;
				}
			}
		}
		exponentialHoge(&hoge, n, &ans);
		dumpHogenum(&ans);
		memset(s, -1, MAX);
	}
}

int main()
{

	
	//test
#ifndef PROD
	monoTest();
#else
	inputValue();
#endif

	return 0;
}

メモリ、速度ともにまだ削れる余地はあるのですが力尽きました。

Javaならライブラリ使って数行で解けるみたいなのでショック。

• Top Short Coder達へ - Cozy Ozy

ツイートする