Task: | Tontti |
Sender: | kalh |
Submission time: | 2015-10-01 18:32:46 +0300 |
Language: | Java |
Status: | READY |
Result: | 47 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | ACCEPTED | 33 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.17 s | 1 | details |
#2 | ACCEPTED | 0.18 s | 1 | details |
#3 | ACCEPTED | 0.17 s | 1 | details |
#4 | ACCEPTED | 0.18 s | 1 | details |
#5 | ACCEPTED | 0.17 s | 1 | details |
#6 | ACCEPTED | 0.53 s | 2 | details |
#7 | ACCEPTED | 0.44 s | 2 | details |
#8 | ACCEPTED | 0.30 s | 2 | details |
#9 | ACCEPTED | 0.31 s | 2 | details |
#10 | ACCEPTED | 0.32 s | 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | ACCEPTED | 0.78 s | 3 | details |
#14 | ACCEPTED | 0.76 s | 3 | details |
#15 | ACCEPTED | 0.89 s | 3 | details |
Code
import java.util.*; import java.math.*; public class Tehtava3 { private static int[][] arvot; private static int korkeus; private static int leveys; private static HashMap<Integer, Integer> puuarvot; public static void laskeTavat(int korkeus, int leveys, String[] metsa, int puita) { //long t = System.currentTimeMillis(); int pieninKoko = (int)Math.ceil(Math.sqrt(puita)); int maksimiKoko = Math.min(korkeus, leveys); // System.out.println("1. Osa: " + (System.currentTimeMillis()-t) + "ms"); int maara = 0; int maaraAlueella = 0; int alaarvo = pieninKoko; int ylaarvo = maksimiKoko; int valiarvo = 0; int valimaksimi = 0; for (int j = 0; j <= leveys - pieninKoko; j++) { for (int k = 0; k <= korkeus - pieninKoko; k++) { valimaksimi = Math.min(korkeus - k, leveys - j); alaarvo = pieninKoko; ylaarvo = valimaksimi; valiarvo = (ylaarvo + alaarvo) / 2; // BINAARIHAKU while (puidenMaara(j, k, valiarvo) != puita && alaarvo <= ylaarvo) { maaraAlueella = puidenMaara(j, k, valiarvo); if (maaraAlueella > puita) { ylaarvo = valiarvo - 1; } else if (maaraAlueella < puita) { alaarvo = valiarvo + 1; } valiarvo = (ylaarvo + alaarvo) / 2; } while (puidenMaara(j, k, alaarvo) >= puita) { alaarvo--; } alaarvo++; while (puidenMaara(j, k, ylaarvo) == puita) { ylaarvo++; } ylaarvo--; //System.out.println(alaarvo + ":" + ylaarvo + ", (" + puidenMaara(j, k, alaarvo) + ", " + puidenMaara(j, k, ylaarvo) + ")"); for (int d = alaarvo; d <= ylaarvo; d++) { int loydettyMaara = puidenMaara(j, k, d); if (loydettyMaara == puita) { maara++; } } } } //System.out.println("Kesto: " + (System.currentTimeMillis() - t) + "ms"); System.out.println(maara); } public static int puidenMaara(int alkux, int alkuy, int koko) { if (koko == 0) return 0; //if (puuarvot.containsKey(koko)) //return puuarvot.get(koko); if (alkux+koko > leveys) return 0; if (alkuy + koko > korkeus) return 0; int arvo1 = 0; int arvo2 = 0; int arvo3 = 0; int arvo4 = arvot[alkux+koko-1][alkuy+koko-1];; if (alkux != 0) { arvo3 = arvot[alkux-1][alkuy+koko-1]; } if (alkuy != 0) { arvo2 = arvot[alkux+koko-1][alkuy-1]; if (alkux != 0) arvo1 = arvot[alkux-1][alkuy-1]; } int tulos = (arvo1+arvo4-arvo2-arvo3); return tulos; } public static void laskeTavatHidas(int korkeus, int leveys, String[] metsa, int puita) { //long t = System.currentTimeMillis(); int tulos = 0; int pieninKoko = (int)Math.ceil(Math.sqrt(puita)); int maksimiKoko = Math.min(korkeus, leveys); // System.out.println("1. Osa: " + (System.currentTimeMillis()-t) + "ms"); int maara = 0; int maaraAlueella = 0; for (int j = 0; j<=leveys-pieninKoko; j++) { for (int k = 0; k<=korkeus-pieninKoko; k++) { for (int i = pieninKoko; i<=maksimiKoko; i++) { if (k+i > korkeus || j+i > leveys) break; maaraAlueella = puidenMaara(j, k, i); if (maaraAlueella == puita) { //System.out.println(j + ":" + k + ", " + i); maara++; } else if (maaraAlueella > puita) { break; } } } } //System.out.println("2. Osa: " + (System.currentTimeMillis()-t) + "ms"); System.out.println(maara); } public static String[] luoSatunnainen(int leveys, int korkeus) { StringBuilder sb; String[] metsa = new String[korkeus]; Random r = new Random(); for (int i = 0; i<korkeus; i++) { sb = new StringBuilder(); for (int j = 0; j<leveys; j++) { int a = r.nextInt(9); if (a <= 1) sb.append('*'); else sb.append('.'); } metsa[i] = sb.toString(); } return metsa; } public static void tulostaMetsa(String[] metsa) { for (int i = 0; i<metsa.length; i++) { for (int j = 0; j<metsa[0].length(); j++) { System.out.print(metsa[i].charAt(j) + " "); } System.out.println(); System.out.println("--------------------------------------"); } } public static void luoArvoTaulukko(String[] metsa) { // metsa[0] = leveys //metsa = korkeus //arvot[0] = korkeus // arvot = leveys //long t1 = System.currentTimeMillis(); int summa1 = 0; for (int i = 0; i<leveys; i++) { if (metsa[0].charAt(i) == '*') { summa1++; } arvot[i][0] = summa1; } int summa2 = 0; for (int y = 1; y<metsa.length; y++) { summa1 = 0; summa2 = 0; for (int x = 0; x<metsa[0].length(); x++) { if (metsa[y].charAt(x) == '*') summa2++; summa1 = arvot[x][y-1]; arvot[x][y] = (summa1+summa2); } } //System.out.println("arvotaulukon luontiin meni " + (System.currentTimeMillis()-t1) + "ms"); } public static void tulostaArvoTaulukko() { System.out.println(); for (int i = 0; i<arvot[0].length; i++) { for (int j = 0; j<arvot.length; j++) { System.out.print(arvot[j][i] + " | "); } System.out.println("--------------"); } } public static void main(String[] args) { IO io = new IO(); korkeus = io.nextInt(); leveys = io.nextInt(); int puita = io.nextInt(); // korkeus = 2000; //leveys = 2000; //int puita = 100; String[] metsa = new String[korkeus]; for (int i = 0; i<korkeus; i++) { metsa[i] = io.next(); } arvot = new int[leveys][korkeus]; //puuarvot = new HashMap<Integer, Integer>(); //metsa[0] = "..**.."; //metsa[1] = "**...."; //metsa[2] = "*...*."; //metsa[3] = "..*..."; //metsa[0] = ".*.*"; //metsa[1] = "...*"; //metsa[2] = ".*.."; //metsa[3] = ".*.*"; //metsa = luoSatunnainen(leveys, korkeus); //tulostaMetsa(metsa); // luoArvoTaulukko(metsa); //tulostaArvoTaulukko(); laskeTavat(korkeus, leveys, metsa, puita); //laskeTavatHidas(korkeus, leveys, metsa, puita); } }
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 1 ......*... .......*.. *..*....*. *....*.... ... |
correct output |
---|
94 |
user output |
---|
94 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ********** ********** ********** ********** ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 10 **...*...* *..*.**.*. ...**.*..* *...**.*.. ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ****...... *.*.**..** ....*.*..* ...*.***.. ... |
correct output |
---|
16 |
user output |
---|
16 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 2 **.***..*. ...*.*.... .***.*...* ***.***..* ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
9552040 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
1536063 |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
288 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
786 |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
1763 |
Test 11
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
(empty) |
Test 12
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
(empty) |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
1849 |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
2665 |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
5587 |