2018-1B Problem A

Wrong solution

// package, import, etc...

func Round(f float64) float64 {
	intPart := int64(f)
	f -= float64(intPart)
	if f >= 0.5 {
		return float64(intPart + 1)
	} else {
		return float64(intPart)
	}
}

func Abs(f float64) float64 {
	if f < 0 {
		return -f
	} else {
		return f
	}
}

func start() {
  // read T, repeat test() T times...
}

type L struct {
	numVotes               int
	votesRequiredToRoundUp int
}

type Larr []L

func (l Larr) Len() int {
	return len(l)
}

func (l Larr) Less(i int, j int) bool {
	return l[i].votesRequiredToRoundUp < l[j].votesRequiredToRoundUp
}

func (l Larr) Swap(i int, j int) {
	l[i], l[j] = l[j], l[i]
}

func test() {
	var N, l int
	mustReadLineOfInts(&N, &l)
	Cis := mustReadLineOfIntsIntoArray()
	assert(len(Cis) == l)
	larr := make(Larr, l)
	votesLeft := N
	for i := 0; i < l; i++ {
		larr[i].numVotes = Cis[i]
		votesLeft -= larr[i].numVotes
	}
	assert(votesLeft > 0)
	for i := 0; i < l; i++ {
		var nvAdd = sort.Search(votesLeft+2, func(nvAdd int) bool {
			f := float64(larr[i].numVotes+nvAdd) / float64(N)
			return Round(f*100) > (f * 100)
		})
		larr[i].votesRequiredToRoundUp = nvAdd
	}
	sort.Sort(larr)
	for i := 0; i < l; i++ {
		if larr[i].votesRequiredToRoundUp <= votesLeft {
			larr[i].numVotes += larr[i].votesRequiredToRoundUp
			votesLeft -= larr[i].votesRequiredToRoundUp
			larr[i].votesRequiredToRoundUp = 0
		} else {
			break
		}
	}
	for votesLeft > 0 {
		useVotes := sort.Search(votesLeft+2, func(vUse int) bool {
			f := float64(vUse) / float64(N)
			return Round(f*100) > f*100
		})
		if useVotes > votesLeft {
			break
		}
		larr = append(larr, L{numVotes: useVotes})
		votesLeft -= useVotes
	}
	if votesLeft > 0 {
		larr = append(larr, L{numVotes: votesLeft})
	}
	sum := 0
	var realSum float64 = 0
	for i := 0; i < len(larr); i++ {
		f := float64(larr[i].numVotes) / float64(N)
		precentage := int(Round(f * 100))
		sum += precentage
		realSum += f
	}
	assert(Abs(realSum-1) < 1e-7)
	fmt.Fprintf(stdout, "%d\n", sum)
}

// boilerplate omitted...

Solution that only works for the small input

/*

	DOES ANYONE HAVE A PROOF OF THIS APPROACH??? (i.e. maximizing number of languages that rounds up)

*/

// package, import, etc...

func Round(f float64) float64 {
	intPart := int64(f)
	f -= float64(intPart)
	if f >= 0.5 {
		return float64(intPart + 1)
	} else {
		return float64(intPart)
	}
}

func Abs(f float64) float64 {
	if f < 0 {
		return -f
	} else {
		return f
	}
}

func start() {
  // read T, repeat test() T times...
}

type L struct {
	numVotes               int
	votesRequiredToRoundUp int
}

type Larr []L

func (l Larr) Len() int {
	return len(l)
}

func (l Larr) Less(i int, j int) bool {
	return l[i].votesRequiredToRoundUp < l[j].votesRequiredToRoundUp
}

func (l Larr) Swap(i int, j int) {
	l[i], l[j] = l[j], l[i]
}

func test() {
	var N, l int
	mustReadLineOfInts(&N, &l)
	Cis := mustReadLineOfIntsIntoArray()
	assert(len(Cis) == l)
	larr := make(Larr, l)
	votesLeft := N
	for i := 0; i < l; i++ {
		larr[i].numVotes = Cis[i]
		votesLeft -= larr[i].numVotes
		var nvAdd int
		for nvAdd = 0; nvAdd <= N; nvAdd++ {
			f := float64(larr[i].numVotes+nvAdd) / float64(N)
			if f > 1 {
				break
			}
			isRoundUp := Round(f*100) > (f * 100)
			if isRoundUp {
				break
			}
		}
		larr[i].votesRequiredToRoundUp = nvAdd
	}
	debug(fmt.Sprintf("%v", larr))
	assert(votesLeft > 0)
	sort.Sort(larr)
	for i := 0; i < l; i++ {
		if larr[i].votesRequiredToRoundUp <= votesLeft {
			larr[i].numVotes += larr[i].votesRequiredToRoundUp
			votesLeft -= larr[i].votesRequiredToRoundUp
			larr[i].votesRequiredToRoundUp = 0
		} else {
			break
		}
	}
a:
	for votesLeft > 0 {
		useVotes := 0
		for {
			f := float64(useVotes) / float64(N)
			isRoundUp := Round(f*100) > f*100
			if isRoundUp {
				break
			} else {
				useVotes++
				if useVotes > votesLeft {
					break a
				}
			}
		}
		larr = append(larr, L{numVotes: useVotes})
		votesLeft -= useVotes
	}
	if votesLeft > 0 {
		larr = append(larr, L{numVotes: votesLeft})
	}
	sum := 0
	var realSum float64 = 0
	for i := 0; i < len(larr); i++ {
		f := float64(larr[i].numVotes) / float64(N)
		percentage := int(Round(f * 100))
		sum += percentage
		realSum += f
	}
	assert(Abs(realSum-1) < 1e-7)
	fmt.Fprintf(stdout, "%d\n", sum)
}

// boilerplate omitted...

Sample test cases given in question

4
3 2
1 1
10 3
1 3 2
6 2
3 1
9 8
1 1 1 1 1 1 1 1