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

Soru 3: Evden Eve Nakliyat

Problem
Ankara'da üniversite okumakta olan Uğur, yeni bir eve taşınmak istemektedir. Fakat eşyalarını toplarken kamyonu ne kadar az doldurursa nakliyata o kadar az bir ücret ödemektedir. Bu yüzden Uğur'un kolilerini, hiçbir koli bir diğeriyle üst üste gelmeden en verimli şekilde yerleştirmesi gerek. Örneğin Uğur'un elinde dört adet koli olsun ve bunları koordinat düzleminde orijinden başlayarak ilk çeyreğe yerleştirmeye çalışsın. (Kolileri yerleştirirken yerçekiminin, diğer fizik kurallarının olmadığını ve sadece iki boyutta yerleştirdiğinizi düşünebilirsiniz. Kutular birbirlerine değmek zorunda da değillerdir, havada da durabilirler. Fakat kutuları yan yatırmak veya herhangi bir açıda döndürmek mümkün değildir.)

Şekil 1

Üstteki Şekil 1'e göre Uğur'un elinde 20x10, 10x10, 5x5 ve 5x1 boyutunda dört kutu var ve Uğur bunları iki farklı şekilde yerleştiriyor (I ve II), bunlar sonucunda ulaştığı en son (x,y) koordinatı iki şekilde de (20,20) oluyor. Bu nedenle Uğur 20+20=40 TL para vermek zorunda kalacak. Fakat bu kutuları yanyana yerleştirseydi daha masraflı olacaktı.

Uğur sizden elindeki kutuları en az yer tutacak şekilde nasıl yerleştirebileceğini öğreneceği bir program istiyor. Programınıza dikdörtgen nesneleri, dikdörtgenlerin kesişip kesişmediğini bulan metod, bir noktada bir koli bulunup bulunmadığını söyleyen metod, dikdörtgeni belli bir koordinata koyan bir metod, bütün dikdörtgenleri birbirleriyle kontrol edip kesişen olup olmadığını söyleyen metod, bir dikdörtgenin başlangıç koordinatını ve genişlik-yüksekliğini bir satırda ekrana yazdıran bir metod vb. Bir önceki sorudaki gibi hazırladığımız şablonlarda hazır olarak bulunmaktadır.

Kısıtlamalar ve Şablon

• (Dikdörtgen sayısı) <= 100
• 1 <= (Dikdörtgenlerin bir kenar uzunluğu) <= 100
• Dikdörtgenler iki boyutta xy-düzlemine yerleştirilecektir, kenarları birbirine değmek zorunda değildir, fakat bir nokta üzerinde iki adet dikdörtgensel bölge veya iki dikdörtgene ait kenar bulunamaz, yani dikdörtgenler kesişemezler.
• Dikdörtgenler herhangi bir açıda döndürülemezler, yan yatırılamazlar.
• Dikdörtgen nesnelerinin sahip oldukları x,y koordinatları (başlangıç noktası) x-y düzleminde sol alt (güneybatı) noktalarını temsil eder ve hiçbiri negatif bir sayı olamaz. Yani dikdörtgenler 1. bölgeye yerleştirilmelidir.
• Programınızda yerleştirme düzeneğini yazacağınız metoda ek olarak kendiniz metodlar, veri tipleri tanımlayabilirsiniz. Dikdörtgen nesnesine ek metodlar ve özellikler ekleyebilirsiniz, mevcut olanları çıkaramazsınız. Kodunuzu şablona ek başka dosyalara da yazabilirsiniz.
• Şablondaki ana çalışma metodunda (main) test girdileri verilir, dikdörtgenlerin başlangıç durumları ekrana basılır, ardından yazacağınız metod çağırılır, daha sonra yine bütün dikdörtgenler ekrana basılır. Ardından main'de yeniden bütün dikdörtgenlerin x-y-genişlik-yükseklik özellikleri ekrana basılır, kesişen dikdörtgenler varsa hangileri olduğu ekrana yazılır. Son olarak kesişen dikdörtgen yoksa dikdörtgenler yerleştirildikten sonra x ekseninde ulaşılan en son nokta, y ekseninde ulaşılan en son nokta ve bu ikisinin toplamı şablon tarafından hesaplanır ve ekrana yazdırılır.
• Algoritmanızı sadece C/C++, Java, C# ve PHP dillerinden birini kullanarak kodlayabilirsiniz. C++ test kodunu indirmek için buraya, Java test kodunu indirmek için buraya, C# test kodunu indirmek için buraya, PHP test kodunu indirmek için buraya tıklayınız. Eğer test kodlarında hata alırsanız düzeltip algoritmanızı test edecek hale getirebilirsiniz. C dilini kullanmak için C++ test şablonunu değiştirebilirsiniz.
• Algoritmanızı test şablonlarındaki yerlestir metodunun içine yazmalısınız. Kendi yazdığınız metodları bu metod içinden çağırmanız zorunludur.
• C/C++ kodları Ubuntu 9.10 işletim sisteminde gcc_4.3.3 kullanılarak, Java kodları Ubuntu 9.10 işletim sisteminde jdk6 kullanılarak, C# kodları .NET 3.5 yüklü Windows™ 7 işletzim sisteminde derlenecektir.
• Özyineli (recursive) algoritmaların kullanımı serbesttir. Fakat veritabanı kütüphanelerini kullanamazsınız. C/C++ için STL kullanımı serbesttir ve memory leak'ler değerlendirme kriteri değildir.
• Kullanabileceğiniz geçici bellek (RAM) en fazla 3 GB'dır. Intel Core 2 Duo T5550 1.83 GHz işlemcide programınız 20 saniye içinde sonuç vermelidir.
• Şablon dosyalarındaki main komutunun içindeki liste adındaki array, deneme olarak verilmiş olup başlangıç noktaları orijinde bulunan ve boyutları 5x5, 20x10, 10x20 olan üç dikdörtgene aittir. C/C++ kullanacaklar için bu array'in boyutunu belirten bir dikdortgenSayisi değişkeni de test esnasında değiştirilecektir. Çözümünüzü test etmek amacıyla buraya kendiniz yeni dikdörtgenler ekleyebilirsiniz. Biz de testler esnasında bu satırları değiştirerek sonuca bakıyor olacağız. Şablon'un main fonksiyonundaki örnek dikdörtgenleri çalışır hale gelmesi için y ekseni boyunca üste yerleştirmek için aşağıdaki kod yerlestir metoduna yazılabilir (Java), fakat unutmayınız ki testler esnasında dikdörtgen sayıları sabit olmayacaktır.

  	liste[1].tasi(0,5);
  	liste[2].tasi(0,15);

  Algoritmanızı uyguladıktan sonra aşağıdaki çıktıyı almanız gerekmektedir. Aksi takdirde hala üst üste gelen dikdörtgenler vardır.

  	Ta$ima Sonrasi Kesi$en Dikdortgen?: yok (TAMAMDIR)

