← 返回题目列表

AtCoder · joisc2019_h

H. 灯

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

ランプ (Lamps) - 原题 PDF 第 1 页
原题PDF第1页
ランプ (Lamps) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                         Contest Day 3 – Lamps

                  ランプ(Lamps)



 長い廊下にN 個のランプが一列に並んでいる.ランプには左から順に1 からN までの番号が付いてい

る.各ランプの状態はoffまたはon のいずれかである.

 ランプの状態を変える特殊な機構が用意されており,1 回の操作で以下の3 つのいずれかができる:

    • 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q をすべてoffにする.

    • 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q をすべてon にする.

    • 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q の状態をすべて変更する(offならon に,

      on ならoffにする).

 現在のランプの状態は長さN の文字列A で表される.A のi 文字目(1 ≦i ≦N) は,ランプi がoffであ

るならば0 であり,on であるならば1 である.これから,できるだけ少ない回数の操作を行い,長さN の

文字列B で表される目標の状態にしたい.B のi 文字目(1 ≦i ≦N) は,ランプi をoffにしたいならば0 で

あり,on にしたいならば1 である.

 ランプの個数,現在の状態と目標の状態が与えられたとき,必要な操作回数の最小値を求めるプログラム

を作成せよ.


入力


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


    N

     A

     B


出力

 標準出力に,必要な操作回数の最小値を1 行で出力せよ.


制約

    • 1 ≦N ≦1 000 000.

    • A, B は長さN の文字列である.

    • A, B の各文字は0, 1 のいずれかである.




                        ランプ– 1 / 2

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                         Contest Day 3 – Lamps



小課題

    1. (6 点) N ≦18.

    2. (41 点) N ≦2 000.

    3. (4 点) A の各文字は0 である.

    4. (49 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   8                              4

   11011100

   01101001

 この入力例では,例えば以下のような4 回の操作によって目標の状態を作ることができる:

    1. ランプ1, 2, 3, 4 の状態を変更する.ランプの状態は00101100 になる.

    2. ランプ2 をon にする.ランプの状態は01101100 になる.

    3. ランプ6, 7, 8 の状態を変更する.ランプの状態は01101011 になる.

    4. ランプ6, 7 をoffにする.ランプの状態は01101001 になる.

  3 回以下の操作では目標の状態を作ることはできないので,4 を出力する.


  入力例2              出力例2

   13                             3

   1010010010100

   0000111001011


  入力例3              出力例3

   18                             5

   001100010010000110

   110110001000100101





                        ランプ– 2 / 2