結果

問題 No.2865 Base 10 Subsets 2
コンテスト
ユーザー ID 21712
提出日時 2025-04-01 14:01:04
言語 Go
(1.23.4)
結果
AC  
実行時間 1,207 ms / 2,000 ms
コード長 1,417 bytes
コンパイル時間 12,460 ms
コンパイル使用メモリ 246,932 KB
実行使用メモリ 8,096 KB
最終ジャッジ日時 2025-04-01 14:01:38
合計ジャッジ時間 32,771 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/rand"

func main() {
	var n,k int64
	Scan(&n,&k)
	ans := solve(n, k)
	Println(ans)
}
	
func solve(n, k int64) int64 {
	t := []int64{}
	m := []int64{1}
	for x := n; x > 0; x /= 10 {
		t = append(t, x%10+1)
		m = append(m, m[len(m)-1]*t[len(t)-1])
	}
	var ans int64
	k--
	for i:=len(t)-1; i >= 0; i-- {
		ans *= 10
		for j := int64(1); j <= t[i]; j++ {
			if j*m[i] > k {
				k -= (j-1)*m[i]
				ans += (j-1)
				break
			}
		}
	}
	return ans
}

func init() {
	for n := int64(0); n <= 1000; n++ {
		for k := int64(1); k <= n; k++ {
			ans := bruteforce(n, k)
			if ans < 0 {
				break
			}
			res := solve(n, k)
			if ans != res {
				panic(Sprintf("n=%d,k=%d,ans=%d,res=%d",n,k,ans,res))
			}
		}
	}
	for i := 0; i < 500; i++ {
		n := int64(Intn(1e6))
		x := int64(1)
		for e := n; e > 0; e /= 10 {
			x *= e%10+1
		}
		k := int64(Intn(int(x)))
		if k==0 {
			k++
		}
		ans := bruteforce(n, k)
		if ans < 0 {
			continue
		}
		res := solve(n, k)
		if ans != res {
			panic(Sprintf("n=%d,k=%d,ans=%d,res=%d",n,k,ans,res))
		}
	}
}

func bruteforce(n, k int64) int64 {
	
	valid := func(ex, ts int64) bool {
		if ts > ex {
			return false
		}
		for ts > 0 && ex > 0 {
			if ts%10 > ex%10 {
				return false
			}
			ts /= 10
			ex /= 10
		}
		return ts <= ex
	}
	
	for i := int64(0); i <= n; i++ {
		if valid(n, i) {
			k--
			if k == 0 {
				return i
			}
		}
	}
	
	return -1
}
0