Değerlendirme ve Ödüller

• Testlerde 3, 5, 20 ve 100 tane dikdörtgen denenecektir. Her yarışmacının çözümüne aynı dikdörtgenlerle hazırlanan test uygulanacaktır.
• Çözümünüz tam değil ise veya düşük bir verimle çalışıyorsa bile gönderiniz. Tam çözüm alınamadığı durumlarda en iyi çözümler sıralanır ve ödül almaya hak kazanırlar.
• Dört testte yapılan sıralamalar sonucunda en iyi olan (en düşük maliyeti elde edebilen) iki yarışmacıya KODLAB yayınlarından istedikleri birer kitap ve Türkiye Bilişim Derneği tarafından yarışmada derece aldığınızı gösterir katılım sertifikası verilecektir.
• Eğer ikiden fazla eşit puan elde eden yarışmacı olursa kura çekilir.
• Çözümleri birbirlerinden çalıntı olduğu tespit edilen yarışmacılar bir daha yarışmaya katılamazlar ve ödül alamazlar.
• Çıktı formatında satır boşlukları, hizalama vb. önem taşımamaktadır. Algoritmanın doğru çalışıp çalışmadığı önemlidir.
• Ödül kazananlarla birlikte tam çö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.

Düzeltmeler

• UYARI: Çözümünüzü göndermeden önce bu sayfayı tekrar ziyaret ediniz. Soru metninde veya şablonda değişiklikler yapıldığına burada açıklanıyor olacaktır.

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

• Çözümlerinizde çalışan dosyayı (exe, out..) değil, kaynak kodu dosyasını gönderiniz.
• Çözümlerinizi, yazdığınız kodla beraber test kodunu da içeren dosyayı iletinize ekleyerek, mesaj kısmına adınız, soyadınız, okulunuz, bölümünüz, sınıfınız, tam ikamet adresiniz, telefonunuz ve KODLAB'dan istediğiniz kitabı kitap listesinden seçerek ankara@tbdgenc.com adresine "Soru 3" 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ümlerinizi en geç 27 Mayıs 2010 saat 17:00'a kadar göndermelisiniz. Geç çözümler kabul edilmeyecektir.
• Yarışmaya sadece üniversite (lisans), yüksek lisans ve doktora öğrencileri katılabilir. Yarışma bütün üniversitelerdeki öğ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.

Başarılar!

« Ana sayfaya dön