makethemmeet
Day2 Tasks

European Girls'Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Turkish (TUR)

D. Buluşmalarını SağlaProblem AdıBuluşmalarını SağlaZaman Limiti

9 saniyeHafıza Limiti

1 gigabyte

Mila ve Laura uzun süredir internette arkadaşlar; ancak gerçek hayatta hiç tanışmadılar. Şu andaikisi de aynı etkinliğe katılıyorlar, bu da kesinlikle buluşacakları anlamına geliyor. Ancak ikisinin dekaldığı otel oldukça büyük ve kafa karıştırıcıdır. Bu nedenle birkaç gün sonra hâlâ birbirlerine
rastlamamışlardır.
Otel, 0'dan N − 1'e kadar numaralandırılmış N tane odadan oluşmaktadır. Her odada farklı
renklere dönüştürülebilen bir lamba bulunmaktadır. Elektrik servis odasını buldunuz ve bu size
lambaların renklerini değiştirme imkanı sağlamıştır. Amacınız, Mila ve Laura'nın lambalararacılığıyla birbirlerini bulmalarını sağlamak için onları yönlendirmektir.
Otel, N düğüm (odalar) ve M kenar (odaları bağlayan koridorlar) içeren bir çizge (graph) olarak
temsil edilebilir. Mila ve Laura başlangıçta iki farklı odadadır, ancak hangi odalarda olduklarınıbilmiyorsunuz. Bir dizi hareket yapabilirsiniz. Her hareket, N tam sayısından oluşan bir listeyi
yazdırmakla ilgilidir: c0 , c1 , ..., cN −1 , bu da her i = 0, 1, ..., N − 1 için odadaki lambanın renginin ci
olacağı anlamına gelir. Mila ve Laura daha sonra, bulundukları odadaki lambanın rengini
gözlemleyip aynı renkteki lambaya sahip komşu bir odaya geçer. Eğer böyle bir komşu oda yoksa,bulundukları odada kalırlar. Eğer birden fazla bu şekilde aynı renkte uygun komşu oda varsa,bunlardan birini rastgele seçerler.
Eğer Mila ve Laura herhangi hareketinizde aynı odada bulunur veya aynı koridoru aynı anda
kullanırlarsa, onları başarılı bir şekilde buluşturduğunuzu kabul ederiz. En fazla 20 000 hareket
yapabilirsiniz, ancak daha az hareket kullanarak daha yüksek puan elde edersiniz.
Mila ve Laura'nın hangi odada başladığını veya birden fazla aynı renkte odadan hangisiniseçeceklerini bilmediğinizi unutmayın. Çözümünüz, onların başlangıç odalarına veya yürüyüştercihlerini nasıl yapacaklarına bakılmaksızın doğru olmalıdır.

Girdi
İlk satırda oteldeki oda sayısı N ve koridor sayısı olmak M üzere iki tam sayı, N ve M , bulunur.

makethemmeet (1 of 4)

Bunu takip eden M satırın her biri iki tam sayı ui ve vi içerir; bu da ui ve vi odalarının bir koridorlabirbirine bağlandığını belirtir.

ÇıktıBir satıra hareket sayısını belirten K tam sayısını yazdırın.
Sonraki K satırın her birine N tane tam sayı c0 , c1 , ..., cN −1 yazdırın; burada 0 ≤ ci ≤ N her i içingeçerlidir. Bu K satır, hareketlerinizi kronolojik sıraya göre temsil eder.

Kısıtlar ve Puanlama
2 ≤ N ≤ 100.
N − 1 ≤ M ≤ N (N2−1) .
0 ≤ ui , vi ≤ N − 1, ve ui ≠ vi .
Her odadan diğer tüm odalara ulaşılabilir. Ayrıca, hiçbir odadan kendine giden koridor
yoktur ve herhangi bir oda çifti arasında birden fazla koridor yoktur.
En fazla K ≤ 20 000 hareket yapabilirsiniz.
Çözümünüz bir dizi test grubunda test edilecektir; her test grubu belirli bir puan değerindedir. Hertest grubu bir dizi test senaryosu içerir. Bir test grubundan puan almak için, test grubundaki tüm
test senaryolarını çözmeniz gerekir.

GrupMaxpuan

110213311436

M = N − 1. Yani, çizge bir ağaçtır.

530

Ek kısıt yoktur.

Limitler

M = N − 1, ve koridorlar şunlardır: (0, 1), (0, 2), (0, 3), ..., (0, N − 1). Başkabir deyişle, çizge bir yıldızdır (star).

M = N (N2−1) , yani, herbir oda çifti arasında koridor vardır. Başka bir deyişle,çizge tamdır (complete).

M = N − 1, ve koridorlar şunlardır (0, 1), (1, 2), (2, 3), ..., (N − 2, N − 1).
Yani, çizge bir yol (path) dir.

Her test grubunu doğru bir şekilde çözdüğünüzde, aşağıdaki formüle dayalı olarak bir puan (score)alırsınız:score = ⌊Sg ⋅ min (1, Kg2000+ 15 )⌋ ,+1900

makethemmeet (2 of 4)

Burada Sg test grubunun maksimum puanı ve Kg test grubundaki herhangi bir test senaryosundaçözümünüzün kullandığı maksimum hareket sayısını temsil eder. Tam puan almak için tüm test
senaryolarında en fazla 600 hareket kullanabilirsiniz. Aşağıdaki şekil, Kg 'ye bağlı olarak puansayısını göstermektedir.

ÖrnekÖrnek senaryo, uzunluğu 3 olan bir yoldur, yani bu, alt görev 3, 4, veya 5'e ait olabilir. Eğer odalarınışıkları örnek çıktısına göre renklendirilirse, Mila ve Laura her zaman buluşur.
Örneğin, Mila'nın oda 0'da ve Laura'nın oda 1'de başladığını varsayalım:İlk hareket: Mila oda 1'e geçmelidir. Eğer Laura oda 0'a geçerse, o zaman 0 ve 1 arasındaki
koridorda buluşacaklardır. Bunun yerine, Laura'nın oda 2'ye gittiğini varsayalım.
İkinci hareket: Mila oda 0'a geri döner ve Laura oda 2'de kalır.
Üçüncü hareket: Mila tekrar oda 1'e gider ve Laura oda 2'de kalır.
Dördüncü hareket: Mila oda 2'ye geçer ve Laura oda 1'e geçer. Böylece 1 ve 2 odaları
arasındaki koridorda buluşurlar.
Beşinci hareket: Mila ve Laura yer değiştirir ve tekrar buluşurlar (ancak zaten buluştuklarıiçin bu önemli değildir).
Aşağıdaki şekil, örneğin ilk dört hareketini göstermektedir.

Bu durumun yalnızca Mila ve Laura'nın 0 ve 1 numaralı odalardan başladığı hali olduğunuunutmayın. Aynı hareketler serisinin, arkadaşların başlangıç noktaları ve nasıl yürüdüklerindenbağımsız olarak buluşmalarını sağlayacağını doğrulayabilirsiniz.

makethemmeet (3 of 4)

GirdiÇıktı

3 20 152 2 21 22 2 32 2 3
1 2 2
1 2 2

makethemmeet (4 of 4)