Forum
Aktif konular
Üyeler
Kurallar
Arama
Java Nested Loop Alternatif Java Nested Loop Alternatif
-
Problemi okuyunca aklıma ilk gelen çözüm her noktanın hangi köşegende olduğunu bulmak oldu. Bir çizim yapıp aynı köşegen üzerindeki noktaları yazınca bir örüntü fark ettim. Aşağıdaki fotoğrafta görebilirsin bunu.
https://www.dropbox.com/s/92zle1epcl363ij/20160201_204728.jpg?dl=0
Buna göre yalancı kod yazacağım. Java'da yazıp sonucu bildirir misin?
Köşegen1 ve Köşegen2 1997 elemanlı arrayler. Bu arraylerin her bir elemanı da o köşegendeki noktaları tutan arrayler. Köşegen1 toplamla elde edilen, köşegen2 de farkla elde edilen köşegeni tutuyor. x tüm x'lerin arrayi y tüm y'lerin arrayi her n noktası için index1 = x[n]+y[n] - 2 index2 = x[n]-y[n]+999 köşegen1[index1].ekle(n) köşegen2[index2].ekle(n) sayac = 0 köşegen1 içerisindeki her bir array a için sayac += a.size() köşegen2 içerisindeki her bir array a için sayac += a.size()
İndexler 1den başlayacak şekilde tasarlandı. Veri yapılarını kafana göre ayarla. Bir de tahta 1000x1000 olacak şekilde değerleri seçtim. O(nokta sayısı + köşegen sayısı) o da yaklaşık O(n+2000)
-
uLtRaLoVeR bunu yazdı
Problemi okuyunca aklıma ilk gelen çözüm her noktanın hangi köşegende olduğunu bulmak oldu. Bir çizim yapıp aynı köşegen üzerindeki noktaları yazınca bir örüntü fark ettim. Aşağıdaki fotoğrafta görebilirsin bunu.
https://www.dropbox.com/s/92zle1epcl363ij/20160201_204728.jpg?dl=0
Buna göre yalancı kod yazacağım. Java'da yazıp sonucu bildirir misin?
Köşegen1 ve Köşegen2 1997 elemanlı arrayler. Bu arraylerin her bir elemanı da o köşegendeki noktaları tutan arrayler. Köşegen1 toplamla elde edilen, köşegen2 de farkla elde edilen köşegeni tutuyor. x tüm x'lerin arrayi y tüm y'lerin arrayi her n noktası için index1 = x[n]+y[n] - 2 index2 = x[n]-y[n]+999 köşegen1[index1].ekle(n) köşegen2[index2].ekle(n) sayac = 0 köşegen1 içerisindeki her bir array a için sayac += a.size() köşegen2 içerisindeki her bir array a için sayac += a.size()
İndexler 1den başlayacak şekilde tasarlandı. Veri yapılarını kafana göre ayarla. Bir de tahta 1000x1000 olacak şekilde değerleri seçtim. O(nokta sayısı + köşegen sayısı) o da yaklaşık O(n+2000)
Düşününce fark ettim ki direk toplamak olmuyor kombinasyon hesaplamak lazım. Bir köşegen üzerinde k tane bishop olsun, kombinasyon(k,2) bize tüm ikilileri verecektir.
-
uLtRaLoVeR bunu yazdıuLtRaLoVeR bunu yazdı
Problemi okuyunca aklıma ilk gelen çözüm her noktanın hangi köşegende olduğunu bulmak oldu. Bir çizim yapıp aynı köşegen üzerindeki noktaları yazınca bir örüntü fark ettim. Aşağıdaki fotoğrafta görebilirsin bunu.
https://www.dropbox.com/s/92zle1epcl363ij/20160201_204728.jpg?dl=0
Buna göre yalancı kod yazacağım. Java'da yazıp sonucu bildirir misin?
Köşegen1 ve Köşegen2 1997 elemanlı arrayler. Bu arraylerin her bir elemanı da o köşegendeki noktaları tutan arrayler. Köşegen1 toplamla elde edilen, köşegen2 de farkla elde edilen köşegeni tutuyor. x tüm x'lerin arrayi y tüm y'lerin arrayi her n noktası için index1 = x[n]+y[n] - 2 index2 = x[n]-y[n]+999 köşegen1[index1].ekle(n) köşegen2[index2].ekle(n) sayac = 0 köşegen1 içerisindeki her bir array a için sayac += a.size() köşegen2 içerisindeki her bir array a için sayac += a.size()
İndexler 1den başlayacak şekilde tasarlandı. Veri yapılarını kafana göre ayarla. Bir de tahta 1000x1000 olacak şekilde değerleri seçtim. O(nokta sayısı + köşegen sayısı) o da yaklaşık O(n+2000)
Düşününce fark ettim ki direk toplamak olmuyor kombinasyon hesaplamak lazım. Bir köşegen üzerinde k tane bishop olsun, kombinasyon(k,2) bize tüm ikilileri verecektir.
aynen öyle reyiz çözüm bu son dediğin gibi olacak. kombinatorik. mevzusu. Dediğin yolu bi implement edeyim bakayım.
whopper tarafından 02/Şub/16 09:37 tarihinde düzenlenmiştir -
abi biri bana açıklayabilir mi bu amk kodu 30.satırda nasıl division by zero verebiliyor. orayı 0 yapan şeyler 0,1,2 onlarında koşulu var zaten benim mi beynim durdu. Bu arada gayet hızlı çalışıyor çözüm bu sağol ultralover
package codeforces; import java.util.Scanner; public class WSBishopB2 { public static void main(String[] args) { Scanner key = new Scanner(System.in); int bishnum = key.nextInt(); int [] arr = new int[800000]; for(int i=0;i<bishnum;i++){ int a = key.nextInt(); int b = key.nextInt(); if(a-b<0){ arr[Math.abs(a-b)+40000]+=1; arr[a+b]+=1; } else{ arr[a-b]++; arr[a+b]++; } } int total=0; for(int i=0;i<bishnum*2;i++){ if(arr[i]!=0){ if(arr[i]==2) total++; else if(arr[i]==1); else total+=factorial(arr[i])/(factorial(arr[i]-2)*factorial(2)); } } System.out.println(total); key.close(); } public static int factorial(int n) { int fact = 1; for (int i = 1; i <= n; i++) { fact *= i; } return fact; } }
whopper tarafından 02/Şub/16 10:55 tarihinde düzenlenmiştir -
O satırda factorial(2) yerine doğrudan 2 yazarak biraz daha performans kazanabilirsin.
Ayrıca problem senin factorial metodundan kaynaklı. Büyük sayılar için o metod mutlaka sıfır döner. Mesela factorial (1000). Bunun sebebi de integer tipinin tutabileceği sayının uzunluğu. Integer overflow ve underflow terimlerine bir bak derim.
Mesela şu kod blogunun çıktısına bakalım:
for (int i = 0; i < 40; i++) { System.out.println(i + " :: " + factorial(i)); }Şöyle olacaktır:
0 :: 1
1 :: 1
2 :: 2
3 :: 6
4 :: 24
5 :: 120
6 :: 720
7 :: 5040
8 :: 40320
9 :: 362880
10 :: 3628800
11 :: 39916800
12 :: 479001600
13 :: 1932053504
14 :: 1278945280
15 :: 2004310016
16 :: 2004189184
17 :: -288522240
18 :: -898433024
19 :: 109641728
20 :: -2102132736
21 :: -1195114496
22 :: -522715136
23 :: 862453760
24 :: -775946240
25 :: 2076180480
26 :: -1853882368
27 :: 1484783616
28 :: -1375731712
29 :: -1241513984
30 :: 1409286144
31 :: 738197504
32 :: -2147483648
33 :: -2147483648
34 :: 0
35 :: 0
36 :: 0
37 :: 0
38 :: 0
39 :: 0
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla