結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー ID 21712
提出日時 2026-04-18 02:26:50
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 2,289 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,112 ms
コンパイル使用メモリ 276,068 KB
実行使用メモリ 30,308 KB
平均クエリ数 10.47
最終ジャッジ日時 2026-04-18 02:27:08
合計ジャッジ時間 17,842 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var n int
	Scan(&n)
	s := newS(n)
	x := ""
	for i := 0; i <= n; i++ {
		var a,b int
		a, b, x = s.req()
		if x != "" || i == n {
			break
		}
		Println("?", min(a, b), max(a, b))
		var p int
		Scan(&p)
		s.res(p)
	}
	Println("!",x)
}

type S struct {
	n int
	pos int
	ms []int
	ps []int
}

func newS(n int) *S {
	s := &S{
		n: n,
		pos: n-2,
		ps: make([]int, n),
		ms: make([]int, 10),
	}
	return s
}

func (s *S)req() (a, b int, x string) {
	if s.pos < 0 {
		mx := 0
		for i := 1; i <= 9; i++ {
			mx = max(mx, s.ms[i])
		}
		h := 0
		cnt := 0
		for i := 1; i <= 9; i++ {
			if mx == s.ms[i] {
				h = i
				cnt++
			}
		}
		if cnt != 1 {
			if s.pos == -1 {
				for i, u := range s.ps[:s.n-1] {
					if u == 0 {
						continue
					}
					for j, v := range  s.ps[i+1:s.n-1] {
						if v == 0 {
							continue
						}
						a, b = i, j+i+1
						return
					}
				}
			}
			x = "-1"
			return
		}
		bs := make([]byte, s.n)
		bs[0] = byte(h+'0')
		for k, p := range s.ps[:s.n-1] {
			for i := 0; i <= 9; i++ {
				if i*h == p {
					bs[s.n-1-k] = byte(i + '0')
					break
				}
			}
		}
		x = string(bs)
		return
	}
	b = s.n-1
	a = s.pos
	return
}

func (s *S)res(p int) {
	if s.pos == -1 {
		s.pos--
		for i, u := range s.ps[:s.n-1] {
			if u == 0 {
				continue
			}
			for _, v := range  s.ps[i+1:s.n-1] {
				if v == 0 {
					continue
				}
				// u = e * f
				// v = e * g
				// p = f * g
				for e := 1; e <= 9; e++ {
					if u*v == e*e*p	 {
						s.ms[e] += 9999
						return
					}
				}
				return
			}
		}
		return
	}
	s.ps[s.pos] = p
	for i := 1; i <= 9; i++ {
		for j := 0; j <= 9; j++ {
			if i*j == p {
				s.ms[i]++
			}
		}
	}
	s.pos--
}

func init() {
	check()
}

func check() {
	for x := 1202; x < 10000; x++ {
		n := 4
		xs := []byte(Sprint(x))
		s := newS(n)
		ok := false
		for i := 0; i <= n; i++ {
			a,b,rx := s.req()
			if rx != "" || i == n {
				var rxx int
				Sscan(rx, &rxx)
				if x != rxx {
					println("n=",n)
					println("x=",x)
					println("rx=",rx)
					println("OMG!")
					return
				}
				ok = true
				break
			}
			u := int(xs[n-1-a])-'0'
			v := int(xs[n-1-b])-'0'
			p := u*v
			s.res(p)
		}
		if !ok {
			println("n=",n)
			println("x=",x)
			println("OOPS!")
			return
		}
	}
	println("ok")
}
0