SRM 707 Div.1

Kriii형이 또 다시 스름 윈을 했다ㅋㅋ
나는 오랜만에 해보았는데 0점 받지 않아서 다행이라 생각한다.
몇 가지 고려 안해서 미디움을 놓친 건 정말 아쉽다.

250pts(Passed System Test)
ㄹ자로 만드는 전략을 통해 맵을 만들어나가면 된다.
단, ㄹ자로 만드는 과정에서 경로가 2씩 증가됨에 주의한다.

class MazeConstruct {
public:
	vector <string> solve(vector <string> ans, int k) {
		int s = ans.size();
		for (int i = 1; i < ans[0].size(); i += 2) {
			if (i % 4 == 1) {
				for (int j = 0; j < s - 1; j++) {
					ans[j][i] = '#';
				}
			}
			else {
				for (int j = s - 1; j >= 1; j--) {
					ans[j][i] = '#';
					k -= 2;
					if (k < 0) return {};
					if (k == 0) return ans;
				}
			}
		}
		return {};
	}
	vector <string> construct(int k) {
		vector <string> ans;
		ans.push_back("");
		k++;
		for (int i = 0; k && i < 50; i++) ans[0] += ".", k--;
		if (k == 0) return ans;
		for (int i = 1; k && i < 50; i++) {
			ans.push_back(ans[0]);
			k--;
		}
		if (k == 0) return ans;
		vector <string> res = solve(ans, k);
		if (res.size() == 0) {
			ans.pop_back();
			k++;
			res = solve(ans, k);
		}
		return res;
	}
};

450pts(Challenge Succeeded, Upsolved)

s=0, a=0, b=0, b=1 4가지 경우에 주의해서 진법 계산하듯 풀 수 있다.

class MultiplyAddPuzzle {
	public:
	long long minimalSteps(long long s, long long t, long long a, long long b) {
		if (s == t) return 0;
		long long ans = 0;
		if (b == 0) {
			if (t == 0) return 1;
			if (a == 0) return -1;
			ans = -1;
			if (t % a == 0) ans = t / a + 1;
			if (t > s && (t - s) % a == 0) ans = (t - s) / a;
			return ans;
		}
		if (b == 1) {
			if (a == 0) return -1;
			if (t > s && (t - s) % a == 0) return (t - s) / a;
			return -1;
		}
		if (a == 0) {
			int cnt = 0;
			while (cnt <= 60) {
				if (s == t) return cnt;
				double lg = log10(s) + log10(b);
				if (lg > log10(t) + (1e-9)) break;
				s *= b;
				cnt++;
			}
			return -1;
		}
		long long pw[61] = { 0, }; int pn;
		pw[0] = 1; pn = 0;
		for (int i = 1; i <= 60; i++) {
			if (log10(pw[i - 1]) + log10(b) > log10(t) + (1e-9)) break;
			pw[i] = pw[i - 1] * b;
			pn = i;
		}
		int k = 0;
		ans = -1;
		long long i = s;
		while (k <= pn) {
			if (t < i) break;
			if ((t - i) % a == 0) {
				long long cnt = k;
				long long r = (t - i) / a;
				for (int i = k; i >= 0; i--) {
					cnt += r / pw[i];
					r %= pw[i];
				}
				if (ans < 0 || ans > cnt) ans = cnt;
			}
			if (i != 0) {
				double lg = log10(i) + log10(b);
				if (lg > log10(t) + (1e-9)) break;
				i *= b;
			}
			k++;
		}
		return ans;
	}
};

1000pts(Unopened)
안 읽어봤다.