需要幫助，這涉及翻轉硬幣編程問題

我試圖解決codechef.com上的翻轉硬幣問題（http://www.codechef.com/problems/FLIPCOIN/）我的代碼是在C中，我在我的機器運行Linux上使用gcc v4.4.3進行測試，並且我的程序適用於提供的示例輸入。但是，在向法官上傳時，我收到「錯誤答案」的消息。在我的程序中，我通過切換位來表示硬幣的翻轉。我認爲我的算法是正確的，我不能提出一個會失敗的情況。以下是我的代碼。任何幫助將非常感激。需要幫助，這涉及翻轉硬幣編程問題

謝謝。

#include <stdio.h> 

long int n=0,temp,number_of_coins,number_of_inputs,bit_mask; 
long int number_of_ones(long int i) //Return the number of bits set 
{ 
    return __builtin_popcountl(i); 
} 
int main(void) 
{ 
    long int ctr,lower,upper,length; 
    int op; 

    scanf("%ld %ld",&number_of_coins,&number_of_inputs); 
    length = number_of_coins-1; 
    for(ctr = 0 ; ctr < number_of_inputs;ctr++) //Main loop 
    { 
     scanf("%d %ld %ld",&op,&lower,&upper); 
     bit_mask = ((1 << length-lower+1)-1) & ~((1 << length-upper)-1); 

     if(op == 0) 
     { 

      n ^= bit_mask ; //Toggle the bits in the range lower to upper 

     } 
     else 
     { 
      temp = n; 
      temp &= bit_mask; 
      printf("%ld\n",number_of_ones(temp)); //Print number of bits set 
     } 


    } 



    return 0; 

}

來源

2010-08-21 raza.sayed

網站是否有可能希望您的程序在打印輸出之前一次接受所有的輸入行？ – Jeff 2010-08-21 23:55:17

你認爲名爲'__builtin_popcountl'的函數是可移植的嗎？ – Borealid 2010-08-21 23:55:57

我認爲那不是這種情況，因爲我已經提交了一些解決方案之前，我沒有事先採取所有輸入。該程序應該從輸入流中讀取並寫入輸出流@Borealid：在線裁判正在使用gcc v4.3.2 。這會導致問題嗎？ – 2010-08-22 00:04:21

由於您使用存儲在long int中的位序列來表示硬幣，因此您的代碼將不能用於超過32個硬幣（或者位於long中的很多位）。該網站指出，雖然可以有多達100000個硬幣。

來源

2010-08-22 00:04:29 interjay

這是對的。您可以手動跟蹤10000位，並且可以使用大量內存，也可以使用鏈接的間隔列表。 – alternative 2010-08-22 00:12:16

@mathepic：「或者你可以使用鏈接列表的間隔」......併成爲像010101010101 – SigTerm 2010-08-22 00:37:16

這樣的序列的巨大內存豬這是一個很好的觀點，但我認爲平均而言，鏈表將佔用更少的內存...不是非常肯定。 – alternative 2010-08-22 13:19:43

CodeChef檢查結果的方法可能存在問題，因爲我也得到了相同的答案。你的代碼沒有問題。

來源

2010-08-21 23:56:59

需要幫助，這涉及翻轉硬幣編程問題

回答

相關問題