AccountantChallenge.cs

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;

#region Infrastructure

public static class Ext
{
    public static TSource MaxBy<TSource, TKey>(this IEnumerable<TSource> source,
        Func<TSource, TKey> selector)
    {
        return source.MaxBy(selector, null);
    }

    public static TSource MaxBy<TSource, TKey>(this IEnumerable<TSource> source,
        Func<TSource, TKey> selector, IComparer<TKey> comparer)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");
        comparer = comparer ?? Comparer<TKey>.Default;

        using (var sourceIterator = source.GetEnumerator())
        {
            if (!sourceIterator.MoveNext())
            {
                throw new InvalidOperationException("Sequence contains no elements");
            }
            var max = sourceIterator.Current;
            var maxKey = selector(max);
            while (sourceIterator.MoveNext())
            {
                var candidate = sourceIterator.Current;
                var candidateProjected = selector(candidate);
                if (comparer.Compare(candidateProjected, maxKey) > 0)
                {
                    max = candidate;
                    maxKey = candidateProjected;
                }
            }
            return max;
        }
    }
}

#region model

public class V
{
    public V(int x, int y)
    {
        X = x;
        Y = y;
    }

    public V(double x, double y)
    {
        X = (int) (Math.Round(x));
        Y = (int) (Math.Round(y));
    }

    public static bool operator ==(V left, V right)
    {
        return Equals(left, right);
    }

    public static bool operator !=(V left, V right)
    {
        return !Equals(left, right);
    }

    public static V operator -(V v1, V v2)
    {
        return new V(v1.X - v2.X, v1.Y - v2.Y);
    }

    public static V operator +(V v1, V v2)
    {
        return new V(v1.X + v2.X, v1.Y + v2.Y);
    }

    public V MoveTo(V to, double maxLen)
    {
        var len = Math.Sqrt(to.Dist2(this));
        var k = maxLen/len;
        return len <= maxLen
            ? to
            : new V(X + (to.X - X)*k, Y + (to.Y - Y)*k);
    }

    public double Len
    {
        get { return Math.Sqrt(X*X + Y*Y); }
    }

    public int Len2
    {
        get { return X*X + Y*Y; }
    }

    public int Dist2(V v)
    {
        var dx = v.X - X;
        var dy = v.Y - Y;
        return dx*dx + dy*dy;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(this, obj)) return true;
        var other = (V) obj;
        return X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (X*397) ^ Y;
        }
    }

    public override string ToString()
    {
        return $"{X} {Y}";
    }

    public readonly int X, Y;


    public static V operator *(V v, double d)
    {
        return new V(v.X*d, v.Y*d);
    }

    public static V operator *(double d, V v)
    {
        return v*d;
    }
}

public class Obj
{
    public readonly V Loc;

    public Obj(V loc, int id)
    {
        Loc = loc;
        Id = id;
    }

    public int Id;
}

public class Data : Obj
{
    public Data(V loc, int id) : base(loc, id)
    {
    }

    public override string ToString()
    {
        return $"{Id} {Loc}";
    }
}

public class Enemy : Obj
{
    public readonly int Life;
    public V Target;
    public int Dist;

    public Enemy(V loc, int id, int life) : base(loc, id)
    {
        Life = life;
    }


    public override string ToString()
    {
        return $"{Id} {Loc} {Life}";
    }
}

#endregion

class GameState
{
    public readonly int Time;
    public readonly int InitialTotalEnemyHP;
    public readonly int ShotsCount;
    public readonly int Score;
    public readonly int Bonus;
    public readonly bool IsOver = false;

    public GameState(V me, Data[] datas, Enemy[] enemies)
        : this(me, datas, enemies, enemies.Sum(e => e.Life), datas.Length*100, 0, 0, 0)
    {
    }

    public GameState(V me, Data[] datas, Enemy[] enemies, int initialTotalEnemyHp, int score, int bonus, int shotsCount,
        int time, bool isOver = false)
    {
        Time = time;
        Me = me;
        Datas = datas;
        Enemies = enemies;
        InitialTotalEnemyHP = initialTotalEnemyHp;
        Score = score;
        Bonus = bonus;
        ShotsCount = shotsCount;
        IsOver = isOver;
    }

    public readonly V Me;
    public readonly Data[] Datas;
    public readonly Enemy[] Enemies;

    public override string ToString()
    {
        var sb = new StringBuilder();
        sb.AppendLine(Me.X + " " + Me.Y);
        sb.AppendLine(Datas.Length + "");
        foreach (var data in Datas)
            sb.AppendLine(data.ToString());
        sb.AppendLine(Enemies.Length + "");
        foreach (var enemy in Enemies)
            sb.AppendLine(enemy.ToString());
        return sb.ToString();
    }


    public static GameState ParseInput()
    {
        return ParseInput(Console.ReadLine);
    }

