hkucuk

Sherlock mu? Ben mi? Süper Bilgisayar mı?

August 16, 2015 • ☕️ 2 dk okuma • 🏷 bilgisayar, yazılım

Yazar tarafından şu dillere çevrildi: English


Bu yazıda dedektif kahramanların en ünlüsü Sherlock Holmes‘e yardımcı olmaya çalışacağız. Sherlock Holmes süper bilgisayara karşı.


Senaryomuz

Sherlock Holmes, ezeli düşmanı olan Moriarty hakkında iyice paranoyaklaşır. Moriarty’i bastırmak için sarfettiği tüm çabaları boşa çıkmıştır. Sherlock bugünlerde Watson ile bir sorun üzerine çalışmaktadır. Watson, son zamanlarda, CIA’in süper bilgisayarı Beast’de tuhaf sorunlarla karşı karşıya olduğunu belirtmiştir.

Bu öğleden sonra Sherlock, Moriarty’den Beast’e bir virüs aracılığı ile sızdığını belirten, bir not alır. Ayrıca, notun üzerinde N adet numara vardır. Bazı hesaplamalar yaptıktan sonra Sherlock virüsü kaldırmak için gereken anahtarın en büyük makul değerinin N basamaklı olacağını çözmüştür.

En makul sayının aşağıdaki özelliklere sahip olması gerekmektedir:

  • Basamaklarda yalnızca 3 veya 5 rakamları kullanılabilir. Başka rakamlar olmamalıdır.
  • Bir çok kez kullanılan 3 sayısı 5 ile bölünebilir.
  • Bir çok kez kullanılan 5 sayısı 3 ile bölünebilir.

Bu arada sayaç Beast’i imha etmek amacıyla çok hızlı çalışıyor. Acaba biz Beast’i kurtarmak için gerekli anahtarı bulabilir miyiz? Peki bunu Sherlock’tan önce yapabilir miyiz?

Girdi Biçimi: 1. satır test durumlarının sayısını ifade edecek bir tam sayı (T) olacaktır.

Çıkış Biçimi: En büyük makul sayımız N basamaklı olacaktır. Eğer eğer bir numarak girilmezse Sherlock yanlış girdi olduğunu söylecek ve ekrana -1 yazacaktır.


Kısıtlamalar

  • 1≤T≤20
  • 1≤N≤100000

Açıklama

  • N = 1 için, geçerli değildir.
  • N = 3 için, 555 tek olası sayıdır.
  • N = 5 için 33.333 tek olası sayıdır.
  • N = 11, 55555533333 bu rakamlarla oluşturulabilecek olasılıklar arasındaki en büyük sayıdır.

Çözümümüz

/*
 * Coding by hkucuk
 */
import java.io.*;

public class SolutionSTB {

    public static void main(String[] args) throws IOException {

        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        byte[] mults = new byte[]{0, 2, 4, 1, 3, 0, 2, 4, 1, 3};

        for(int T = Integer.parseInt(br.readLine()); T > 0; T--){

            String S = br.readLine();
            int N = Integer.parseInt(S);
            
            // Silinecek kaç tane 5'li grup var
            int G = mults[S.charAt(S.length()-1) - 48];
            N -= 3*G;
            
            // Eğer numara çok küçükse
            if (N < 0){ sb.append("-1\n"); continue; } // 5 gruplarını ekleme for(G += 5*(N/15); G > 0; G--){
                sb.append("555");
            }
            
            // 3 gruplarını ekleme
            for(G = (N%15)/5; G > 0; G--){
                sb.append("33333");
            }
            
            // Yeni satır ekleme
            sb.append("\n");
        }
        
        System.out.print(sb);
    }
}

Örnek Girdi

4
1
3
5
11

Örnek Çıktı

-1
555
33333
55555533333