CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:zfoil
Submission time:2024-11-10 15:01:01 +0200
Language:C
Status:READY
Result:20
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.01 s2, 3, 4, 5, 6details
#7ACCEPTED0.01 s2, 3, 4, 5, 6details
#8ACCEPTED0.01 s2, 3, 4, 5, 6details
#9ACCEPTED0.01 s2, 3, 4, 5, 6details
#10ACCEPTED0.20 s3, 4, 5, 6details
#11ACCEPTED0.18 s3, 4, 5, 6details
#12ACCEPTED0.20 s3, 4, 5, 6details
#13ACCEPTED0.17 s3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 5, 6details
#17--4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21--5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Compiler report

input/code.c: In function 'main':
input/code.c:143:16: warning: unused variable 'j' [-Wunused-variable]
  143 |         int i, j, result;
      |                ^
input/code.c:143:13: warning: unused variable 'i' [-Wunused-variable]
  143 |         int i, j, result;
      |             ^
input/code.c: In function 'create_field':
input/code.c:97:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |                 scanf("%s", flowers_in_row);
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.c: In function 'main':
input/code.c:145:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         scanf("%d", &field.width);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <stdio.h>
#include <stdlib.h>
typedef struct {
int letter_count[26];
} Alphabet;
typedef struct {
int width;
Alphabet *NW_flowers;
Alphabet *empty_alphabet;
} Field;
int get_letter_index(char c)
{
return (int)c - 65;
}
void reset_alphabet(Alphabet *alphabet)
{
int i;
for (i = 0; i < 26; i++) {
alphabet->letter_count[i] = 0;
}
}
void copy_alphabet(Alphabet *destination, Alphabet *source)
{
int i;
for (i = 0; i < 26; i++) {
destination->letter_count[i] = source->letter_count[i];
}
}
int contains_all_species(Alphabet *alphabet, Alphabet *all_flowers)
{
int i;
for (i = 0; i < 26; i++) {
if (alphabet->letter_count[i] < 1 && all_flowers->letter_count[i] != 0) {
return 0;
}
}
return 1;
}
void add_alphabets(Alphabet *term1, Alphabet *term2)
{
int i;
for (i = 0; i < 26; i++) {
term1->letter_count[i] += term2->letter_count[i];
}
}
void subtract_alphabets(Alphabet *term1, Alphabet *term2)
{
int i;
for (i = 0; i < 26; i++) {
term1->letter_count[i] -= term2->letter_count[i];
}
}
void print_alphabet(Alphabet *alphabet)
{
int i;
for (i = 0; i < 26; i++) {
printf("%d", alphabet->letter_count[i]);
}
printf("\n");
}
Alphabet *get_at(Field *field, int column, int row)
{
if (column < 0 || row < 0) {
return field->empty_alphabet;
}
return field->NW_flowers + row * field->width + column;
}
void update_flower_count(Field *field, int row, int column, Alphabet *row_running_total)
{
if (row > 0) {
copy_alphabet(get_at(field, column, row), get_at(field, column, row - 1));
} else {
reset_alphabet(get_at(field, column, row));
}
add_alphabets(get_at(field, column, row), row_running_total);
}
void create_field(Field *field)
{
int row, column, letter_index;
char *flowers_in_row;
Alphabet row_running_total;
flowers_in_row = malloc(field->width * sizeof(*flowers_in_row));
for (row = 0; row < field->width; row++) {
scanf("%s", flowers_in_row);
reset_alphabet(&row_running_total);
for (column = 0; column < field->width; column++) {
letter_index = get_letter_index(flowers_in_row[column]);
row_running_total.letter_count[letter_index]++;
update_flower_count(field, row, column, &row_running_total);
}
}
}
void get_quadrant_alphabet(Alphabet *result, Field *field, int x, int y, int width, int height)
{
Alphabet *full, *top_excess, *bottom_excess, *corner;
full = get_at(field, x + width - 1, y + height - 1);
top_excess = get_at(field, x + width - 1, y - 1);
bottom_excess = get_at(field, x - 1, y + height - 1);
corner = get_at(field, x - 1, y - 1);
add_alphabets(result, full);
subtract_alphabets(result, top_excess);
subtract_alphabets(result, bottom_excess);
add_alphabets(result, corner);
}
int get_number_of_possible_fences(Field *field)
{
int total = 0, i, j, k, l, max = field->width - 1;
Alphabet result, *all_flowers;
all_flowers = get_at(field, max, max);
for (i = max; i >= 0; i--) {
for (j = max; j >= 0; j--) {
for (k = i + 1; k <= max + 1; k++) {
for (l = j + 1; l <= max + 1; l++) {
reset_alphabet(&result);
get_quadrant_alphabet(&result, field, i, j, k - i, l - j);
if (contains_all_species(&result, all_flowers)) {
total++;
}
}
}
}
}
return total;
}
int main(void)
{
int i, j, result;
Field field;
scanf("%d", &field.width);
field.NW_flowers = malloc(field.width * field.width * sizeof(*field.NW_flowers));
field.empty_alphabet = malloc(sizeof(*field.empty_alphabet));
reset_alphabet(field.empty_alphabet);
create_field(&field);
/*
for (i = 0; i < field.width; i++) {
for (j = 0; j < field.width; j++) {
print_alphabet(get_at(&field, i, j));
}
printf("\n");
}
*/
result = get_number_of_possible_fences(&field);
printf("%d\n", result);
return 0;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
9

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1584665

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1077746

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)