Submission details
Task:Tontti
Sender:hello_world
Submission time:2015-10-01 19:10:03 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.06 s1details
#20.05 s1details
#30.05 s1details
#40.06 s1details
#50.05 s1details
#60.05 s2details
#70.06 s2details
#80.05 s2details
#90.05 s2details
#100.05 s2details
#110.09 s3details
#120.09 s3details
#130.13 s3details
#140.11 s3details
#150.12 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:40:8: warning: variable 'pointersToLines' set but not used [-Wunused-but-set-variable]
  Line *pointersToLines[h];
        ^
input/code.cpp:48:15: warning: unused variable 'lines' [-Wunused-variable]
  unsigned int lines = 0; //montako lineä on muistissa
               ^
input/code.cpp:62:31: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(char_line, len, stdin);
                               ^

Code

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <stdlib.h>

using namespace std;

struct Line{
	unsigned int *trees_x;	//listaa puiden määrän x-suunnassa
	unsigned int *trees_y;	//listaa puiden määrän y-suunnassa
	unsigned int *r;		//matka edelliseen puuhun, joko y-tai x-suunnassa
	Line *next;
	Line *last;
	bool *isTree;
};

void printTreesX(Line *ap, unsigned int w);
void printTreesY(Line *ap, unsigned int w);
void printIsTree(Line *ap, unsigned int w);
void printR(Line *ap, unsigned int w);

int main(void){
	
	unsigned int h, w, x;	//korkeus, leveys, puiden määrä aluetta kohti
	
	cin >> h;	//korkes
	cin >> w;	//leveys
	cin >> x;	//puita / alue (voi olla myös nolla, ota se huomioon)

	Line *a = (Line *)malloc(sizeof(Line));
	a->next = NULL;
	a->last = NULL;
	a->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->r = (unsigned int *)malloc(sizeof(unsigned int) * w);
	a->isTree = (bool *)malloc(sizeof(bool) * w);
	
	//tämä sisältää pointerit lineihin, jotta ei pidä aina välttämättä toimia ->last:n ja next->n avulla
	Line *pointersToLines[h];

	unsigned int v = w;
	while(v--) {			
		a->r[v] = 0;	//ensimmäisellä rivillä ei ole lähintä matkaa ('oikea yläkulma'), vaan se on aina nolla, sillä lähimmästä matkasta mitataan kuinka paljon pitää kasvattaa kokoa
		//a->trees_y[v] = 0;	//myöskään ensimmäisen rivin yläpuolella ei ole puita
	}
	Line *ap = a;
	unsigned int lines = 0;	//montako lineä on muistissa
	unsigned int len = w + 1;
	char *char_line = (char*)malloc(sizeof(unsigned int) * len);


	if (!feof(stdin)) fgetc(stdin);
	
	unsigned int i = h;
	
	while(i--) {
		//huomioi, että myös pontersToLines on +:sta -:s suuntaan menevä, kuten lähes kaikki muukin tässä ohjelmassa
		pointersToLines[i] = ap;	
		
		cout << "i:" << i << " " << char_line << endl;
		fgets(char_line, len, stdin);
		fgetc(stdin);
		
		//katsotaan montako puuta uudella linellä oli, muodostetaan uusi Line
		unsigned int j = w;
		unsigned int tree_count = 0;
		
		while(j--){
			if (char_line[j] == '*') {
				tree_count++;			//lisätään puiden määrää x-suunnassa yhdellä, nopeampi tehdä counterilla kuin samalla tyylillä kuin y:n
				ap->isTree[j] = true;
				if (ap->last != NULL) ap->trees_y[j] = (ap->last)->trees_y[j] + 1;	//puiden määrä y-suunnassa lisääntyy yhdellä
				else ap->trees_y[j] = 1;
			} else {
				ap->isTree[j] = false;	//ei toimi
				if (ap->last != NULL) {
					ap->trees_y[j] = (ap->last)->trees_y[j];	//puiden määrä y-suunnassa pysyy samana
				}else ap->trees_y[j] = 0;
			}
			ap->trees_x[j] = tree_count;	//rivin alkiosta[ind] rivin loppuun olevien puiden määrä
			if (j < w - 1){ //j > 0, ei ole ensimmäinen alkio
				if (ap->last != NULL){	//ei ole ensimmäinen rivi
					if ((ap->last)->isTree[j]) ap->r[j] = 1;	//puu suoraan yläpuolella, joudutaan kasvattamaan kokoa yhdellä jos halutaan saada puu
					else if (ap->isTree[j + 1]) ap->r[j] = 1;	//puu sivulla joudutaan kasvattamaan kokoa yhdellä, jos halutaan saada puu
					else if ((ap->last)->isTree[j + 1]) ap->r[j] = 1;
					else {
						unsigned int m = min((ap->last)->r[j], ap->r[j + 1]);
						if ((ap->last)->r[j] != 0 || ap->r[j + 1] != 0) ap->r[j] = m + 1;	//ei ole aivan puun vieressä, joten etäisyyttä puuhun kasvatetaan yhdellä, kasvatettavaa matkaa lisätään yhdellä
						else ap->r[j] = m;	//jos molemmat y+1 ja x+1 matkat ovat 0, niin myös tämän matka on nolla, muutoin ... +1
					}
				}
			} else ap->r[j] = 0;
		}
		
		//lasketaan neliöt
		/*unsigned int v = w;
			cout << "a->";
			while(v--){
				cout << ap->trees[v] << " " << endl; 
			}*/
		//katsotaan onko lines tarpeeksi suuri, jotta voidaan alkaa muodostamaan neliön muotoisia
		
		if (i) {	//muodostetaan uusi line, mikäli tarvetta, eli linejen ottamista jatketaan vielä
			ap->next = (Line *)malloc(sizeof(Line));
			(ap->next)->last = ap;
			ap = ap->next;
			ap->trees_x = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->trees_y = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->r = (unsigned int *)malloc(sizeof(unsigned int) * w);
			ap->isTree = (bool *)malloc(sizeof(bool) * w);
		}
		
		//nyt on uusi line jälleen alustettu(ja kenties vanha poistettu)
		
	}
	
	//nyt on kaikki linet tallessa
	
	//cout << endl; printTreesX(ap, w);
	//cout << endl; printTreesY(ap, w);
	//cout << endl; printIsTree(ap, w);
	//cout << endl; printR(ap, w);
	
	//määritetään kullekin ruudulle pienin mahdollinen neliön koko, eli että alkaa tulemaan puita
	
	/*
	
	//saadaan selville kuinka paljon kokoa on minimissään suurennettava, löydetään puita
	
	selataan rivi kerrallaan:
		rivi1: alustetaan nollaksi
		muut rivit:
			-jokaisen rivin ensimmäinen alkio on nolla
			-jokainen alkio on yhden suurempi kuin pienempi kahdesta seuraavasta on
				-edellisen rivin saman x:n omaava alkio(last, x)
				-current rivin edellisen y:n omaava alkio(cur, x - 1)	
	*/
	
	/*
		1.nyt on selvillä jokaisen rivin jokaisen alkion matka(x tai y)
		lähimpään 'mustaan' alkioon
		
		2.lasketaan kuinka monta puuta on alueella (size = matka)
			*jos alueella on liian vähän puita:
				-tarkistetaan kuinka paljon alueen kokoa pitää vielä lisätä
					*etsitään yläreunaa ja vasenta sivua kiertämällä pienimmän matkan 
					 omaava alkio, min(matka, line->matka)
	
	*/

	
	free(char_line);
	//free(pointersToLines);

	return 0;
	
}

void printTreesX(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->trees_x[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printTreesY(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->trees_y[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printIsTree(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->isTree[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void printR(Line *ap, unsigned int w){
	Line *l = ap;
	while(l != NULL) {
		unsigned int w2 = w;
		cout << "line: ";
		while (w2--){
			cout << l->r[w2] << " ";
		} cout << endl;
		l = l->last;
		cin.get();
	}
}

void freeMemory(Line *line){
	Line *l;
	do {
		l = line;
		line = line->last;
		free(l->trees_x);
		free(l->trees_y);
		free(l);
	} while(line->last != NULL);
}

Test details

Test 1

Group: 1

Verdict:

input
10 10 1
......*...
.......*..
*..*....*.
*....*....
...

correct output
94

user output
i:9 
i:8 ......*...
i:7 .......*..
i:6 *..*....*.
i:5 *....*....
...

Test 2

Group: 1

Verdict:

input
10 10 5
**********
**********
**********
**********
...

correct output
0

user output
i:9 
i:8 **********
i:7 **********
i:6 **********
i:5 **********
...

Test 3

Group: 1

Verdict:

input
10 10 10
**...*...*
*..*.**.*.
...**.*..*
*...**.*..
...

correct output
4

user output
i:9 
i:8 **...*...*
i:7 *..*.**.*.
i:6 ...**.*..*
i:5 *...**.*..
...

Test 4

Group: 1

Verdict:

input
10 10 5
****......
*.*.**..**
....*.*..*
...*.***..
...

correct output
16

user output
i:9 
i:8 ****......
i:7 *.*.**..**
i:6 ....*.*..*
i:5 ...*.***..
...

Test 5

Group: 1

Verdict:

input
10 10 2
**.***..*.
...*.*....
.***.*...*
***.***..*
...

correct output
30

user output
i:9 
i:8 **.***..*.
i:7 ...*.*....
i:6 .***.*...*
i:5 ***.***..*
...

Test 6

Group: 2

Verdict:

input
500 500 1
.................................

correct output
9552040

user output
i:499 
i:498 ...........................

Test 7

Group: 2

Verdict:

input
500 500 5
.................................

correct output
1536063

user output
i:499 
i:498 ...........................

Test 8

Group: 2

Verdict:

input
500 500 25000
**...*...**..*.*..*.**.*..*.*....

correct output
288

user output
i:499 
i:498 **...*...**..*.*..*.**.*...

Test 9

Group: 2

Verdict:

input
500 500 12500
**.**.*..*...*.**...*.***........

correct output
786

user output
i:499 
i:498 **.**.*..*...*.**...*.**...

Test 10

Group: 2

Verdict:

input
500 500 5000
.*.*.**..*.*.**.**..*..**...*....

correct output
1763

user output
i:499 
i:498 .*.*.**..*.*.**.**..*..*...

Test 11

Group: 3

Verdict:

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

correct output
489611392

user output
i:1999 
i:1998 ..........................

Test 12

Group: 3

Verdict:

input
2000 2000 5
.................................

correct output
120725884

user output
i:1999 
i:1998 ..........................

Test 13

Group: 3

Verdict:

input
2000 2000 400000
..*..**.**.**.*.***...**.*..**...

correct output
1849

user output
i:1999 
i:1998 ..*..**.**.**.*.***...*...

Test 14

Group: 3

Verdict:

input
2000 2000 200000
***.*....*.*..*....**..*..*.*....

correct output
2665

user output
i:1999 
i:1998 ***.*....*.*..*....**.....

Test 15

Group: 3

Verdict:

input
2000 2000 80000
**.**...*.***.**....**.*....*....

correct output
5587

user output
i:1999 
i:1998 **.**...*.***.**....**....