fork(2) download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. class Friend
  5. {
  6.     private readonly int indexInSet;
  7.     private int di;
  8.  
  9.     public int Iset { get => indexInSet; }
  10.     public int Di { get => di; set => di = value; }
  11.  
  12.     public Friend(int i)
  13.     {
  14.         this.indexInSet = i;
  15.     }
  16.     public Friend(int i, int Di)
  17.     {
  18.         this.indexInSet = i;
  19.         this.Di = Di;
  20.     }
  21. }
  22.  
  23. class Program
  24. {
  25.     static int goal;
  26.     static int friends;
  27.     static List<Friend> toConvinceList;
  28.     static List<Friend> conditionFriendsList;
  29.     static int minDi;
  30.  
  31.     private static void ReadSet()
  32.     {
  33.         string[] friendsAndGoal = Console.ReadLine().Split(' ');
  34.         friends = int.Parse(friendsAndGoal[0]);
  35.         goal = int.Parse(friendsAndGoal[1]);
  36.  
  37.         string[] zestawString = Console.ReadLine().Split(' ');
  38.         int[] set = Array.ConvertAll(zestawString, int.Parse);
  39.  
  40.         minDi = Int32.MaxValue;
  41.         toConvinceList = new List<Friend>();
  42.         conditionFriendsList = new List<Friend>();
  43.  
  44.         SeperateSetToLists(ref set);
  45.         Console.WriteLine(CountHowManyMustBeConvinced(ref toConvinceList, ref conditionFriendsList));
  46.     }
  47.  
  48.     private static void SeperateSetToLists(ref int[] set)
  49.     {
  50.         for (int i = 0; i < friends; i++)
  51.         {
  52.             if (set[i] >= i + 1)
  53.             {   //Di zbyt wysokie aby wplacili bez przekonywania
  54.                 toConvinceList.Add(new Friend(i));
  55.             }
  56.             else
  57.             {   //warunkowo moga wplacic
  58.                 conditionFriendsList.Add(new Friend(i, set[i]));
  59.                 if (set[i] < minDi)
  60.                 {
  61.                     minDi = set[i];
  62.                 }
  63.             }
  64.         }
  65.         if (minDi == Int32.MaxValue)
  66.         {
  67.             minDi = 0;
  68.         }
  69.     }
  70.     private static int CountHowManyMustBeConvinced(ref List<Friend> toConvinceList, ref List<Friend> conditionFriendsList)
  71.     {
  72.         int conditionFriendsCounted = conditionFriendsList.Count;
  73.         int convince;
  74.  
  75.         //ilu wstepnie nalezy przekonac sprawdzajac ilu znajomych jest skora wplacic 
  76.         if ((goal - conditionFriendsCounted) > 0) 
  77.         {
  78.             convince = goal - conditionFriendsCounted;                                             
  79.             if (convince == goal)
  80.             {
  81.                 return goal;
  82.             }
  83.         }
  84.         else
  85.             convince = 0;
  86.  
  87.         //jakie jest najmniejsze Di w stosunku do tego ilu chcemy przekonac
  88.         if (minDi > convince)
  89.         {
  90.             if (goal <= minDi)
  91.             {
  92.                 return goal;  //minimalne Di jest za duze, aby znajomi zaczeli wplacac oraz cel jest osiagalny samym wstepnym przekonaniem.
  93.             }
  94.             else
  95.             {
  96.                 convince = minDi;
  97.             }
  98.         }
  99.  
  100.         //liczenie przekonanych;
  101.         int toConvinceListCounted = toConvinceList.Count;
  102.         int beginIndex = 0;
  103.         int sum = 0;
  104.  
  105.         if (convince > 0)
  106.         {
  107.             beginIndex = SearchIndexWithNearestGreaterValue(toConvinceList[convince - 1].Iset, ref conditionFriendsList);
  108.             sum = toConvinceList[convince - 1].Iset + 1;
  109.         }
  110.  
  111.         do
  112.         {
  113.             for (int i = beginIndex; i < conditionFriendsCounted; i++)
  114.             {
  115.                 if (sum >= conditionFriendsList[i].Di) {sum++;}
  116.             }
  117.             if (GoalAchieved(goal, sum)){return convince;}
  118.             beginIndex = SearchIndexWithNearestGreaterValue(toConvinceList[++convince - 1].Iset, ref conditionFriendsList);
  119.             sum = toConvinceList[convince - 1].Iset + 1;
  120.         } while (true);
  121.     }
  122.  
  123.     private static int SearchIndexWithNearestGreaterValue(int index, ref List<Friend> list)
  124.     {
  125.         int min = 0;
  126.         int max = list.Count - 1;
  127.         int mid = max / 2;
  128.         int loopCountTarget = ((int)Math.Round(Math.Log(Convert.ToDouble(max), 2), 0)) + 1;
  129.         int result = max + 1;
  130.  
  131.         for (; loopCountTarget > 0; loopCountTarget--)
  132.         {
  133.             if (list[mid].Iset > index)
  134.             {
  135.                 result = mid;
  136.                 max = mid;
  137.                 mid = (max - (max - min)) / 2;
  138.             }
  139.             else
  140.             {
  141.                 min = mid;
  142.                 mid = min + (max - min) / 2;
  143.             }
  144.         }
  145.  
  146.         return result;
  147.     }
  148.     private static bool GoalAchieved(int goal, int sum)
  149.     {
  150.         return goal <= sum ? true : false;
  151.     }
  152.  
  153.  
  154.     static void Main()
  155.     {
  156.         int countedSets = int.Parse(Console.ReadLine());
  157.         while (countedSets-- > 0)
  158.         {
  159.             ReadSet();
  160.         }
  161.         //Console.ReadLine(); //break
  162.     }
  163.  
  164. }
Success #stdin #stdout 0.02s 16696KB
comments (?)
stdin
copy 
4
8 5
10 5 1 4 2 3 10 4
5 5
3 3 3 3 3
5 2
6 2 5 3 4
5 5
1 2 3 4 5
stdout
copy 
1
3
2
5
https://ideone.com/5zh3MG
language:
C# (gmcs 5.20.1)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!