← 返回题目列表

AtCoder · joiopen2024_a

A. 考试2

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

試験 2 (Examination 2) - 原题 PDF 第 1 页
原题PDF第1页
試験 2 (Examination 2) - 原题 PDF 第 2 页
原题PDF第2页
試験 2 (Examination 2) - 原题 PDF 第 3 页
原题PDF第3页
試験 2 (Examination 2) - 原题 PDF 第 4 页
原始 PDF 第 4 部分
可复制的 PDF 提取文本
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                        examination2

            試験2 (Examination 2)



  JOI 君の通うIOI 高校では,近いうちに定期試験が行われる予定である.試験では,IOI 高校が独自に

ルールを定めたIOI 関数の値を正しく計算できるかどうかが問われる.IOI 関数とは以下の6 種類のいずれ
かのルールにより得られる文字列のことであり,1 以上109 以下の整数にTrue またはFalse の真偽値を対

応させる.

    1. a を1 以上109 以下の整数として,[a] はIOI 関数である(ただし,a はa を十進表記して得られる

   文字列とする).このIOI 関数はa 以上の整数にTrue を,a 未満の整数にFalse を対応させる.

    2. f をIOI 関数として,(f) はIOI 関数である.このIOI 関数はf がTrue に対応させる整数にTrue

    を,f がFalse に対応させる整数にFalse を対応させる.

    3. f をIOI 関数として,!f はIOI 関数である.このIOI 関数はf がTrue に対応させる整数にFalse

    を,f がFalse に対応させる整数にTrue を対応させる.

    4. f, g をIOI 関数として,f&g はIOI 関数である.このIOI 関数はf, g の両方がTrue に対応させる整

    数にTrue を,そうでない整数にFalse を対応させる.

    5. f, g をIOI 関数として,fˆg はIOI 関数である.このIOI 関数はf, g のちょうど一方がTrue に対応

    させる整数にTrue を,そうでない整数にFalse を対応させる.

    6. f, g をIOI 関数として,f|g はIOI 関数である.このIOI 関数はf, g の少なくとも一方がTrue に対

   応させる整数にTrue を,そうでない整数にFalse を対応させる.

 あるIOI 関数が複数のルールから得られる場合,より番号の大きいルールによりIOI 関数が対応させる真

偽値を定めるものとする.例えば[1]&[2]|[3] の場合にはf = [1]&[2], g = [3] に対してルール6 が適

用される(f = [1], g = [2]|[3] に対してルール4 が適用されるのではない).さらに,ルール4, 5, 6 につ

いては,よりf が長くなるようにルールが適用される.例えば[4]ˆ[5]ˆ[6] の場合にはf = [4]ˆ[5], g =

[6] に対してルール5 が適用される(f = [4], g = [5]ˆ[6] に対してルール5 が適用されるのではない).
  JOI 君は試験勉強として,長さがN であるIOI 関数S を用意し,Q 個の整数X1, X2, . . . , XQ についてこ
の関数が対応させる真偽値を求める練習をしようと考えている.そこで,IOI 関数の扱いに長けているあな

たに模範解答を作るよう頼んできた.

  N, Q, S およびX1, X2, . . . , XQ が与えられるので,X1, X2, . . . , XQ について,JOI 君の用意したIOI 関数が

対応させる真偽値を求めるプログラムを作成せよ.





                         試験2– 1 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                        examination2



入力


 入力は以下の形式で標準入力から与えられる.


    N Q

      S

      X1
      X2
                                    ...

     XQ


出力

 標準出力にQ 行出力せよ.i 行目(1 ≦i ≦Q) には,JOI 君の用意したIOI 関数が整数Xi に対応させる真

偽値を出力せよ.


制約

    • 1 ≦N ≦1 000 000.

    • 1 ≦Q ≦200 000.

    • S は長さN のIOI 関数である.
    • 1 ≦Xi ≦109 (1 ≦i ≦Q).
    • N, Q およびXi (1 ≦i ≦Q) はすべて整数である.


小課題

    1. (5 点) S は&, | を含まない.

    2. (20 点) Q = 1.

    3. (10 点) N ≦10 000.

    4. (6 点) S は!, ˆ を含まない.

    5. (12 点) S が得られる過程でルール4 またはルール6 が適用されたとき,f, g のうち少なくとも一方

   はルール1 によって得られるIOI 関数であった.

    6. (20 点) N ≦400 000.

    7. (27 点) 追加の制約はない.



                         試験2– 2 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                        examination2



入出力例

  入力例1              出力例1

   15 5                           True

   (![2]|[3])&![4]                False

   1                              True

   2                              False

   3                              False

   4

   5

 問題文中のルールによりS が得られる過程で現れるIOI 関数のうち一部について,それが各Xi (1 ≦i ≦Q)

に対応させる真偽値を求めると,次の表のようになる.


    Xi  ![2]   [3]    ![2]|[3]  ![4]   (![2]|[3])&![4]

   1   True   False  True      True   True

   2   False  False  False     True   False

   3   False  True   True      True   True

   4   False  True   True      False  False

   5   False  True   True      False  False

 この入力例は小課題3, 6, 7 の制約を満たす.


  入力例2              出力例2

   20 4                           True

   (!![23])ˆ((([116])))           False

   54                             False

   1                              True

   200

   89

 この入力例は小課題1, 3, 5, 6, 7 の制約を満たす.





                         試験2– 3 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                JOI Open Contest

                                                                          June 16, 2024


                                                                       examination2


 入力例3                    出力例3

 32 4                                    True

 [2]|[5]&[1]|(([1000000000])|[7])        True

 4                                       True

 10                                      False

 6

 1

この入力例は小課題3, 4, 6, 7 の制約を満たす.





                        試験2– 4 / 4