Զրոյական XOR ենթաբազմություն

Տրված է չափի մատրից և ամբողջ թիվ, որտեղ , , իսկ մատրիցի բոլոր տարրերը -բիթանոց ոչ բացասական ամբողջ թվեր են։

Պետք է ընտրել մատրիցի տարրերի այնպիսի ենթաբազմություն, որ ընտրված տարրերի բիթային XOR-ը հավասար լինի -ի, և յուրաքանչյուր տողից ու յուրաքանչյուր սյունից ընտրված լինի առնվազն մեկ տարր։

Եթե գոյություն ունեն մի քանի լուծումներ, արտածել դրանցից կամայականը։

Բիթային XOR-ը (Բացառիկ ԿԱՄ - Exclusive OR, որը նշվում է սիմվոլով) երկուական գործողություն է, որը համեմատում է երկու թվերի (կամ տողերի) համապատասխան բիթերը: Արդյունքի բիթը է, եթե համեմատվող բիթերը տարբեր են, և , եթե դրանք նույնն են: Օրինակ՝ :

Հիմնական կանոնները

Հատկություններ

• Նույնականություն.

• Ինքնահակադարձում.

• Տեղափոխականություն.

• Զուգորդականություն.

Մուտքային տվյալները

Առաջին տողում տրված են երեք ամբողջ թվեր :
Հաջորդ տողերից յուրաքանչյուրում տրված են ամբողջ թվեր, որոնք ներկայացնում են մատրիցի տարրերը։

Ելքային տվյալները

Առաջին տողում արտածել մեկ ամբողջ թիվ ՝ ընտրված տարրերի քանակը։ Հաջորդ տողերից յուրաքանչյուրում արտածել երկու ամբողջ թիվ , , որոնք նշանակում են, որ ընտրվել է -րդ տողի և -րդ սյան տարրը։
Տողերն ու սյուները համարակալվում են 1-ից։

Օրինակներ

3 3 1
1 0 1
1 1 1
0 1 1

3
2 1
1 2
3 3

5 5 2
1 1 2 2 3
3 3 1 1 2
2 3 3 1 1
1 1 2 3 0
3 3 3 3 3

7
1 3
2 3
3 3
4 4
5 2
4 1
3 5

5 5 4
1 2 8 10 12
9 7 6 5 3
2 1 4 3 13
8 7 10 12 14
7 5 3 4 2

8
1 4
2 1
3 2
4 4
5 3
5 5
1 3
2 2

Օրինակների բացատրություն

Առաջին օրինակում կարող ենք ընտրել , և տարրերը, որոնց արժեքները համապատասխանաբար , և են: Այս ընտրությունը ճիշտ ծածկում է բոլոր տողերն ու սյուները, իսկ դրանց բիթային XOR-ը է:

Երկրորդ օրինակում կարող ենք ընտրել , , , , , և տարրերը, որոնց արժեքներն են համապատասխանաբար , , , , , և : Այս ընտրությունը ծածկում է բոլոր տողերն ու սյուները, իսկ դրանց բիթային XOR-ը է:

Ենթախնդիրները

Եթե ենթախնդրում տարրի համար սահմանափակում նշված չէ, ապա տեղի ունեն հետևյալ սահմանափակումները․

• ,

• :