SRM 355 Div2

全部Greedyという偏ったセット
結果
Easy(250) 249.53
Medium(550) 471.28
Hard(950) 620.42


Easy
実装するだけ。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Imports Weight=System.Int32
Public Class ValueAddedTax
	Public Function calculateFinalPrice(ByVal product As String, ByVal price As Integer, ByVal food As String()) As Double
		Dim i As Integer,j As Integer
		Dim k As Double=1.18
		For Each t as String in food
			if t=product then k=1.1
		Next
		Return CType(price,double)*k
	End Function
End Class

Medium
最初の連続する一致する数のなかに8がいくつ含まれているか数える。ToString最強。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Imports Weight = System.Int32
Public Class NoEights
    Public Function smallestAmount(ByVal low As Integer, ByVal high As Integer) As Integer
        Dim i As Integer, j As Integer
        Dim a As String = low.ToString("0000000000")
        Dim b As String = high.ToString("0000000000")
        smallestAmount = 0
        For i = 1 To 10
            If Mid(a, i, 1) <> Mid(b, i, 1) Then Exit For
            If Mid(a, i, 1) = "8" Then
                smallestAmount += 1
            End If
        Next
    End Function

End Class

Hard
薄い方を全部使うか、濃い方を全部使うか考える。

Imports Microsoft.VisualBasic
Imports System
Imports System.Collections
Imports System.Collections.Generic
Imports System.Text
Imports System.Math
Imports Weight = System.Int32
'値型の物を入れるのに使う。
Public Structure Pair(Of T1 As IComparable(Of T1), T2 As IComparable(Of T2))
    Implements System.IComparable
    Implements System.IComparable(Of Pair(Of T1, T2))
    Public First As T1, Second As T2
    Public Sub New(ByVal V1 As T1, ByVal V2 As T2)
        First = V1 : Second = V2
    End Sub
    Public Function CompareTo(ByVal tar As Pair(Of T1, T2)) As Integer Implements System.IComparable(Of Pair(Of T1, T2)).CompareTo
        If First.CompareTo(tar.First) > 0 Then Return 1 Else If First.CompareTo(Tar.First) < 0 Then Return -1 Else If Second.CompareTo(Tar.Second) > 0 Then Return 1 Else If Second.CompareTo(Tar.Second) < 0 Then Return -1 Else Return 0
    End Function
    Public Function CompareTo(ByVal tar As Object) As Integer Implements System.IComparable.CompareTo
        If tar.GetType() IsNot Me.GetType() Then Throw New ArgumentException("比較不可能な型です", "tar")
        Return Me.CompareTo(DirectCast(tar, Pair(Of T1, T2)))
    End Function
End Structure
Public Class MixingLiquids
    Public Function howMuch(ByVal percent As Integer(), ByVal amount As Integer(), ByVal need As Integer) As Double
        Dim i As Integer, j As Integer
        Dim per(UBound(amount)) As Pair(Of Integer, Integer)
        For i = 0 To UBound(amount)
            per(i).First = percent(i)
            per(i).Second = amount(i)
        Next
        Dim s As Integer = -1, e As Integer = UBound(amount) + 1
        Array.Sort(per)
        For i = 0 To UBound(amount)
            If per(i).First < need Then s = i
        Next
        For i = UBound(amount) To 0 Step -1
            If per(i).First > need Then e = i
        Next

        Dim nm As Double = 0
        For i = s + 1 To e - 1
            nm += per(i).Second
        Next
        howMuch = nm
        Dim Res1 As Double = 0
        Dim Res2 As Double = 0
        For i = 0 To s
            Res1 += per(i).Second
            Res2 += per(i).Second * per(i).First / 100.0
        Next
        If (Res1 > 0) Then
            For i = e To UBound(amount)
                If ((Res2 + per(i).First * per(i).Second / 100.0) / (Res1 + per(i).Second)) * 100 < need Then
                    Res2 += per(i).First * per(i).Second / 100.0
                    Res1 += per(i).Second
                Else
                    Res1 += (need * Res1 / 100.0 - Res2) / ((per(i).First - need) / 100)
                    howMuch = Max(howMuch, Res1 + nm)
                    Exit For
                End If
            Next
        End If

        Res1 = 0
        Res2 = 0
        For i = e To UBound(amount)
            Res1 += per(i).Second
            Res2 += per(i).Second * per(i).First / 100.0
        Next
        If (Res1 > 0) Then
            For i = s To 0 Step -1
                If ((Res2 + per(i).First * per(i).Second / 100.0) / (Res1 + per(i).Second)) * 100 > need Then
                    Res2 += per(i).First * per(i).Second / 100.0
                    Res1 += per(i).Second
                Else
                    Res1 += (need * Res1 / 100.0 - Res2) / ((per(i).First - need) / 100)
                    howMuch = Max(howMuch, Res1 + nm)
                    Exit For
                End If
            Next
        End If
    End Function

End Class