CSES - Datatähti 2016 alku - Results
Submission details
Task:Tontti
Sender:kalh
Submission time:2015-10-11 22:04:29 +0300
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));
laskeTavat(korkeus, leveys, metsa, puita);
// System.out.println("Kesto: " + (System.currentTimeMillis()-t));
//laskeTavatHidas2(korkeus, leveys, metsa, puita);
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