CSES - DatatÃ¤hti 2016 alku - Results
 Task: Tontti Sender: kalh Submission time: 2015-10-11 22:04:29 Language: Java Status: READY Result: 47
Feedback
groupverdictscore
#1ACCEPTED14
#2ACCEPTED33
#30
Test results
testverdicttimegroup
#1ACCEPTED0.17 s1details
#2ACCEPTED0.18 s1details
#3ACCEPTED0.18 s1details
#4ACCEPTED0.17 s1details
#5ACCEPTED0.18 s1details
#6ACCEPTED0.43 s2details
#7ACCEPTED0.32 s2details
#8ACCEPTED0.30 s2details
#9ACCEPTED0.32 s2details
#10ACCEPTED0.30 s2details
#11--3details
#12--3details
#13ACCEPTED0.49 s3details
#14ACCEPTED0.57 s3details
#15ACCEPTED0.66 s3details

### Code

```import java.util.*;
import java.math.*;

public class Tehtava3 {

private static int[][] arvot;
private static int korkeus;
private static int leveys;
private static IO io;
private static long t;
private static int pieninKoko;
private static int ya2;

public static void laskeTavat(int korkeus, int leveys, String[] metsa, int puita) {

int puitaYhteensa = arvot[leveys-1][korkeus-1];

int maara = 0;
int maaraAlueella = 0;
int alaarvo = 0;
int ylaarvo = 0;
int valiarvo = 0;
int valimaksimi = 0;
int loydettyMaara = 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
maaraAlueella = puidenMaara(j, k, valiarvo);

while (maaraAlueella != puita && alaarvo <= ylaarvo) {
if (maaraAlueella > puita) {
ylaarvo = valiarvo - 1;
} else {
alaarvo = valiarvo + 1;
}

valiarvo = (ylaarvo + alaarvo) / 2;
maaraAlueella = puidenMaara(j, k, valiarvo);

}

for (int d = ylaarvo; d >= alaarvo; d--) {
loydettyMaara = puidenMaara(j, k, d);

if (loydettyMaara == puita) {
maara++;
}

else if (loydettyMaara < puita) {
break;
}

}

}

}

//System.out.println("Kesto: " + (System.currentTimeMillis() - t) + "ms" +", [" + leveys + ", " + korkeus + "], " + puita + ", tulos: " + maara);
io.print(maara);
}

public static int puidenMaara(int alkux, int alkuy, int koko) {

if (alkux + koko > leveys || alkuy + koko > korkeus)
return -1;

int maxx = alkux + koko - 1;
int maxy = alkuy + koko - 1;

if (maxx < 0 || maxy < 0)
return 0;

int arvo1 = 0;
int arvo2 = 0;
int arvo3 = 0;
int arvo4 = arvot[maxx][maxy];

if (alkux != 0) {
arvo3 = arvot[alkux - 1][maxy];
}

if (alkuy != 0) {
arvo2 = arvot[maxx][alkuy - 1];

if (alkux != 0)
arvo1 = arvot[alkux - 1][alkuy - 1];
}
return (arvo1 + arvo4 - arvo2 - arvo3);

}

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(10);
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) {

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 main(String[] args) {

io = new IO();

korkeus = io.nextInt();
leveys = io.nextInt();
int puita = io.nextInt();

//korkeus = 2000;
//leveys = 2000;
//int puita = 1000;

String[] metsa = new String[korkeus];

for (int i = 0; i < korkeus; i++) {
metsa[i] = io.next();
}

arvot = new int[leveys][korkeus];

//metsa = luoSatunnainen(leveys, korkeus);

//
// tulostaMetsa(metsa);

//t = System.currentTimeMillis();

//
luoArvoTaulukko(metsa);
// tulostaMetsa(metsa);

// tulostaArvoTaulukko();
pieninKoko = (int) Math.ceil(Math.sqrt(puita));

// System.out.println("Kesto: " + (System.currentTimeMillis()-t));
io.close();

}

}```

### 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:

input
2000 2000 1
.................................

correct output
489611392

user output
(empty)

#### Test 12

Group: 3

Verdict:

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