結果
問題 | No.319 happy b1rthday 2 me |
ユーザー |
![]() |
提出日時 | 2023-04-19 00:40:05 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,211 bytes |
コンパイル時間 | 14,087 ms |
コンパイル使用メモリ | 221,464 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 00:27:58 |
合計ジャッジ時間 | 15,077 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
package mainimport ("bufio""fmt""io""os""strconv")var iost *Iosttype Iost struct {Scanner *bufio.ScannerWriter *bufio.Writer}func NewIost(fp io.Reader, wfp io.Writer) *Iost {const BufSize = 2000005scanner := bufio.NewScanner(fp)scanner.Split(bufio.ScanWords)scanner.Buffer(make([]byte, BufSize), BufSize)return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}}func (i *Iost) Text() string {if !i.Scanner.Scan() {panic("scan failed")}return i.Scanner.Text()}func (i *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x }func (i *Iost) GetNextInt() int { return i.Atoi(i.Text()) }func (i *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x }func (i *Iost) GetNextInt64() int64 { return i.Atoi64(i.Text()) }func (i *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x }func (i *Iost) GetNextFloat64() float64 { return i.Atof64(i.Text()) }func (i *Iost) Print(x ...interface{}) { fmt.Fprint(i.Writer, x...) }func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) }func (i *Iost) Println(x ...interface{}) { fmt.Fprintln(i.Writer, x...) }func isLocal() bool { return os.Getenv("NICKEL") == "BACK" }func main() {fp := os.Stdinwfp := os.Stdoutif isLocal() {fp, _ = os.Open(os.Getenv("WELL_EVERYBODY_LIES_TOO_MUCH"))}iost = NewIost(fp, wfp)defer func() {iost.Writer.Flush()}()solve()}func solve() {l := iost.GetNextInt()r := iost.GetNextInt()ans := f(r) - f(l-1) + g(r-1) - g(l-1)if l == 1 && l < r {ans++}iost.Println(ans)}func f(r int) int {rr := make([]int, 0)for r > 0 {rr = append(rr, r%10)r /= 10}a := 0n := len(rr)b := n - 1for a < b {rr[a], rr[b] = rr[b], rr[a]a++b--}dp := make([][2][2]int, n+1)cnt := make([][2][2]int, n+1)cnt[n][0][0] = 1ans := 0for i := n - 1; i >= 0; i-- {for j := 0; j < 2; j++ {for k := 0; k < 2; k++ {for d := 0; d < 10; d++ {tj := 0if rr[i]-j < d {tj = 1}tk := 0if d == 2 {tk = 1}add := 0if d == 1 && k == 1 {add = cnt[i+1][j][k]}dp[i][tj][tk] += dp[i+1][j][k] + addcnt[i][tj][tk] += cnt[i+1][j][k]if d == 0 {continue}if i > 0 || tj == 0 {ans += dp[i+1][j][k] + add}}}}}return ans}func g(r int) int {if r == 0 {return 0}rr := make([]int, 0)for r > 0 {rr = append(rr, r%10)r /= 10}a := 0n := len(rr)b := n - 1for a < b {rr[a], rr[b] = rr[b], rr[a]a++b--}dp := make([][2]int, n+1)enable := make([][2]int, n)enable[n-1][0] = 1enable[n-1][1] = 1for i := 0; i < n-1; i++ {enable[i][1] = 9}dp[n][0] = 1ans := 0for i := n - 1; i >= 0; i-- {for j := 0; j < 2; j++ {for d := enable[i][0]; d <= enable[i][1]; d++ {tj := 0if rr[i]-j < d {tj = 1}dp[i][tj] += dp[i+1][j]if d != 2 {continue}if i > 0 || tj == 0 {ans += dp[i+1][j]}}}}return ans}