Advertisement
Filkolev

Emergency Repairs

Feb 27th, 2016
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.41 KB | None | 0 0
  1. namespace Bitwise_Operations
  2. {
  3.     using System;
  4.  
  5.     public class EmergencyRepairs
  6.     {
  7.         public static void Main(string[] args)
  8.         {
  9.             ulong wall = ulong.Parse(Console.ReadLine());
  10.             int emergencyKits = int.Parse(Console.ReadLine());
  11.             int attacksCount = int.Parse(Console.ReadLine());
  12.  
  13.             /* An attack means unsetting a bit at a specified position;
  14.              * there is a formula for that: number &= ~ (1 << p) */
  15.             for (int i = 0; i < attacksCount; i++)
  16.             {
  17.                 int position = int.Parse(Console.ReadLine());
  18.                 wall &= ~(1ul << position);
  19.             }
  20.  
  21.             // Used to keep track of 0s we turned into 1s
  22.             bool previousWasZero = false;
  23.  
  24.             /* Border case, check if first bit (position 0) is part of a hole;
  25.              * 3 is 11 in binary, so we check if both bit 0 and 1 are empty
  26.              * which means bit 0 is part of a hole. We also check if we have
  27.              * repair kits available in order to plug the hole. */
  28.             if ((wall & 3) == 0 && emergencyKits > 0)
  29.             {
  30.                 wall |= 1; // repair it, simply set bit 0 to 1
  31.                 emergencyKits--; // remember to keep track of repair kits
  32.  
  33.                 // since we turned a 0 into 1, when we move on we need to know there used to be a 0 here
  34.                 previousWasZero = true;
  35.             }
  36.  
  37.             // iterate bits from 1 to 62; border cases (bits 0 and 63) are taken care of separately
  38.             for (int position = 1; position < 63; position++)
  39.             {
  40.                 int bit = (int)((wall >> position) & 1); // What's the value of the current bit?
  41.                 if (bit == 1)
  42.                 {
  43.                     // Mark that the 1 we have wasn't a 0 we repaired and move on to next position
  44.                     previousWasZero = false;
  45.                     continue;
  46.                 }
  47.  
  48.                 /* Take the value of the bit we're currently at along with its two neighbors;
  49.                  * 7 is 111 in binary, so this masks out all other bits but the three we care about */
  50.                 int triplet = (int)((wall >> (position - 1)) & 7);
  51.  
  52.                 /* We have a hole if the triplet is something different than 101 in binary (5) or
  53.                  * if it is 101, but the 1 to the right used to be a 0 we repaired. Remember to check
  54.                  * if we have enough repair kits. */
  55.                 if ((triplet != 5 || previousWasZero) && emergencyKits > 0)
  56.                 {
  57.                     wall |= 1ul << position; // repair bit - set it to 1
  58.                     emergencyKits--; // Keep track of repair kits
  59.  
  60.                     // Exit if we don't have any more kits left
  61.                     if (emergencyKits == 0)
  62.                     {
  63.                         break;
  64.                     }
  65.  
  66.                     /* We turned a 0 into 1, we need to save this information in case the
  67.                      * bit to the left is 0 and the one next to it is 1. */
  68.                     previousWasZero = true;
  69.                 }
  70.             }
  71.  
  72.             // Border case - check bit at position 63
  73.             int lastBit = (int)((wall >> 63) & 1);
  74.             if (lastBit == 0 && previousWasZero && emergencyKits > 0)
  75.             {
  76.                 wall |= 1ul << 63;
  77.             }
  78.  
  79.             Console.WriteLine(wall);
  80.         }
  81.     }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement