fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // Używamy __int128 do obsługi ogromnych liczb, które mogą powstać przy mnożeniu k * suma
  7. typedef __int128_t int128;
  8.  
  9. int main() {
  10.     // Optymalizacja wejścia/wyjścia
  11.     ios_base::sync_with_stdio(false);
  12.     cin.tie(NULL);
  13.  
  14.     long long n_in, k_in, s_in;
  15.     if (!(cin >> n_in >> k_in >> s_in)) return 0;
  16.  
  17.     int128 n = n_in;
  18.     int128 k = k_in;
  19.     int128 s = s_in;
  20.  
  21.     // Krok 1: Sprawdzenie warunku początkowego
  22.     if (s <= 0) {
  23.         cout << "Julian zgasl..." << endl;
  24.         return 0;
  25.     }
  26.  
  27.     vector<long long> a(n_in);
  28.     int128 min_prefix = 0; // Najniższy punkt w trakcie jednego cyklu (względem startu cyklu)
  29.     int128 current_prefix = 0;
  30.     int128 cycle_sum = 0;
  31.  
  32.     // Wczytujemy dane i analizujemy pierwszy cykl "na sucho" pod kątem statystyk
  33.     // oraz sprawdzamy, czy padniemy już w pierwszym obiegu.
  34.     for (int i = 0; i < n_in; ++i) {
  35.         cin >> a[i];
  36.         current_prefix += a[i];
  37.         if (current_prefix < min_prefix) {
  38.             min_prefix = current_prefix;
  39.         }
  40.  
  41.         // Sprawdzamy czy zginęliśmy w trakcie 1. cyklu (symulacja on-the-fly)
  42.         if (s + current_prefix <= 0) {
  43.             cout << i + 1 << endl;
  44.             return 0;
  45.         }
  46.     }
  47.     cycle_sum = current_prefix;
  48.  
  49.     // Zaktualizuj s po pierwszym pełnym cyklu
  50.     s += cycle_sum;
  51.  
  52.     // Jeśli przetrwaliśmy 1. cykl i suma jest nieujemna, to nigdy nie spadniemy
  53.     // (bo startujemy z wyższego lub równego poziomu)
  54.     if (cycle_sum >= 0) {
  55.         cout << "Nic nas nie powstrzyma!" << endl;
  56.         return 0;
  57.     }
  58.  
  59.     // Pozostało k-1 cykli do wykonania
  60.     int128 cycles_left = k - 1;
  61.     if (cycles_left <= 0) {
  62.         // Jeśli mieliśmy wykonać tylko 1 cykl i go przeżyliśmy
  63.         cout << "Nic nas nie powstrzyma!" << endl;
  64.         return 0;
  65.     }
  66.  
  67.     // Matematyczne wyliczenie ile cykli możemy bezpiecznie pominąć.
  68.     // Szukamy takiego C, że: s + C * cycle_sum + min_prefix > 0
  69.     // A padamy w następnym.
  70.     // Ponieważ cycle_sum jest ujemne, użyjmy wartości dodatniej dla dzielenia:
  71.     int128 drop_per_cycle = -cycle_sum;
  72.  
  73.     // Chcemy przetrwać: s + min_prefix > C * drop_per_cycle
  74.     // Czyli max C = (s + min_prefix - 1) / drop_per_cycle
  75.  
  76.     int128 numerator = s + min_prefix;
  77.  
  78.     // Jeśli numerator <= 0, oznacza to, że padniemy w nadchodzącym cyklu (bez pomijania)
  79.     int128 safe_cycles = 0;
  80.     if (numerator > 0) {
  81.         safe_cycles = (numerator - 1) / drop_per_cycle + 1; 
  82.         // +1 w logice, bo safe_cycles to ile cykli PRZEŻYJEMY. 
  83.         // Ale czekaj, uprośćmy logikę:
  84.         // Obliczamy ile cykli trzeba odjąć od s, żeby (s + min_prefix) stało się <= 0.
  85.         // Szukamy najmniejszego X takiego, że s - X*drop + min <= 0
  86.         // s + min <= X * drop
  87.         // X >= (s + min) / drop
  88.         // X = (s + min + drop - 1) / drop  (sufit z dzielenia)
  89.  
  90.         int128 jumps_needed = (numerator + drop_per_cycle - 1) / drop_per_cycle;
  91.         // jumps_needed to liczba cykli, po których nastąpi zgon.
  92.         // Czyli musimy pominąć (jumps_needed - 1) cykli i wejść do tego ostatniego.
  93.         safe_cycles = jumps_needed - 1;
  94.     } else {
  95.         safe_cycles = 0; // Padniemy w tym cyklu, który właśnie ma nadejść
  96.     }
  97.  
  98.     // Jeśli bezpieczne cykle przekraczają to co nam zostało, to przeżyjemy wszystko
  99.     if (safe_cycles >= cycles_left) {
  100.         cout << "Nic nas nie powstrzyma!" << endl;
  101.         return 0;
  102.     }
  103.  
  104.     // Przeskakujemy bezpieczne cykle
  105.     s += safe_cycles * cycle_sum;
  106.  
  107.     // Symulujemy ten jeden, ostatni cykl, w którym na pewno padniemy
  108.     current_prefix = 0;
  109.     for (int i = 0; i < n_in; ++i) {
  110.         current_prefix += a[i];
  111.         if (s + current_prefix <= 0) {
  112.             cout << i + 1 << endl;
  113.             return 0;
  114.         }
  115.     }
  116.  
  117.     // Teoretycznie ten punkt jest nieosiągalny przy poprawnej matematyce,
  118.     // ale dla bezpieczeństwa:
  119.     cout << "Nic nas nie powstrzyma!" << endl;
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
4 2000 9
-2 2 -7 1
stdout
copy 
3
https://ideone.com/tsbRMU
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!