結果

問題 No.1187 皇帝ペンギン
コンテスト
ユーザー ID 21712
提出日時 2026-06-05 02:34:40
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 86 ms / 1,000 ms
コード長 1,929 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,586 ms
コンパイル使用メモリ 282,928 KB
実行使用メモリ 30,308 KB
平均クエリ数 16.59
最終ジャッジ日時 2026-06-05 02:35:04
合計ジャッジ時間 19,749 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "sort"

func main() {
	solve(Judge{})
}

type Interactive interface {
	Q(x int) bool
	A(x int)
}

type Judge struct{}

func (Judge)Q(x int) bool {
	Println("?", x)
	var s string
	Scan(&s)
	return s == "safe"
}

func (Judge)A(x int) {
	Println("!", x)
}

func solve(io Interactive) {
	n := Search(1e3+2, func(x int) bool {
		if io.Q(x) {
			return false
		}
		return !io.Q(x+1)
	})
	io.A(max(0, min(1e3-1, n-1)))
}

type Testcase struct { n,d,c int }

func (t *Testcase) Q(x int) bool {
	t.c++
	if t.c > 25 {
		println("n=",t.n)
		println("d=",t.d)
		println("x=",x)
		panic("queries over 25")
	}
	return x < t.n && (x < t.d || x % t.d != 0)
}

func (t *Testcase) A(x int) {
	ans := t.n-1
	if ans >= t.d && ans % t.d == 0 {
		ans--
	}
	if ans != x  {
		println("n=",t.n)
		println("d=",t.d)
		println("ans=",ans)
		println("x=",x)
		println("c=",t.c)
		panic("Wrong")
	}
}

func init() {
	check()
}

func check() {
	for n := 1; n <= 1e3; n++ {
		for d := 2; d <= 1e3+1; d++ {
			solve(&Testcase{ n, d, 0 })
		}
	}
}

/*
考察

クエリXの最大が10^9なのは何故
N回以上だと怒りだす、Nは最大でも10^3
つまりX>10^3の質問クエリに意味がない…

最終的にDの倍数回叩くと怒り出すというやつ
よくわからなかったが
どうも叩いている途中にD回に到達しようとも怒るわけじゃなく
叩くのをやめたときの回数がDの倍数だと怒るという意味らしい

つまり
求める答えは
N-1がDの倍数でないならN-1
N-1がDの倍数であるならN-2
ということらしい

普通に二分探索すると
XがDの倍数だった場合
探索範囲を絞ることができない
仮にXがDの倍数だった場合、X+1かX-1するとDの倍数ではなくなる
昇順に対する二分探索が"以上"の位置を求めるものだからX+1で再確認すればいいのかもしれない



*/
0