Ve İşte Yarışma Sorumuz;
LAMBADA
Lambada tek kişilik oynanan bir oyundur.
Oyunun kuralları:
- Bu oyun her kişinin sırayla tahta üzerinde kendi çözümlerini sergilediği bir oyundur. Yani tek oyunculu bir oyundur.
- Oyun satrançta olduğu gibi küçük karelere bölünmüş bir alanda oynanır. Oyun alanı dikdörtgen şeklindedir.
- Oyun tahtasının her karesi bir düğümdür ve bu düğümler bir lambadır.
- Düğmelerden herhangi birinin basılması ile o düğmenin yakılması veya söndürülmesi gerçekleştirilir. Basılan düğme tersi olan duruma geçmektedir ve bu durumda ilgili düğmenin yatay ve dikey komşuları da mevcut durumun tersi durumla değiştirilir. Yani düğme eğer yanıksa sönük, sönükse yanık duruma geçmektedir.
- Her yarışmanın başında oyuncuya, oyun tahtasının başlangıç dizilimi, hakem tarafından rastgele dizilmiş düğümler ile verilir. Dolayısıyla her yarışmada düğümlerin başlangıç dizilimleri değişebilir.
- Oyunun amacı, lambaları, düğümlerin başlangıç dizilimlerinden yola çıkarak, kurallara uygun hamleler yaparak, yine hakem tarafından oyunun başında açıklanan ya tüm lambalar yanık ya da tüm lambalar sönük olma durumuna en az hamle ile getirmektir.
- Oyuncu ne kadar az hamle yaparsa o kadar çok puan alır.
- Çözümün herhangi bir adımında herhangi bir düğüm yakılabilir veya söndürülebilir.
Varsayımlar:
1. Oyun tahtası yatayda N, dikeyde M kareden oluşmaktadır. (9 ? N, M ? 27)
2. Her karenin her bir kenarı bir pozitif tamsayı ile numaralandırılmıştır. Buna göre en güneydeki ve en batıdaki kenarların numaralandırılması 1?den başlamaktadır. Eğer batı-doğu eksenindeki kenar numaralarına ‘x’, güney-kuzey eksenindeki kenar numaralarına
‘y’ denirse: 1 ? x ? N, 1 ? y ? M’dir.
3. Her bir kare “x y” şeklinde ifade edilmektedir.
4. Programınız girdileri “lambada.gir” isimli dosyadan okuyup, çıktıları “lambada.cik” isimli dosyaya yazmalıdır.
Girdi (lambada.gir):
Girdi dosyasının ilk satırında N ve M tamsayıları sırası ile verilecektir. Bundan sonraki satırlarda düğümlerin yanık olan başlangıç pozisyonları (kareleri) “x y” şeklinde verilecektir. Diğer düğümler sönük olarak kabul edilecektir. Yanıklık “1” ile sönüklük “0” ile ifade edilecektir. Dosyanın son satırında oyunun bitiş durumda lambaların olması gereken durum “0” veya “1” olarak belirtilecektir.
Çıktı (lambada.cik):
Çıktı dosyasının ilk satırında toplam hamle sayısı verilmelidir. Takip eden tüm satırlarda ise her bir hamle bir satır olmak üzere bastığınız düğümün koordinatlarını vermelidir.
Örnek:
.
.
. |
Önceki durumu “0”dı. Kendisine basıldığında “1” oldu. Komşu yatay ve dikey düğümler mevcut durumlarının ters durumlarına döndüler.
(3,6 karesinde)
n |
Batı  Doğu
Güney
m |
8 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
7 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
6 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
5 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
4 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
3 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
. . . |
lambada.gir |
lambada.cik |
9 9
3 5
4 8
5 9
9 3
2 2
3 3
4 5
4 7
5 6
5 9
1 |
23
3 5
7 4
8 2
4 4
4 3
5 7
6 6
3 8
9 2
2 6
… |
Not: Değerler rastgele verilmiştir ve tutarsızlık olabilir. Genel mantığın anlaşılması için gösterilmiştir. “lambada.cik” dosyasına girilen hamle sayıları ve hamlelerin doğruluğu hakem programı tarafından test edilecektir. Problemin çözümünde kaba kuvvet yöntemleri dâhil değişik yaklaşımlar düşünülebilir. Ancak bunların içersinde en basit ve sağlam çözüm analitik çözümdür.
Hazırlayan: Yusuf Bahadır PASKALOĞLU
Ödülümüz: 2GB USB Bellek+ Süpriz Bir Ödül Daha:)
İletişim için: lamerarikan@hotmail.com
|
