TopCoder SRM 403 DIV 2

Problem	Check	Points
250	○	239.31
500	×	-
1000	-	-

最近練習で500を落とすなあ。無理やりやろうとしてわけがわからなくなるパターンが多いので、まずは1000までとかよくばらずに500を確実にできるように。
今日の練習会のMVPは@Matsu4512。全部通しやがった・・・

Problem 250 TheLargestLuckyNumber

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.
You are given an int n. Return the largest lucky number that is less than or equal to n.

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

class TheLargestLuckyNumber {
public:
  int find(int n) {

	  deque<int> a;
	  bool b;
	  for(int i=n ; i>=4 ; i--){
		  a = integerDigits(i);
		  b = true;
		  for(int j=0 ; j<a.size() ; j++){
			  if(a[j]!=4 && a[j]!=7){
				  b = false;
				  break;
			  }
		  }
		  if(b) return i;
	  }
	  return 4;
  }
};

Problem 500 TheLuckyNumbers

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.
You are given ints a and b. Return the number of lucky numbers between a and b, inclusive.

実装が糞になってしまった。countLuckyがあればfindMinLuckyとfindMaxLuckyなんていらないと気づいたのがついさっき。直す気力がありません

int findMinLucky(int a, int b){
	if(a>777777777) return -1;
	if(77777777<a && a<444444444 && 444444444<b) return 444444444;

	int k;
	bool f;
	for(int i=a ; i<=b ; i++){
		k = i;
		f = true;

		while(k!=0){
			if(k%10!=4 && k%10!=7){
				f = false;
				break;
			}
			k /= 10;
		}
		if(f) return i;
	}

	return -1;
}

int findMaxLucky(int a){
	if(a>777777777) return 777777777;
	if(a>77777777 && a<444444444)  return 77777777;

	int k;
	bool b;
	for(int i=a ; i>=4 ; i--){
		k = i;
		b = true;

		while(k!=0){
			if(k%10!=4 && k%10!=7){
				b = false;
				break;
			}
			k /= 10;
		}
		if(b) return i;
	}
	return -1;
}

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

int countLucky(deque<int> d1, deque<int> d2){
	int cnt = 1;
	while(d1!=d2){
		cnt++;
		bool f = true;	
		for(int i=d1.size()-1 ; i>=0 ; i--){
			if(d1[i]==4){
				d1[i]=7;
				f = false;
				break;
			}
			else d1[i] = 4;
		}
		if(f) d1.push_front(4);
	}
	return cnt;
}


class TheLuckyNumbers {
public:
  int count(int a, int b) {


	  int kmin = findMinLucky(a,b);
	  int kmax = findMaxLucky(b);

	  cout << kmin << " " <<kmax << endl;

	  if(kmin==-1) return 0;

	  deque<int> d1 = integerDigits(kmin);
	  deque<int> d2 = integerDigits(kmax);
	  return countLucky(d1,d2);
 }
};

Problem 1000

John thinks 4 and 7 are lucky digits, and all other digits are not lucky. A lucky number is a number that contains only lucky digits in decimal notation.

Some numbers can be represented as a sum of only lucky numbers. Given an int n, return a int whose elements sum to exactly n. Each element of the int must be a lucky number. If there are multiple solutions, only consider those that contain the minimum possible number of elements, and return the one among those that comes earliest lexicographically. A int a1 comes before a int a2 lexicographically if a1 contains a smaller number at the first position where they differ. If n cannot be represented as a sum of lucky numbers, return an empty int[] instead.

500の実装が腐っていたので1000までひきずるはめに。DP部分は@Matsu4512の作品、勉強になります。

vector<int> v;

int findMinLucky(int a, int b){
	int k;
	bool f;
	for(int i=a ; i<=b ; i++){
		k = i;
		f = true;

		while(k!=0){
			if(k%10!=4 && k%10!=7){
				f = false;
				break;
			}
			k /= 10;
		}
		if(f) return i;
	}

	return -1;
}

int findMaxLucky(int a){
	int k;
	bool b;
	for(int i=a ; i>=4 ; i--){
		k = i;
		b = true;

		while(k!=0){
			if(k%10!=4 && k%10!=7){
				b = false;
				break;
			}
			k /= 10;
		}
		if(b) return i;
	}
	return -1;
}

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}

void calcLucky(deque<int> d1, deque<int> d2){
	while(d1!=d2){
		v.push_back(fromDigits(d1));
		
		bool f = true;	
		for(int i=d1.size()-1 ; i>=0 ; i--){
			if(d1[i]==4){
				d1[i]=7;
				f = false;
				break;
			}
			else d1[i] = 4;
		}
		if(f) d1.push_front(4);
	}
	v.push_back(fromDigits(d1));

	return;
}

int sumdeq(deque<int> a){
	int sum=0;
	for(int i=0 ; i<a.size() ; i++){
		sum += a[i];
	}
	return sum;
}

int nn;

int dp[1000001];
vector<int> nums[1000001];

void dpcalc(){
	dp[0] = 0;
	dp[1] = dp[2] = dp[3] = 1000000;

	int mina, a;
	vector<int> min_vec;

	for(int i=4; i<=nn ; i++){
		mina = 1000000;
		min_vec.clear();

		for(int j=0 ; j<v.size() ; j++){
			if(i-v[j]<0) break;
			if(mina > dp[i-v[j]]){
				a = v[j];
				mina = dp[i-a];
				min_vec = nums[i-a];
			}
		}

		dp[i] = mina+1;

		if(mina != 1000000) min_vec.push_back(a);
		nums[i] = min_vec;
	}
}

class TheSumOfLuckyNumbers {
public:
  vector <int> sum(int n) {
	  v.clear();
	  nn = n;

	  int kmin = 4;
	  int kmax = findMaxLucky(n);

	  if(kmax==-1) return vector<int>();

	  deque<int> d1 = integerDigits(kmin);
	  deque<int> d2 = integerDigits(kmax);

	  calcLucky(d1,d2);
	  	  
	  dpcalc();

	  if(nums[n].size()>0)
		  sort(nums[n].begin(), nums[n].end());

	  return nums[n];
  }
};