Courses

algoritmalar

Belirli bir maskenin tüm alt modellerini yineleyin

Module: Belirli bir maskenin tüm alt modellerini yineleyin

Problem

5 /7

Eric ve LED Kartı

Theory Click to read/hide

Belirli bir uzunluktaki tüm bit dizilerini numaralandırmak gerekli olur. Veya başka bir deyişle, her nesne için iki olası durumdan birinin seçildiği tüm olası seçenekleri yineleyin.

Bu gibi durumlarda, bit maskeleri kullanarak numaralandırma yapmak mümkündür. Bu yaklaşımın avantajı, bu tür bir kodun yinelemesiz çalışması ve koleksiyonlar veya benzerleri yerine sayılar üzerinde çalışmasıdır, bu da performansı büyük ölçüde artırır.

Bit maskelerini kullanan genel kod aşağıda verilmiştir: int; // onesne sayısı (bit dizisinin uzunluğu) for (int mask = 0; mask < (1 << n); mask++) { // 0'dan 2^n - 1'e kadar tüm sayılar arasında döngü yapın, burada her sayı bir bit maskesine karşılık gelir // geçerli sayı maskesi, i'inci bitin i'inci nesnenin durumunu belirttiği bir bit maskesidir for (int i = 0; i < n; i++) { // her nesnenin hangi duruma sahip olduğunu anlamak için n biti tekrarla if ((1
Bu kod O(2^n * f(n)) içinde çalışır, burada f(n), belirli bir yinelemeyi işlemeniz için geçen süredir.

Problem

Eric, büyükbabasının eski garajında bir LED panosu buldu. Ancak, etkinleştirildiğinde diyotların birbiriyle senkronize olmamasına şaşırdı. Yani bazıları yandı, bazıları yanmadı.
Tahtanın kendisinin olağandışı olduğu ortaya çıktı. Her hücrenin bir diyot içerdiği n satır ve m sütunlu dikdörtgen bir ızgaradır. Her sıranın yanında, bu sıradaki tüm diyotları değiştiren bir kol vardır (yanan diyotlar söner ve tersi). Her sütun aynı kaldıraçlara sahiptir (ilgili sütunda diyotları kullanıyorum).
Eric, kolları değiştirerek diyotları aynı duruma getirmenin mümkün olup olmadığını merak etti.

Giriş:
İlk satır iki doğal sayı n ve m içerir (1 <= n, m <= 7) - sırasıyla tahtadaki satır ve sütun sayısı.
Sonra, her biri m numaralı n satır vardır - diyotların durumları; burada 0, diyotun kapalı olduğu ve 1'in açık olduğu anlamına gelir.

Çıktı:
Diyotları bir duruma getirmek mümkünse "EVET", mümkün değilse "HAYIR" yazdırın.

Örnekler:

Açıklama:
İlk örnekte, ilk satırdaki tüm diyotları değiştirebilir, ardından ilk sütundaki tüm diyotları değiştirebilirsiniz. Ardından tüm diyotlar kapanacaktır.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking