IEEEXtreme 2008 - Sorular ve Cevaplar
IEEEXtreme, 24 saat boyunca internetten üzerinden gönderilen problemleri çözmek gereken IEEE’nin düzenlediği bir programcılık yarışması. 02.12.2006 tarihinde ilki düzenlendi. Bu sene de ikincisi düzenlendi.
Dünya çapından katılan 125 takımdan 16 tanede Türk takımı vardı. Buna bende Doğuş Üniversitesi'nde IEEE klübü üyesi olan 3 kişilik bir takımla katıldım. İşin ilginç kısmı Türkiye'deki dağılımın çok dengesiz olmasıydı. 15 takım Bilkent Üniversitesi'nden ve 1 takımda biz.
Sorular:
Sorulara gelirsek, geçen seneye göre aşırı zorlaşmış ve soru sayısı artmış. Geçen sene 8 soru + 4 bonus vardı. Bu sene 10 soru + 6 bonus oldu. Kendi yaptığım sorulardan bazılarını anlatmaya çalışacağım:
ieeextreme2008-competition-booklet.pdf
ieeextreme2008-competition-booklet2.pdf
ieeextreme2008-competition-booklet3.pdf
Problem 1: Merging IP ranges (IP aralıklarını birleştirme)
Bazı spyware ve adware programları zararlı kaynakların IP adreslerini karaliste (blacklist, blocklist) adında bir dosyada saklarlar. Bazı karalisteler 250.000'den fazla kayıt içerebilir. Örnek bir karaliste dosyasının başlangıcı:
3.0.0.0-3.255.255.255
4.0.25.146-4.0.25.148
4.0.26.14-4.0.29.24
4.2.144.64-4.2.144.95
4.2.144.224-4.2.144.231
4.2.144.248-4.2.144.255
4.2.145.224-4.2.145.239
...
Hedef: Örnekteki gibi bir dosyayı standart input'tan okuyup bu aralıkları olabildiğince birleştirip ve kısaltıp yazdırmak.
Örnek girdi:
S
3.201.0.0-3.255.255.255
4.0.25.146-4.0.25.148
4.0.26.14-4.0.29.24
4.2.144.64-4.2.144.95
3.0.0.0-3.200.255.255
4.2.144.224-4.2.144.231
4.2.144.248-4.2.144.255
4.2.145.224-4.2.145.239
3.100.255.0-3.110.111.111
Örnek çıktı:
3.0.0.0-3.255.255.255
4.0.25.146-4.0.25.148
4.0.26.14-4.0.29.24
4.2.144.64-4.2.144.95
4.2.144.224-4.2.144.231
4.2.144.248-4.2.144.255
4.2.145.224-4.2.145.239
Problem 7: Snapshot (Arama motoru algoritması)
Bu arama algoritması aranan kelimeleri dökümanlarda bulmaya çalışırken bu kelimelerin geçtiği en geniş ve kesintisiz olan metin parçasını yakalamaya çalışır. Bulduğu bu metin parçasının kaç kelimeden oluştuğuda bu sonucun önemini (significance) gösterir.
Hedef: Standart input'tan sadece boşluklarla ayrılmış bir metin alan ve programa parametreler olarak gönderilen anahtar kelimelere (keywords) göre önem derecesini bulan programı yazın.
Örnek girdi:
The registration for the 2008 edition of IEEEXtreme is now open
Programınız şu şekilde çalıştırılacak:
> snapshot 2008 IEEEXtreme
Konsolda 4 yazması bekleniyor.
Not: Hiçbir kelime bulunamazsa 0 yazmalı.
Yorum yok