    public static GameState ParseInput(Func<string> read)
    {
        var inputs = read().Split(' ');
        int x = int.Parse(inputs[0]);
        int y = int.Parse(inputs[1]);
        V me = new V(x, y);
        int dataCount = int.Parse(read());
        var datas = new List<Data>();
        for (int i = 0; i < dataCount; i++)
        {
            inputs = read().Split(' ');
            int dataId = int.Parse(inputs[0]);
            int dataX = int.Parse(inputs[1]);
            int dataY = int.Parse(inputs[2]);
            datas.Add(new Data(new V(dataX, dataY), dataId));
        }
        int enemyCount = int.Parse(read());
        var enemies = new List<Enemy>();
        for (int i = 0; i < enemyCount; i++)
        {
            inputs = read().Split(' ');
            int enemyId = int.Parse(inputs[0]);
            int enemyX = int.Parse(inputs[1]);
            int enemyY = int.Parse(inputs[2]);
            int enemyLife = int.Parse(inputs[3]);
            enemies.Add(new Enemy(new V(enemyX, enemyY), enemyId, enemyLife));
        }
        return new GameState(me, datas.ToArray(), enemies.ToArray());
    }

    public GameState PredictMoveTo(V dest)
    {
        var state = this;
        while (!state.IsOver && state.Me != dest)
        {
            state = state.PredictNextState(new MoveAction(dest));
        }
        return state;
    }

    public GameState PredictShootEnemyToDeath(int targetId)
    {
        var state = this;
        while (!state.IsOver)
        {
            var enemy = state.Enemies.FirstOrDefault(e => e.Id == targetId);
            if (enemy == null) break;
            state = state.PredictNextState(new ShootAction(targetId));
        }
        return state;
    }

    public GameState PredictNextState(PlayerAction action)
    {
        var state = DoMovements(this, action as MoveAction);
        if (state.IsOver)
            return state;
        if (action is ShootAction)
            state = state.ShootEnemy(((ShootAction) action).Id);
        var newDatas = state.Datas.Where(d => !state.Enemies.Any(e => e.Loc.Equals(d.Loc))).ToArray();
        var datasDestroyedCount = Datas.Length - newDatas.Length;
        var isOver = !state.Enemies.Any() || !newDatas.Any();
        var shotsCount = state.ShotsCount + (action is ShootAction ? 1 : 0);
        var bonus = isOver ? newDatas.Length*Math.Max(0, state.InitialTotalEnemyHP - 3*shotsCount) : 0;
        return new GameState(state.Me, newDatas, state.Enemies, state.InitialTotalEnemyHP,
            state.Score - datasDestroyedCount*100, bonus, shotsCount, state.Time, isOver);
    }

    private GameState DoMovements(GameState state, MoveAction optionalMove)
    {
        var newEnemies = state.Enemies.Select(e => PredictEnemy(e, state.Datas)).ToList();
        var newMe = optionalMove == null ? state.Me : state.Me.MoveTo(optionalMove.Target, 1000);
        var willMeDie = WillMeDie(newMe, newEnemies);
        return new GameState(
            newMe, state.Datas, newEnemies.ToArray(),
            state.InitialTotalEnemyHP, willMeDie ? 0 : state.Score, 0, state.ShotsCount,
            state.Time + 1,
            willMeDie);
    }

    private bool WillMeDie(V me, List<Enemy> enemies)
    {
        return enemies.Any(e => (e.Loc - me).Len <= 2000);
    }

    public static Enemy PredictEnemy(Enemy enemy, Data[] datas)
    {
        var target = datas[0];
        var bestLen2 = int.MaxValue;
        foreach (var data in datas)
        {
            var len2 = data.Loc.Dist2(enemy.Loc);
            if (len2 < bestLen2 || len2 == bestLen2 && data.Id < target.Id)
            {
                target = data;
                bestLen2 = len2;
            }
        }
        var newLoc = enemy.Loc.MoveTo(target.Loc, 500);
        return new Enemy(newLoc, enemy.Id, enemy.Life) { Target = target.Loc, Dist = (int) Math.Sqrt(bestLen2) };
    }

    public GameState ShootEnemy(int enemyId)
    {
        var enemy = Enemies.FirstOrDefault(e => e.Id == enemyId);
        var otherEnemies = Enemies.Where(e => e.Id != enemyId).ToList();
        if (enemy == null)
            return new GameState(Me, Datas, Enemies, InitialTotalEnemyHP, 0, 0, ShotsCount + 1, Time);
        var damage = (int) Math.Round(125000/Math.Pow((Me - enemy.Loc).Len, 1.2));
        var killScore = 0;
        if (enemy.Life > damage)
        {
            otherEnemies.Add(new Enemy(enemy.Loc, enemy.Id, enemy.Life - damage));
        }
        else
            killScore = 10;
        return new GameState(Me, Datas, otherEnemies.ToArray(),
            InitialTotalEnemyHP, Score + killScore,
            Bonus, ShotsCount + 1, Time);
    }

    public GameState IncorrectShoot()
    {
        return new GameState(Me, Datas, Enemies, InitialTotalEnemyHP, 0, 0, ShotsCount + 1, Time);
    }

    public int TotalScore
    {
        get { return Score + Bonus; }
    }
}

public class PlayerAction
{
}

