Super Paintball [Aram Shatakhtsyan, 2007]

The cows have purchased a Super Paintball Deluxe game set from Tycow, the cow-toy manufacturer. Bessie, knowing you can help, has partitioned the pasture into a set of N x N unit squares (1 <= N <= 100) and compiled a list of the K (1 <= K <= 100,000) locations (1 <= R_i <= N; 1 <= C_i <= N) of every one of her opponents in the Paintball game. This paintball game features a paintball gun that can shoot paintballs in any of eight directions: north, south, east, west, and the diagonals that split those directions exactly (northeast, southeast, northwest, southwest). Bessie wants you to tell her the total number of squares she can occupy and still be able to shoot all of her opponents (she can even shoot them if she shares the same square as they occupy!). PROBLEM NAME: paint2 INPUT FORMAT: * Line 1: Two space-separated integers: N and K * Lines 2..K+1: Line i+1 describes cow i's location with two space-separated integers: R_i and C_i SAMPLE INPUT (file paint2.in): 4 3 2 1 2 3 4 1 INPUT DETAILS: The pasture has 4 rows and 4 columns. Bessie needs to shoot cows at (2,1), (2,3), and (4,1): . . . . C . C . . . . . <--- Cow locations C . . . OUTPUT FORMAT: * Line 1: A single integer that tells how many different locations Bessie may occupy if she is to be able to shoot any cow according to the shooting rules. SAMPLE OUTPUT (file paint2.out): 5 OUTPUT DETAILS: Bessie can occupy any of these cells: (2,1), (2,3), (3,2), (4,1), and (4,3). The diagram below notates possibly shared spaces by '*': . . . . . . . . B . B . ---\ * . * . . B . . ---/ . B . . B . B . * . B . Potential Bessie Bessie & Cows Locations
ქართული თარგმანი არ არის დამატებული

paint2

This tasks asks you to count the number of locations in a grid who have either horizontal, vertical, or diagonal access to all of a list of input locations. Folks wonder why the input dataset isn't a lot larger (i.e., more cows), but if you do the math, the most cows you can ever have is just under 4*N (rows, columns, and two diagonals of cows surrounding a shooter). How to solve it? Iterate through each location and ask if it has 'access' to each of the input locations. N is never very large (and even if it was millions, 4N is never very large for a total number of operations). USA's Stephen Carlson wrote a Java solution: import java.io.*; import java.util.*; public class paint2 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new FileReader("paint2.in")); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("paint2.out"))); StringTokenizer str = new StringTokenizer(br.readLine()); int N = Integer.parseInt(str.nextToken()); int K = Integer.parseInt(str.nextToken()); Position[] loc = new Position[K]; for (int i = 0; i < K; i++) { str = new StringTokenizer(br.readLine()); loc[i] = new Position(Integer.parseInt(str.nextToken()) - 1, Integer.parseInt(str.nextToken()) - 1); } int x = 0, y = 0; int possibles = 0; boolean ok; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ok = true; for (int k = 0; k < K; k++) { x = loc[k].x; y = loc[k].y; if (i != x && j != y && Math.abs(i-x) != Math.abs(j-y)) { ok = false; break; } } if (ok) possibles++; } } out.println(possibles); out.close(); } } class Position { public int x; public int y; public Position() { x = y = 0; } public Position(int ax, int ay) { x = ax; y = ay; } } China's Mengyu Zhou wrote an extremely compact C solution (and it could even be shorter at the cost of some readability in the input stages). He used a bit cleverer set of calculations to compute -- during input -- where the shooter might be. #include <cstdio> int n, m, x, y, h[100], v[100], l[200], r[200], s[100][100], ans; int main() { freopen ("paint2.in","r",stdin); freopen("paint2.out","w",stdout); scanf ("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf ("%d%d", &x, &y); x--; y--; h[x]++; v[y]++; l[y-x+n-1]++; r[x+y]++; s[x][y]++; } for (x = 0; x < n; x++) for (y = 0; y < n; y++) if (h[x] + v[y] + l[y-x+n-1] + r[x+y] - 3*s[x][y] == m) ans++; printf ("%d\n", ans); return 0; } Egypt's Mohamed Abd El-Wahab adds this: Actually you don't need to count the number of cows. The only thing you need is to count the number of cells occupied by cows which is less than 10,000 (100x100). By precomputing the number of occupied cells in each row and column and diagonal you can find an O(n2) solution which is 10,000 even if the number of cows are more than 100,000. Here is solution for it. #include <iostream> using namespace std; int ncow[200][200],row[200],col[200],d1[300],d2[300],n,k,coun; int main() { freopen("paint2.in","rt",stdin); freopen("paint2.out","wt",stdout); cin >>n>> k; for(int i=0; i<k; i++) { int r, c; cin >> r >> c; if(ncow[--r][--c]) continue; coun++; ncow[r][c]++; col[c]++; row[r]++; d1[r+c]++; d2[r-c+100]++; } int res=0; for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (row[i]+col[j]+d1[i+j]+d2[i-j+100]-3*ncow[i][j]==coun) res++; cout << res<< endl; return 0;

USA's Stephen Carlson wrote a Java solution:

import java.io.*;
import java.util.*;

public class paint2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("paint2.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("paint2.out")));
        StringTokenizer str = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(str.nextToken());
        int K = Integer.parseInt(str.nextToken());
        Position[] loc = new Position[K];
        for (int i = 0; i < K; i++) {
            str = new StringTokenizer(br.readLine());
            loc[i] = new Position(Integer.parseInt(str.nextToken()) - 1,
                Integer.parseInt(str.nextToken()) - 1);
        }
        int x = 0, y = 0;
        int possibles = 0;
        boolean ok;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ok = true;
                for (int k = 0; k < K; k++) {
                    x = loc[k].x;
                    y = loc[k].y;
                    if (i != x && j != y && Math.abs(i-x) !=
Math.abs(j-y)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) possibles++;
            }
        }
        out.println(possibles);
        out.close();
    }
}

class Position {
    public int x;
    public int y;
    public Position() { x = y = 0; }
    public Position(int ax, int ay) { x = ax; y = ay; }
}

China's Mengyu Zhou wrote an extremely compact C solution

#include <cstdio>

int n, m, x, y, h[100], v[100], l[200], r[200], s[100][100], ans;

int main() {
    freopen ("paint2.in","r",stdin);
    freopen("paint2.out","w",stdout);
    scanf ("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf ("%d%d", &x, &y);
        x--; y--;
        h[x]++; v[y]++;
        l[y-x+n-1]++;
        r[x+y]++;
        s[x][y]++;
    }
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            if (h[x] + v[y] + l[y-x+n-1] + r[x+y] - 3*s[x][y] == m)
                ans++;
    printf ("%d\n", ans);
    return 0;
}

Egypt's Mohamed Abd El-Wahab adds this

#include <iostream>
using namespace std;

int ncow[200][200],row[200],col[200],d1[300],d2[300],n,k,coun;
int main() {
    freopen("paint2.in","rt",stdin);
    freopen("paint2.out","wt",stdout);
    cin >>n>> k;
    for(int i=0; i<k; i++) {
        int r, c;
        cin >> r >> c;
        if(ncow[--r][--c])
            continue;
        coun++;
        ncow[r][c]++;
        col[c]++;
        row[r]++;
        d1[r+c]++;
        d2[r-c+100]++;      
    }
    int res=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if (row[i]+col[j]+d1[i+j]+d2[i-j+100]-3*ncow[i][j]==coun)
                res++;
    cout << res<< endl;
    return 0;
}