Задача 2
Задача 3
Задача 4
Задача 5
Здравейте,
Ето че стигнахме до битовата задача.
Условието на задачата може да изтеглите от тук: 5. Neurons.doc
Тази задача я правих 2 пъти from scratch.
Питате се защо ли? Ами причината ще я разберете по-надолу.
Първо ми хрумна следния алгоритъм:
Обръщам всички 0 на 1 и обратно. След което изчиствам рекурсивно всички 1 които се допират до стените, техните съседи и така докато стигна до 0 (достигнатите нули са точно ограждането на някой neuron, които от 1 са станали 0 при обръщането, и по този начин вътрешните не ги докосвам.
Логиката е чудесна и работи за примерите.
Ето и кода:
using System;
using System.Collections.Generic;
class NeuronMapping
{
static void ClearAtPosition(List input, int x, int y)
{
if (x >= 0 && x < 32 && y >= 0 && y < input.Count)
{
if ((input[y] & (1 << x)) != 0)
{
input[y] = input[y] & (~((uint)1 << x));
ClearAtPosition(input, x - 1, y);
ClearAtPosition(input, x + 1, y);
ClearAtPosition(input, x, y - 1);
ClearAtPosition(input, x, y + 1);
}
}
}
static void Main()
{
List input = new List();
while (true)
{
string inString = Console.ReadLine();
if (inString == "-1")
{
break;
}
uint number = uint.Parse(inString);
input.Add(~number);
}
for (int x = 0; x < 32; x++)
{
ClearAtPosition(input, x, 0);
ClearAtPosition(input, x, input.Count - 1);
}
for (int y = 0; y < input.Count; y++)
{
ClearAtPosition(input, 0, y);
ClearAtPosition(input, 31, y);
}
foreach (var item in input)
{
Console.WriteLine(item);
}
}
}
Но се оказа че не покрива 100% от тестовете в bgcoder. Един от тях даваше грешен отговор. От тук на сетне започна голямото чудене зато е така.
Чудех се можеше ли да остане поле между neuron-ите което да не изчиствам. Какви ли не мисли ми минаха през главата.
Накрая реших да започна отначало цялата програма с нов алгоритъм. А именно, за всеки ред първо обръщам с побитова операция НЕ (~), след това от двата края всички единици ги правя от 1 на 0 до срещане на 0.
Този алгоритъм ми докара 100%.
Ето и кода:
using System;
using System.Collections.Generic;
class NeuronMapping2
{
static void Main()
{
List input = new List();
while (true)
{
string inString = Console.ReadLine();
if (inString == "-1")
{
break;
}
uint number = uint.Parse(inString);
number = ~number;
for (int i = 0; i < 32; i++)
{
if ((number & (1 << i)) != 0)
{
number = number & (~((uint)1 << i));
}
else
{
break;
}
}
for (int i = 31; i >= 0; i--)
{
if ((number & (1 << i)) != 0)
{
number = number & (~((uint)1 << i));
}
else
{
break;
}
}
input.Add(number);
}
foreach (var item in input)
{
Console.WriteLine(item);
}
}
}
На пръв поглед ползването на "сложната" рекурсия може да е причината. Но аз не мисля така. Във втория алгоритъм има логически бъг въпреки че ми прави 100%.
Нека да разгледаме следния пример:
................................ 0 .....................11....11... 1560 ....................1..1..1..1.. 2340 ...................1....11....1. 4290 ....................1........1.. 2052 .....................1......1... 1032 ......................1....1.... 528 .......................1..1..... 288 ........................11...... 192 ................................ 0Този вход би трябвало да ми даде следния изход, ако правилно съм разбрал условието (не го твърдя, нямам претенции английския да ми е перфектен):
................................ 0 ................................ 0 .....................11....11... 1560 ....................1111..1111.. 3900 .....................11111111... 2040 ......................111111.... 1008 .......................1111..... 480 ........................11...... 192 ................................ 0 ................................ 0И точно това е резултата с първия алгоритъм.
А със втория резултата е:
................................ 0 .......................1111..... 480 .....................11.11.11... 1752 ....................1111..1111.. 3900 .....................11111111... 2040 ......................111111.... 1008 .......................1111..... 480 ........................11...... 192 ................................ 0 ................................ 0Но пък той ми донесе 100%
Хареса ми преживяването имаше емоция, трудности, проблеми за решаване. Удоволствието е невероятно, ако се сблъскаш с трудности и накрая успееш да се справиш.
И благодаря за времето което отделихте да прочетете преживяванията ми по време на изпита.
