結果

問題 No.757 チャンパーノウン定数 (2)
コンテスト
ユーザー iicafiaxus
提出日時 2018-12-05 23:39:58
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 5,365 bytes
コンパイル時間 975 ms
コンパイル使用メモリ 126,080 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-13 02:01:12
合計ジャッジ時間 5,863 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 34 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

void main(){
	
	int b = read.to!int;
	string d = readln.chomp;
	debug writeln("b: ", b);
	debug writeln("d: ", d);
	
	// 第k群(k桁の数たちの中にいる)
	int k = 1 + uplimit(1, 100, (int x) => wk(b, x).lt(d));
	debug writeln("k: ", k);
	
	// 第k群の第j文字目
	string j = d.sub(wk(b, k - 1), b);
	debug writeln("j: ", j);
	
	// 第k群の何個目の数を構成している文字か
	string m = j.add((k - 1).to!string, b).div(k, b);
	debug writeln("m: ", m);
	
	// それは何という数か
	string x = ("1" ~ ("0".repeat(k - 1))).sub("1", b).add(m, b);
	debug writeln("x: ", x);
	
	// その何桁目か
	int y = j.mod(k, b);
	if(y == 0) y += k;
	debug writeln("y: ", y);
	
	// ずばり答えは
	x[y - 1].writeln;
	
	
	/*
	debug foreach(x; [
		["5", "8"],
		["8", "5"],
		["5", "5"],
		["50", "8"],
		["80", "8"],
		["80", "5"],
		["5", "80"],
		["5", "50"],
		["8", "50"],
		["54", "54"],
		["52", "53"],
		["85", "82"],
		]) writeln(x[0], " <= ", x[1], " : ", le(x[0], x[1]));
	*/

	/*
	debug foreach(x; [
		["423", "144", "9"],
		["836", "542", "9"],
		["836", "543", "9"],
		["4", "108", "10"],
		["189", "9", "10"]
		]) writeln(x[0], " + ", x[1], " (", x[2], ")= ", x[0].add(x[1], x[2].to!int));
	debug foreach(x; [
		["846", "512", "9"],
		["836", "542", "9"],
		["106", "42", "9"],
		["106", "2", "9"],
		["106", "8", "9"],
		["140", "140", "6"]
		]) writeln(x[0], " - ", x[1], " (", x[2], ")= ", x[0].sub(x[1], x[2].to!int));
	*/

	/*
	debug foreach(x; [
		[10, 1],
		[10, 2],
		[10, 3],
		[10, 4],
		[10, 5],
		[10, 6],
		[5, 1],
		[5, 2],
		[5, 3],
		[5, 4],
		[5, 5],
		[5, 6],
		]) writeln(x[0], ", ", x[1], " => ", wk(x[0], x[1]));
	*/
	/*
	debug foreach(x; [
		[0, 10, 6],
		[0, 10, 0],
		[0, 10, 10],
		[0, 10, 100],
		]) writeln(x[0], ", ", x[1], ", ( x < ", x[2], " ) => ", uplimit(x[0], x[1], (int k) => k < x[2]));
	*/
	/*
	debug foreach(x; [
		[100, 5, 10],
		[100, 5, 9],
		[83, 5, 10],
		[83, 5, 9],
		[3, 8, 9],
		[1000, 3, 9],
		[305, 5, 10],
		[900, 9, 10]
		]) writeln(x[0], " / ", x[1], " (" , x[2], ")= ", x[0].to!string.div(x[1], x[2]), " ... ", x[0].to!string.mod(x[1], x[2]));
	*/
}

// 整数としての比較
bool lt(string a, string b){
	if(a.length < b.length) return 1;
	if(a.length > b.length) return 0;
	if(a < b) return 1;
	if(a > b) return 0;
	return 0;
}
bool le(string a, string b){
	if(a.length < b.length) return 1;
	if(a.length > b.length) return 0;
	if(a < b) return 1;
	if(a > b) return 0;
	return 1;
}

// 整数としての足し算
string add(string u, string v, int b){
	string ux, vx, ansx;
	foreach_reverse(c; u) ux ~= c;
	foreach_reverse(c; v) vx ~= c;
	while(ux.length < vx.length) ux ~= '0';
	while(vx.length < ux.length) vx ~= '0';
	int f = 0;
	for(int i = 0; i < ux.length; i ++){
		int iu = ("" ~ ux[i]).to!int, iv = ("" ~ vx[i]).to!int;
		if(iu + iv + f < b) ansx ~= (iu + iv + f).to!string, f = 0;
		else ansx ~= (iu + iv + f - b).to!string, f = 1;
	}
	if(f) ansx ~= "1";
	string ans;
	foreach_reverse(c; ansx){
		if(ans.length == 0 && c == '0') continue;
		ans ~= c;
	}
	if(ans == "") ans = "0";
	return ans;
}

// 整数としての引き算
string sub(string u, string v, int b){
	string ux, vx, ansx;
	foreach_reverse(c; u) ux ~= c;
	foreach_reverse(c; v) vx ~= c;
	while(ux.length < vx.length) ux ~= '0';
	while(vx.length < ux.length) vx ~= '0';
	int f = 0;
	for(int i = 0; i < ux.length; i ++){
		int iu = ("" ~ ux[i]).to!int, iv = ("" ~ vx[i]).to!int;
		if(iu >= iv + f) ansx ~= (iu - iv - f).to!string, f = 0;
		else ansx ~= (iu + b - iv - f).to!string, f = 1;
	}
	string ans;
	foreach_reverse(c; ansx){
		if(ans.length == 0 && c == '0') continue;
		ans ~= c;
	}
	if(ans == "") ans = "0";
	return ans;
}

// 割り算
string div(string u, int k, int b){
	int tmp;
	string ans;
	foreach(c; u){
		tmp *= b;
		tmp += ("" ~ c).to!int;
		if(tmp >= k) ans ~= (tmp / k).to!string, tmp %= k;
		else if(ans.length > 0) ans ~= '0';
	}
	if(ans == "") ans = "0";
	return ans;
}
int mod(string u, int k, int b){
	int tmp;
	string ans;
	foreach(c; u){
		tmp *= b;
		tmp += ("" ~ c).to!int;
		if(tmp >= k) ans ~= (tmp / k).to!string, tmp %= k;
		else ans ~= '0';
	}
	return tmp;
}


// 第k群の終わりまでで何文字あるかを表すb進数の文字列
string wk(int b, int k){
	if(k == 0) return "0";
	string res;
	if(k > 1) res ~= repres(k - 1, b);
	foreach(i; 0 .. k - 1) res ~= (b - 2).to!string;
	res ~= (b - 1).to!string;
	return res;
}

// b進法でのx
string repres(int x, int b){
	string tmp;
	while(x > 0){
		tmp ~= (x % b).to!string;
		x /= b;
	}
	string res;
	foreach_reverse(c; tmp) res ~= c;
	if(res == "") res = "0";
	return res;
}


// b進法でのxの桁数
int length(int b, int x){
	long tmp = 1;
	int res = 0;
	while(tmp < x) tmp *= b, res += 1;
	return res;
}

// fをみたす最大
int uplimit(int a, int c, bool delegate(int) f){
	if(f(c)) return c;
	if(! f(a)) return a - 1;
	while(a + 1 < c){
		int b = (a + c) / 2;
		if(f(b)) a = b;
		else c = b;
	}
	return a;
}

// 繰り返し
string repeat(string s, int t){
	string res;
	foreach(i; 0 .. t) res ~= s;
	return res;
}
0