Official Analysis (C++)

By simulating handshakes for all values of KK, we can find the minimum, maximum, and number of possible values of KK which are valid.

Implementation

Time Complexity: O(N⋅T2)\mathcal{O}(N \cdot T^2)

C++

#include <bits/stdc++.h>
using namespace std;


void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}

Python

import sys


sys.stdin = open("tracing.in", "r")
sys.stdout = open("tracing.out", "w")


n, t = map(int, input().split())


infected = [int(i) for i in input().strip()]
shakes = []

Java

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


public class CowntactTracing {
	static boolean[] cowEndsInfected;
	static int n;
	static int maxT = 250;
	static int maxN = 100;
	static int[] cowX = new int[maxT + 1];
	static int[] cowY = new int[maxT + 1];

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum