結果

問題 No.1986 Yummy
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:01:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,681 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 68,360 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:03:20
合計ジャッジ時間 1,425 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // Include the input/output stream library

int main() {
    // Optimize input/output operations for speed.
    // std::ios_base::sync_with_stdio(false) disables synchronization with C standard streams.
    // std::cin.tie(NULL) unties cin from cout, allowing input operations to not wait for output operations.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long N; // Declare N as a long long integer to handle inputs up to 10^9.
    std::cin >> N; // Read the number of candies, N, from standard input.
    
    // The problem asks for the maximum number of delicious candies the first player (P1) can get
    // when both players play optimally. Candies at odd positions (1, 3, ...) are delicious.
    // Players take turns choosing a candy from either end of the row.
    
    // Through analysis of small cases and game dynamics, a pattern emerges based on N modulo 4:
    // Case 1: N is odd.
    // If N = 1, 3, 5, 7, ... candies are D, DOD, DODOD, DODODOD, ...
    // The first and last candies are always delicious (D). P1 starts.
    // P1 takes one D. The remaining ends are O and D (or D and O if P1 took the last candy).
    // P2, playing optimally, will take the available D.
    // The remaining ends become O and O. P1 is forced to take an O.
    // This pattern continues: P1 gets the first D, P2 gets subsequent available D's, P1 gets mostly O's.
    // P1 ends up with exactly 1 delicious candy regardless of N being 4k+1 or 4k+3.
    
    // Case 2: N is even.
    // If N = 2, 4, 6, 8, ... candies are DO, DODO, DODODO, DODODODO, ...
    // The first candy is D, the last candy is O. P1 starts.
    // P1 takes the first candy (D).
    // The remaining ends are O and O. P2 is forced to take an O.
    // The remaining ends become D and O (or O and D). P1 takes the available D.
    // This pattern continues: P1 always gets the D candy when available, P2 always faces O, O ends.
    // P1 ends up taking all the delicious candies. The total number of delicious candies is N/2 when N is even.
    
    // Calculate the remainder of N when divided by 4 to determine which case applies.
    int remainder = N % 4;
    
    // Apply the discovered pattern based on the remainder.
    if (remainder == 1 || remainder == 3) {
        // If N is congruent to 1 or 3 modulo 4 (N is odd), P1 gets 1 delicious candy.
        std::cout << 1 << std::endl;
    } else { // The remainder must be 0 or 2 (N is even).
        // If N is congruent to 0 or 2 modulo 4 (N is even), P1 gets N/2 delicious candies.
        std::cout << N / 2 << std::endl;
    }
    
    return 0; // Indicate successful program execution.
}
0