結果

問題 No.2766 Delicious Multiply Spice
コンテスト
ユーザー ID 21712
提出日時 2024-11-07 19:58:35
言語 Go
(1.23.4)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 1,163 bytes
コンパイル時間 14,445 ms
コンパイル使用メモリ 217,904 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-11-07 19:58:54
合計ジャッジ時間 16,734 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 8
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

type F struct {
	s string
	a, b int64
}

type R struct {
	s string
	x int64
}

func (f *F)Append(e *F) *F{
	return &F{
		s: f.s + e.s,
		a: f.a * e.a,
		b: f.b * e.a + e.b,
	}
}

func (f *F) Remove(n *R) (r *R, ok bool) {
	x := n.x - f.b
	if x < 1 || x % f.a != 0{
		return
	}
	x /= f.a
	ok = x % 2 == 1 || x % 3 == 1
	if ok {
		r = &R{
			s:f.s+n.s,
			x:x,
		}
	}
	return
}

func (r *R)IsFirst() bool {
	return r.x==1
}

func (f *F)String() string {
	return Sprintf("%s (%dx+%d)", f.s, f.a, f.b)
}

func main() {
	
	ffs := [][]*F{
		[]*F{
			&F{"A", 2, 1},
			&F{"B", 3, 1},
		},
	}
	
	for i := 0; i < 4; i++ {
		fs := []*F{}
		for _, x := range ffs[i] {
			for _, y := range ffs[i] {
				f := x.Append(y)
				fs = append(fs, f)
			}
		}
		ffs = append(ffs, fs)
	}
	
	var n R
	Scan(&n.x)
	if n.IsFirst() {
		Println()
		return
	}
	
	rs:=[]*R{&n}
	
	p:=len(ffs)-1
	
	rx:=[]*R{}
	for {
		rx=rx[:0]
		for _,r:=range rs {
			for _,f:=range ffs[p] {
				if x,ok:=f.Remove(r);ok {
					if x.IsFirst() {
						Println(x.s)
						return
					}
					rx=append(rx,x)
				}
			}
		}
		if len(rx)==0 {
			p--
		} else {
			rx,rs=rs,rx
		}
	}
}
0