Back
Close
Employers: discover CodinGame for tech hiring
EVENTS
UPCOMINGPAST
SOLO
PUZZLESCODE GOLFOPTIMIZATION
MULTI
LEADERBOARDSCLASH OF CODEBOT PROGRAMMINGCODING ESCAPE
COMMUNITY
CONTRIBUTIONSLEARNDISCORDFORUMLIVE STREAMS

Kiss the girls

Statement

 Goal

At an HxW rave, Bob wants to kiss as many girls as possible without his odds of catching monkeypox exceeding 40%. The chances of catching monkeypox from any given girl at position (x,y) are min(x, y) / (x^2 + y^2 + 1).
Input
Line 1: H W
Next H lines: The grid values (G indicates a girl), where (0,0) is the upper left corner.
Output
The maximum number of girls Bob can kiss.
Constraints
4 ≤ H,W ≤ 50
Example
Input
6 6
G....G
.G..G.
..GG..
..GG..
.G..G.
G....G
Output
8
Tags
Difficulty
Easy
Test cases
Test 1 Test
Input
6 6 G....G .G..G. ..GG.. ..GG.. .G..G. G....G
Output
8
Validator 1 Validator
Input
7 7 G.....G .G...G. ..G.G.. ...G... ..G.G.. .G...G. G.....G
Output
9
Test 2 Test
Input
8 12 GGGGGGGGGGGG G....GG....G G....GG....G G....GG....G G....GG....G G....GG....G G....GG....G GGGGGGGGGGGG
Output
33
Validator 2 Validator
Input
8 12 GGGGGGGGGGGG G....GG....G G....GG....G GGGGGGGGGGGG GGGGGGGGGGGG G....GG....G G....GG....G GGGGGGGGGGGG
Output
35
Test 3 Test
Input
15 10 .......... .......... .......... .......... ....GG.... ....GG.... ....GG.... ....GG.... ....GG.... ....GG.... ....GG.... ....GG.... .......... .......... ..........
Output
10
Validator 3 Validator
Input
15 10 .......... .......... .......... GGGGGGGGGG .......... .......... GGGGGGGGGG GGGGGGGGGG GGGGGGGGGG .......... .......... GGGGGGGGGG .......... .......... ..........
Output
21
Test 4 Test
Input
20 40 G.GG..G.GGG..G.GG.G.GGGG....GG.GGG...GGG GGGG..GGGGG.GG.G.G.GG.GG..G....G.GG..G.G G...GG.GG.GG.GGGGGGGG.GGGGGGGGGG.GGGGG.. GGGG.GG.GG..G.GGG..GG..GGG.GGG.G.G.GGGG. GG..G.G.GG.GGGGGG...G.G..G.GG.G..GG.G..G G.GGG.....GGGGGG...GGGGG..GG..GGGG.GGGG. GG..GGGGGGGGGG.GGGG.GGGGGGGGGGG.GGGGGGGG G.GG....G.GGG..GGGG.GGGGGGGGGG..G.GG.GGG .G.G.GG..GGGGGGGGGG.G.GG.GGG.GGGGG..GGGG GGGGGGGGGGGG..GGGGGGGGGG....GG.GGGGGGGGG .GGGG.G.GGGGG.GGGGGGG..GG.GG.G...GG.G..G GG..GGGGGGGGG.GG..G.G.G..GGG.GG..GGGGG.. GGGG.G..GGGGGGGGGGG.GG.G.G..GG.GG.G.GGG. GGGG..GGGGGGG.GGG.GGGGG.GGGG.GG.GGG...GG GGGGG.G.G.G...GGGG..G.G.GG...G.G.G.G.G.G GGGGG.GGGGGG.G.G.GGG.GGGG.GGG.GG..GGGGGG GGGGG.GGGGGGG.GGGGGGGG.GG.G.GGGG.G.GGGGG G.G.GGGG..G...GG.GGG.GGGGG.GG.GGGG.GGG.. GGGGGG.GGGG.G..G..GG.GG.GGGG.GGGGG.GG.GG .GGGGGGGGGGGGGGG.G.GGGG...G..GG..GGGGGGG
Output
151
Validator 4 Validator
Input
20 40 ................G.......G.G...G..G.G..G. ...........G..................GG....G..G ...........G..G........G.G.G.....G...... ..GG....................G.G........G.G.. ....G......G.........G.....G..GGG.G..G.. G...G.......G.........G.GG..G.....G.G.G. GG....GG......G........G.............G.G G......GG........G.G...G....G........... G............G......G..GG.......G....... .....G........G.........GG........GGG... G..GG........G.G....G..GGG........GGG... .G..G....G.............................. ..G...G......G.....G.G......G.G.......GG ...G.G...G.......G.................G.... ....GGGG.G.....G.G.G..G....G.G.......... ...G.....G...GG..............G..G......G .G........G.......G...GG...G......GG..G. ..................GGG...G.G............G ...G........G.....GG....G.G..........G.. ....G.........G...G...G...G.............
Output
78
Test 5 Test
Input
50 50 GG..G.....G.........GGGG.G..GG..G..G..G........G.. .......GG..G....G.G....GG.G........GG.....G....... .......G.....G...G....................G.........GG .....GG.....G..........GGG........G..G.G...G.G.G.. .GG.G.............G....G..G.GG....GG...G.....G.... G..G...GGG...G....G.G...G.G.G...G......GG...GG.... ..G.....G.G.G...G.....G..G........................ .........GG.G...G.G.G...G........GGG.....G....G... ..G.G.......G............G.......G...........G.G.. .G.G..G..................G..G...GG...G....GGG..... .......GG...G.....G......G.....G......G....G..G..G .G.......GGG.G....GG..G........G..G.G.......G.G.G. ......G.......G...GG..........G..G..G.........G..G .....G.......G.....G.....G..G........G.GGG..G..... ...G.....G..G.G.....G...........GG...........G..G. ........G..G......G.GG....G...G...G...G.G.GG...... .....G....G.........G.GG....G....G................ G......G.....GG.....G.G......G.....G..G......G.... ........G.GG..GG........G.........GGG.G......G.... ....G..G....G..G..................G..G.GG......... ...G....G...G....G...GG...................G....GGG ..................G......G..GG.....GG.......G..... G.....G.G......GG.G.G...........G................. .G......G.......G.......GGGG..........G.......GG.. ......G...........G..G.G..G.G..........G.GG.G..... ......GG.G.....G..G.GG.........G....G..G....G.GGG. ..G.GG.............G.G.GG....G...G...GG.G.G....... G.......G.G........G....G...G..G..GGGG........G..G ...GG.........GG.....GG..G......GG....G..GG....G.. .....G..G...G.............G....G.GG........G.G.... GG....GG............G..G.G...........GGG....G..... .........G.GG.G.....G..G................G.G....... ..............G..G..............G..G.....G....GG.. ..............G......G......G............G..G..... .GG....G..G...................GG..GG..G..G........ G.G.GG..G..GG...G..G...G.....GG.....GG.G.....G..G. ....GG.....G.............G....G.GGG....G.........G G........G.G...G...G...G.......GG.GG..G.G.G..G...G GG.....G........G.......G..........G...G......GG.. ......GG......G.....G..................G.....G.... .G.G..GG............GG....GG.G....GGG...G...G..... ...G.....G...G....G...............GG..........G..G .........GGG......G.....G.G....G.G................ GG..G.G...G..G.G...................G.............. ......GG.........G.G...G.........GG...G.........GG ........G.....G.G..G..G.....GG.................G.. G.........G..G....G.G..G...G..GG.......G.....G.... G.G...G..G.GG.G.GG...G..........G.G......G..G..... ..........G.....G...G.......G...GG.G....GG....G..G G...G..G...G............G.G.........G..........G..
Output
150
Validator 5 Validator
Input
50 50 G.G.GG.G..GG....G.G..GGGG.G.G.GG...GG.GG.GG..GG... .GG.GGG.G.G..G.GG.GG.GG.GG..GGGGG....G..G.GG.G..GG GG....G.GGGGG.G..........G.G.GGG.G..GG.G.GGGGGG.G. GG.G.....GG..GG..G.G.G....GG..G...GG.....G.GGG.G.G .G.GGG....GGG..GG.G..GGG.G.GGG.GGGG.GGG.G.GGGGGGGG ..G.GGG...GGGGGG..GG....G.GGGG.G...G...G.G..GG.GGG .....G...GGG..GG..GG.GGGG..G.GGG.G....G.GG.GGGG.G. ..GG.GG...G.G.G.G...GG.G.GG.G.G..G...G.G...G...... G...GGG.G.GGGGGGG..GGG.G.GGG....G....GGGGGGG.G.G.. .G.G.G.G....G..G...GG.....G...GG..G.G.GG..G.G..G.G G....G....G..G.G.GG..G.GG....G.GGG.GGGGGG.GGG.GGGG .G.GG.GG..G.GG.G.G.G..GGGGGG..G....G..GGGGG..G..GG GGGGGG....GG.G.GGG.G..GGGG.....GGGGGG..G..GG.GGGG. G.GG.GG.GGGG..GG.GG.G.GGG.G..G.G.......G.GG.GG...G .GGGG.GGG.GG.G.G...G..GG.GG...G..G...GG.GG.G.GG.GG GG.GG.GGGGG..GG.GG.G.....GGG.GGGG......G.GGG...GG. ..GGGGG......G.GG.G..GG..GG.G.G..G....G.G.G.GG.G.G GG..G.G.G...G.G.G...G...GGG.....GG......G.G.G.G.GG .GGG.G.G.GGGG....G...G..GG..G.GG.GG...G..G..G..GG. GG.GG.GG.G..GG...G..G.GGG.G.GG...G..G.GG..GGG..GG. .G..GGGGG..G..G.G.G..G.G.GG.....G.G.G..GGGG...G.GG ..G...G.GGGG.GGG...GG..G.GG..G.GGG.GGGG..G.G.G.GG. ..GGGG..GG.GGG...GG.G..G.GGG.G.G..G.G.GGG.G....GG. ..G.GGGGGGG.GG..GGG.G.G....G...GG.GG...GGG...GGG.. ...G.G.G...G..GG...G.GGG..G...GGGGGG.G...GG...G..G .GGGG.G.GG.....G...G..GG.G..GGG.GGGGGGG........G.. .GGGG...GGGGG.GG.GGGGGGG.G..G.GGG.G.GG.GGG...G.GGG GGG....GGG....G...G.G.G.G....GGGG....GGGG..GGG..GG GGG.GG.G.GG.G.....GG...G.GGGG.GG..G.G..GGGGG.GGGGG GG....GGGGG.GG.G.GGGGGG.GG.G...G.G......GG.GGGGG.G ..G..GG.GG......G.GGG..G......GG...G....G.G.G.GGGG .G..G.GGG.G.....G.G..GGGG...GG..G..G.G...G.G.GGGGG GG.GG.G..GG..G.G..G..G..G.GG..G.GGGG.GG..GGGG.GGG. ..GG......GG.G...G.GGGG..G.GGGGG.G.GG....GG.G..GG. G.G.G..GG..G.GGG....G.GGG..G....GGG.GG.G.GG.GG.GGG G..G..GGG.GGGG.G.GGGGG.GG.GGG.....G..G.GG.....GG.. GG..G...G..G.GGG.GGG.G..GGGGG..GGGGGGG..GG..G.G.GG GGG..GG..G.G.G.G.GG.G.G..GG..GG..G.G..GG..GGG.GGG. .GGGG.G.....G.G..GG....G..GGG...GG.G...GG.G...G..G .G...G.GG.G..G.GGG.GGGG.GGGGGGGG..GG..GGGGG.GGG.G. GGG.GG..G.....GGGGG..GG.G..G.G.G..GGGG.GG.GGGGGG.. ..G....G.G.G.G..G.G..GG.GG..G.G..GG..G.G....G.GGG. ...GG..GG.GGG..G.G.G...GG.GG.GGGGGGGG.GG..G.....G. GG.GG.....G.G....GG.GG.G.GG..GG.GGGG....G..G...G.G GGGG.GGGG.G.G.G..G..G.G.......G.G.G..GG.G...G.GGG. .GG.G....GG.GGGG.G...G..GG.G.GGGGG.G.GGGGG...G.G.G G.G.G.G.G.G.GG..GG.G.GG..GG.G.G.GG.......GG....GG. .G.G.....GGGG..GGG.G..G..G.G.G.G.G....G..G.....GGG ..GG..G..G.GG...G.GGG.G.G...G.G..GG...GGG.G...G..G G.G.G.G.GG..G.G..G.G.GG.GG.G..G..G.GG.......G....G
Output
240
Solution language
Solution
Stub generator input
ABOUT USCAREERSPRIVACYFAQBLOG
ABOUT USCAREERSPRIVACYFAQBLOG

The #1 tech hiring platform

SCREENINGINTERVIEWING
FacebookYouTubeTwitterLinkedIn