Vrijeme: 01:04

Diamonds & Dancefloors #5

Plesni podij oblika je 1000 \times 1000 ploče. Svaka osoba na plesnom podiju zauzima svoj prostor za ples koji je pravokutnik oblika m \times k gdje su m i k proizvoljni za svaku osobu. Kako su ljudi na plesnom podiju solidarni i vole svoj osobni prostor, u svakom retku i svakom stupcu plesnog podija postoji točno jedno 1 \times 1 polje koje niti jedna osoba nije zauzela za svoj prostor za ples.

Koliko najmanje ljudi može biti na plesnom podiju?

The dance floor is a 1000 \times 1000 grid. Each person on the dance floor occupies a dance space in the form of an m \times k rectangle, where m and k can vary for each person. Because the people on the dance floor are considerate and value their personal space, there is exactly one 1 \times 1 square in every row and every column of the dance floor that is not occupied by anyone's dance space.

What is the minimum number of people that can be on the dance floor?