Loogisessa piirissä on n lähtöbittiä, ja piiri tuottaa m tulosbittiä. Piiri koostuu AND- ja OR-porteista, jotka ottavat sisään kaksi bittiä ja tuottavat tuloksena yhden bitin. Jokainen piirin tulosbitti on joko piirin lähtöbitti tai jonkin portin tulosbitti. Piirin rakenteessa ei ole silmukoita.

AND-portti antaa bitin 1, jos kumpikin porttiin sisään menevä bitti on 1, ja muuten bitin 0. OR-portti antaa bitin 1, jos toinen tai kumpikin porttiin sisään menevä bitti on 1, ja muuten bitin 0. Jokainen porttiin sisään menevä bitti on joko lähtöbitti tai toisen portin tulosbitti.

Seuraavassa on esimerkkinä piiri, jossa n=m=5. Kun piirille annetaan lähtöbitit 01101, se tuottaa tulosbitit 00101.

Tässä tehtävässä sinulle ei kerrota piirin rakennetta, mutta voit testata piirin toimintaa erilaisilla lähtöbittien yhdistelmillä. Onko olemassa kaksi eri bittiyhdistelmää, joilla piiri tuottaa saman tuloksen?

Kommunikaatio

Tämä on interaktiivinen tehtävä.

Lue ensin yhdeltä riviltä kaksi kokonaislukua n, m: piirin lähtö- ja tulosbittien määrä.

Tämän jälkeen ohjelmasi voi tehdä kyselyjä. Tulosta yhdelle riville merkki ? sekä n lähtöbittiä. Saat vastauksena yhden rivin, jolla on m tulosbittiä.

Kun ohjelmasi on saanut vastauksen selville, tulosta ensin YES, jos kaksi eri lähtobittien yhdistelmää tuottavat saman tuloksen, ja muuten NO. Jos vastaus on YES, tulosta vielä erillisille riveille esimerkki kahdesta lähtöbittien yhdistelmästä, jotka tuottavat saman tuloksen.

Jos mahdollisia vastauksia on useita, voit tulostaa minkä tahansa niistä. Jos ohjelmasi tekee yli 3000 kyselyä ennen vastauksen tulostamista, testin tulokseksi tulee WRONG ANSWER.

Esimerkki 1

5 5
? 00000
00000
? 01001
00101
? 01101
00101
YES
01001
01101

Selitys: Tämä esimerkki vastaa kuvassa olevaa piiriä. Se antaa saman tuloksen lähtöbiteillä 01001 ja 01101.

Esimerkki 2

2 2
? 01
10
? 10
01
? 11
11
NO

Selitys: Tässä voidaan päätellä, että piiri antaa kaikilla lähtöbittien yhdistelmillä erilaisen tulosbittien yhdistelmän.

Osatehtävä 1 (14 pistettä)

• n = m
• 2 \le n, m \le 10

Osatehtävä 2 (12 pistettä)

• n = m
• 2 \le n, m \le 30

Osatehtävä 3 (26 pistettä)

• n = m + 1
• 2 \le n, m \le 1000

Osatehtävä 4 (48 pistettä)

• n = m
• 2 \le n, m \le 1000