Ödüllü Yarışma

Sınavlar başlamadan güzel bir deneyim olabilir. Önemli olan katılmak, yarışma havasına girmek. Sen katıldın mı diyeceksin. Daha fırsat olmadı diyelim. :) Ama boş vaktim olsa mutlaka uğraşırdım.

TBD Genç Ankara - Ödüllü Programlama Sorusu 8

(Bu soru TBD Genç Ankara Ekim 2010 bülteninde yayımlanmıştır.)

Soru: Yalancılar

Problem

Yeni bir kasabaya doğru yola çıktınız. Gittiğiniz kasabadaki herkes ya her zaman doğruyu söylüyor, ya da her zaman yalan söylüyor. Yani yalan söyleyen biri hiçbir zaman doğruyu söylemiyor; doğru söyleyen biri de hiçbir zaman yalan söylemiyor.

Ardından kimlerin doğru kimlerin yalan söylediğini anlamak amacıyla bütün halka "bu kasabada kim yalan söylüyor?" diye tek tek soruyorsunuz. Kasabadakiler kimlerin doğru söylediğini ve kimlerin yalancı olduğunu biliyorlar, fakat kime sorsanız size tüm yalancıların listesini vermiyor. Bu yüzden olabildiğince çok veri toplamanız gerekli. Sizden bu kasabada, yalan söyleyen ve doğru söyleyenlerin sayısını bulmanız için bir program yazmanız isteniyor. Programınız ilk olarak çoğunluk olan gruptaki (doğru söyleyenler veya yalan söyleyenler), ardından azınlık olan gruptaki kişi sayısını ekrana yazdırmalı.

Örnek Girdi-Çıktı Biçimi

• Girdinin ilk satırında kasabadaki kişi sayısı n verilir .
• Sonraki satırda "yalan söyleyenler kimler?" sorusunu sorduğunuz kişinin adı ve sayacağı kişi sayısı m verilir. Takip eden m satırda ise yalancı olarak söyleyeceği kişilerin isimleri verilir. Örneğin:
  
  

  Emre 3
  Burcu
  Cakil
  Ceren

• Kişi isimlerinde sadece Latin alfabesindeki karakterler kullanılır ve en fazla 10 karakterli olur. Büyük-küçük harf hassasiyeti vardır. Tek kelimeden oluşur (boşluk içermez).
• Kasabadaki herkese tek tek kimlerin yalancı olduğu sorulur ve çıktıda bu veri kesinlikle verilir. Bir kişi kimseyi yalancı olarak söylemiyorsa adının yanındaki m değeri 0 olarak verilir.
• Girdide verilen bilgilere göre (sorulan sorulardan alınan cevaplara göre) kasabadaki kişiler tüm yalan söyleyenlerin (veya yalancı olanlar tüm iftira atmak istediklerinin) listesini vermeyebilirler. Bu nedenle bu bilgileri girdiden toplayıp çıkarım yapmanız gerek. Girdi dosyaları her zaman bu çıkarımları yapmanız için yeterli bilgiyi içerecek şekilde verilecektir.
• Çıktıda çoğunluğu oluşturan gruptaki kişi sayısı ve azınlığı oluşturan gruptaki kişi sayısı aralarında bir boşluk olacak şekilde aynı satırda verilmesi yeterlidir. Unutmayın ki bu iki grubun toplam sayısı kasaba nüfusuna (n) eşit olmalıdır.

Örnek girdi:

5
Emre 1
Kubra
1
Ceren
Kubra
 
Ilkay 1
n 1
K
Kubra
Cer
eubra
Cakil 2

Ilkay

Emre

Bu durumda çıktı şu şekilde olmalıdır:

3 2

Kısıtlamalar

• Toplam nüfus (n): 1 <= n <=1000
• Kişilerin isim uzunluğu: 1 <= i <= 10

Çözüm Kriterleri

• Bir komut satırı (console, command line) uygulaması yazmanız beklenmektedir. Pencere arayüzlü çözümler kabul edilmeyecektir.
• Çıktı formatında satır boşlukları, hizalama vb. önem taşımamaktadır. Algoritmanın doğru çalışıp çalışmadığı önemlidir.
• Algoritmanızı sadece C/C++, Java, C# veya Python dillerinden birini kullanarak kodlayabilirsiniz. Bu soruda veritabanı kullanımı ve dışarıda herhangi bir dosyaya yazmaların yapılmasına izin verilmemektedir.
• C/C++ kodları Unix tabanlı bir işletim sisteminde (Ubuntu, Pardus vb. veya Windows'ta Cygwin üzerinden) gcc-4.3.3 derleyicisi kullanılarak, Java kodları Windows™ 7 işletim sisteminde jdk6u20 kullanılarak, C# kodları .NET 3.5 yüklü Windows™ 7 işletim sisteminde derlenecektir ve çalıştırılacaktır. Python kodları Windows üzerinde 32-bit Python 2.6.5 kullanılarak çalıştırılacaktır.

Değerlendirme, Sıralama ve Ödüller

• Doğru çözüm yollayan yarışmacılar arasından kurayla seçilen iki yarışmacı ödül almaya hak kazanır.
• Yapılan sıralama sonucunda en iyi olan iki yarışmacıya KODLAB yayınlarından istedikleri birer kitap verilecektir.
• Ödül kazananlarla birlikte doğru çözüm bulanların da isimleri ve okulları TBD Genç Ankara web sitesindeki haberde, e-posta listesi duyurularında ve bültenin sonraki sayısından yayımlanır.

Çözümlerin Ulaştırılması

• Çözümlerinizi, yazdığınız kodla beraber iletinize ekleyerek, mesaj kısmına adınız, soyadınız, okulunuz, bölümünüz, sınıfınız, (kargonun teslim edilebileceği) tam ikamet adresiniz, telefonunuz ve KODLAB'dan istediğiniz kitabı kitap listesinden seçerek ankara@tbdgenc.com adresine "Soru 8" başlığıyla e-posta olarak göndermeniz gerekmektedir. (İsim ve okul dışında bilgileriniz saklı tutulmaktadır. Doğru çözüm gönderenlerin isimleri ve okulları yayınlanır.)
• Çözümlerinizde çalışan dosyayı (exe, out..) değil, kaynak kodu dosyasını gönderiniz.
• Birden fazla kaynak dosyası gönderecek olmanız durumunda sıkıştırıp (zip) göndermeniz tercih edilir.
• Çözümlerinizi en geç 29 Ekim 2010 saat 17:00'a kadar göndermelisiniz. Geç çözümler kabul edilmeyecektir.
• Yarışmaya sadece lise, üniversite (lisans), yüksek lisans ve doktora öğrencileri katılabilir. Yarışma T.C. vatandaşlarına ve Türkiye'de yaşama hakkı olan öğrencilere açıktır.
• E-Postalarınızın spam'e düşmemesi adına güvendiğiniz bir e-posta adresinden göndermeniz önerilir.

Düzeltmeler

Çözümünüzü yollamadan önce bu sayfayı tekrar ziyaret etmeyi unutmayınız. 

Başarılar