[C#] Изпитна задача - Bobi Avokadoto - 6/100 и 100/100


0

Здравейте, тренирах решаването на задачата Bobi Avokadoto от миналата година (линк към условието) , стигнах до някакво решение, което работи на 100% от примерите, но разбира се - класическия проблем - в BGCoder дава само 6/100. Започнах да търся защо, установих защо, но не мога да си обясня каква е логиката да е така. Затова искам мнения, грешно ли е това изписване, защо, и честно ли е една решена задача да не се приема в BGCoder за такова нещо.

В случая на мен ми струваше още 1 час да проуча защо се получават толкова малко точки, което на изпита би коствало много. Поствам двата варианта на кода, като единствената разлика е в това къде се инициализира променливата "uint comb = 0". В първия случай, който дава малките точки, го правя в началото на задачата. Във втория, се инициализира в пърия if statement - и вече отчита 100/100. Не мога да си обясня защо е така. Моля коментирайте.

Ето това е първия вариант на решението, което работи но дава 6/100:
using System; class BobiAvokadoto2 { static void Main(string[] args) { //Input //Reading from the console: uint head = uint.Parse(Console.ReadLine()); uint numbOfCombs = uint.Parse(Console.ReadLine()); //Initialisation if variables: uint superComb = 0; uint combCount = 0; uint comb = 0; for (int i = 0; i < numbOfCombs; i++) { uint input = uint.Parse(Console.ReadLine()); // //Calculation: //Check if comb is compatable: if ((head & input) == 0) { //Counting the numbers of 1`s, representing the Points for the comb: for (int j = 0; j < 32; j++) { comb += (input >> j) & 1; } // Evaluating the best comb if (combCount < comb) { combCount = comb; superComb = input; comb = 0; } } } //Printing the result Console.WriteLine(superComb); } }

А това е втория вариант, с единстваната разлика - по-вътрешно инициализиране на променливата:

using System; class BobiAvokadoto2 { static void Main(string[] args) { //Input //Reading from the console: uint head = uint.Parse(Console.ReadLine()); uint numbOfCombs = uint.Parse(Console.ReadLine()); //Initialisation if variables: uint superComb = 0; uint combCount = 0; for (int i = 0; i < numbOfCombs; i++) { uint input = uint.Parse(Console.ReadLine()); // //Calculation: //Check if comb is compatable: if ((head & input) == 0) { uint comb = 0; //Counting the numbers of 1`s, representing the Points for the comb: for (int j = 0; j < 32; j++) { comb += (input >> j) & 1; } // Evaluating the best comb if (combCount < comb) { combCount = comb; superComb = input; comb = 0; } } } //Printing the result Console.WriteLine(superComb); } }




Отговори



1

Здравей,

Когато инициализираш променливата си comb в обхвата на цикъла, си гарантираш нулирането й при всяко ново броене, както си направил при последния if-statement, combCount < comb. Представи си, че си навъртял за comb стойността 14 (от първия нулев тест), това влиза в if-а (combCount < comb) и оттам combComb ти става 14, comb си го нулираш. След това почваш наново броене - comb става 1, този път обаче не влизаш в if-a, директно минаваш на следващата итерация, но този път comb ти остава с тази стойност 1, която се добавя към сметките ти във for-цикъла - оттук вече почваш да получаваш грешни резултати. Най-полезно в този случай е дебъгването, нищо не остава скрито :). Друга оптимизация на кода е да сложиш една проверка дали input-a ти е по-малък от 0 и да спреш самия цикъл (втория for, където броиш битовете)...така си спестяваш цялото въртене до 32 бит, например по условие ти е дадено 14, което е 1110 и реално цикълът тук не е необходимо да върти до 31 чак - проверката (input >> j) < 0 слагаш в самия for-цикъл след j < 32.

 


от Daniela_Popova (1125 точки)