public class MoveAction : PlayerAction
{
    public MoveAction(V target)
    {
        Target = target;
    }

    public V Target;

    public override string ToString() => $"MOVE {Target}";
}

public class ShootAction : PlayerAction
{
    public int Id { get; set; }

    public ShootAction(int id)
    {
        Id = id;
    }

    public override string ToString() => $"SHOOT {Id}";
}

#endregion

class Decision
{
    public static Decision Create(int targetId, GameState movedState, PlayerAction firstAction)
    {
        var finalState = movedState.PredictShootEnemyToDeath(targetId);
        return new Decision(finalState, firstAction, $"{firstAction} Id:{targetId}");
    }

    public static Decision Create(V moveDestination, int targetId, GameState initialState)
    {
        var needMove = moveDestination != null && initialState.Me != moveDestination;
        var movedState = needMove ? initialState.PredictMoveTo(moveDestination) : initialState;
        var needShoot = targetId >= 0;
        var finalState = needShoot ? movedState.PredictShootEnemyToDeath(targetId) : movedState;
        var action = needMove
            ? (PlayerAction) new MoveAction(moveDestination)
            : needShoot
                ? (PlayerAction) new ShootAction(targetId)
                : new MoveAction(initialState.Me);
        return new Decision(finalState, action, $"{moveDestination} Id:{targetId}");
    }

    public Decision(GameState finalState, PlayerAction action, string description)
    {
        FinalState = finalState;
        Action = action;
        this.description = description;
        if (FinalState.IsOver)
        {
            Cost = FinalState.TotalScore == 0 ? int.MinValue : FinalState.TotalScore;
        }
        else
        {
            DistCost = AvDistCost();
            Cost = FinalState.Datas.Length*50 - FinalState.Time - FinalState.ShotsCount;
        }
    }

    public override string ToString()
    {
        return $"{description} C:{Cost} DC:{DistCost}";
    }

    private int AvDistCost()
    {
        if (FinalState.Enemies.Length == 0)
            return 100;
        if (FinalState.Datas.Length == 0)
            return 0;
        return (int) FinalState.Enemies.Average(e => e.Dist);
    }

    public readonly double Cost;
    public readonly int DistCost;

    public readonly GameState FinalState;
    public readonly PlayerAction Action;
    private readonly string description;
}

class Player
{
    static void Main(string[] args)
    {
        var player = new Player();
        while (true)
        {
            var state = GameState.ParseInput();
            var action = player.Move(state);
            Console.WriteLine(action);
        }
        // ReSharper disable once FunctionNeverReturns
    }

    public Decision SearchForDecision(GameState state, int depth, DateTime start)
    {
        if (state.IsOver) return new Decision(state, new MoveAction(state.Me), "stay");
        var allDs = CreateDecisions(state);
        if (DateTime.Now - start > TimeSpan.FromMilliseconds(60)) return allDs.First();
        var ds = allDs.OrderByDescending(d => d.Cost);
        if (depth <= 0) return ds.First();
        else
        {
            //ds.ToList().ForEach(Console.Error.WriteLine);
            return ds.MaxBy(d => SearchForDecision(d.FinalState, depth - 1, start).Cost);
        }
    }

    public PlayerAction Move(GameState state)
    {
        var bestDecision = SearchForDecision(state, state.Enemies.Length + state.Datas.Length > 10 ? 0 : 1, DateTime.Now);
        if (bestDecision.FinalState.TotalScore == 0)
            bestDecision = RunAwayDecisions(state).MaxBy(d => d.Cost);
        Console.Error.WriteLine("Decision " + bestDecision);
        return bestDecision.Action;
    }

    private IEnumerable<Decision> CreateDecisions(GameState state)
    {
        foreach (var enemy in state.Enemies)
            yield return Decision.Create(null, enemy.Id, state);
        var me = state.Me;

        var radius = 20000/Math.Max(1, state.Enemies.Length);
        var left = Math.Max(1, me.X - radius);
        var right = Math.Min(16000, me.X + radius);
        var top = Math.Max(1, me.Y - radius);
        var bottom = Math.Min(9000, me.Y + radius);
        for (int x = left; x <= right; x += 1000)
            for (int y = top; y < bottom; y += 1000)
            {
                if (me.X != x || me.Y != y)
                {
                    var moveDestination = new V(x, y);
                    var movedState = state.PredictMoveTo(moveDestination);
                    var action = new MoveAction(moveDestination);
                    foreach (var enemy in state.Enemies)
                    {
                        yield return Decision.Create(enemy.Id, movedState, action);
                    }
                }
            }
    }

    private static IEnumerable<Decision> RunAwayDecisions(GameState state)
    {
        for (int x = Math.Max(0, state.Me.X - 600); x < Math.Min(16000, state.Me.X + 600); x += 200)
            for (int y = Math.Max(0, state.Me.Y - 600); y < Math.Min(9000, state.Me.Y + 600); y += 200)
                if (state.Me.X != x || state.Me.Y != y)
                    yield return Decision.Create(new V(x, y), -1, state);
    }
}