Task: | Tontti |
Sender: | kalh |
Submission time: | 2015-09-29 19:04:04 +0300 |
Language: | Java |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.19 s | 1 | details |
#2 | WRONG ANSWER | 0.20 s | 1 | details |
#3 | WRONG ANSWER | 0.20 s | 1 | details |
#4 | WRONG ANSWER | 0.20 s | 1 | details |
#5 | WRONG ANSWER | 0.19 s | 1 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | TIME LIMIT EXCEEDED | -- | 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
import java.util.*;import java.math.*;public class Tehtava3 {public static class Puu {int x;int y;public Puu(int _x, int _y) {x = _x;y = _y;}}public static void laskeTavat(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);ArrayList<Puu> puut = new ArrayList<Puu>();for (int i = 0; i<korkeus; i++) {for (int j = 0; j<leveys; j++) {//System.out.println(metsa[i].charAt(j));if (metsa[i].charAt(j) == '*') {Puu p = new Puu(j, i);puut.add(p);}}}//System.out.println("eka: " + (System.currentTimeMillis()-t));int maara = 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;int maaraAlueella = puidenMaara(j, k, i, puut);if (maaraAlueella == puita) {//System.out.println("levyeys: " + j +", korkeus: " + k + ", koko: " + i +", puita: " + maaraAlueella);maara++;}else if (maaraAlueella > puita) {break;}}}}//System.out.println("toka: " + (System.currentTimeMillis()-t));System.out.println(maara);}public static int puidenMaara(int alkux, int alkuy, int koko, ArrayList<Puu> puut) {int maara = 0;for (Puu puu : puut) {if (puu.x >= alkux && puu.x < alkux+koko && puu.y >= alkuy && puu.y < alkuy+koko) {maara++;if (alkux == 1 && alkuy== 1 && koko == 2) {// System.out.println(puu.x + ":" + puu.y);}//System.out.println(puu.y + ":" + puu.x);}}return 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('*');elsesb.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 main(String[] args) {//IO io = new IO();//int korkeus = io.nextInt();//int leveys = io.nextInt();//int puita = io.nextInt();Scanner s = new Scanner(System.in);String[] arvot = new String[3];int korkeus = 0;int leveys = 0;int puita = 0;arvot = s.nextLine().split("\\s+");korkeus = Integer.parseInt(arvot[0]);leveys = Integer.parseInt(arvot[1]);puita = Integer.parseInt(arvot[2]);String[] metsa = new String[korkeus];//for (int i = 0; i<korkeus; i++) {// metsa[i] = s.nextLine();// }// metsa[0] = "..**..";//metsa[1] = "**....";// metsa[2] = "*...*.";// metsa[3] = "..*...";metsa = luoSatunnainen(leveys, korkeus);// tulostaMetsa(metsa);laskeTavat(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: WRONG ANSWER
input |
---|
10 10 5 ********** ********** ********** ********** ... |
correct output |
---|
0 |
user output |
---|
21 |
Test 3
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 10 10 **...*...* *..*.**.*. ...**.*..* *...**.*.. ... |
correct output |
---|
4 |
user output |
---|
5 |
Test 4
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 10 5 ****...... *.*.**..** ....*.*..* ...*.***.. ... |
correct output |
---|
16 |
user output |
---|
18 |
Test 5
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 10 2 **.***..*. ...*.*.... .***.*...* ***.***..* ... |
correct output |
---|
30 |
user output |
---|
37 |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
(empty) |
Test 8
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
(empty) |
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: TIME LIMIT EXCEEDED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
(empty) |