#ifdef _MSC_VER #ifndef __GNUC__ #pragma warning(disable: 4996) #endif #define main main0 #endif #include <algorithm> #include <iostream> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; const int Max = 1000000+1; ll objetosc[Max+3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; do { fill_n(objetosc + 1, Max, 0); objetosc[Max+1] = -1; // ograniczniki objetosc[Max+2] = 1; bool wynik = false; int n, iMniejsze = 1, iKubek = 1; ll roznicaEnergii = 0;//, pozostalaObjetosc = 0; double objetoscLewa = 0, objetoscPrawa = 0, objetoscKubka = 0; double energiaLewa = 0, energiaPrawa = 0, energiaKubka = 0; double tempKubka, tempLewa, tempPrawa; cin >> n; for(int i = 0, l, a, b; i < n; ++i) { cin >> l >> a >> b; // pozostalaObjetosc += l; objetoscPrawa += l; roznicaEnergii += (a - b) * l; energiaPrawa += a * l; objetosc[a] += l; objetosc[b] -= l; } if(roznicaEnergii != 0) { cout << "NIE" << endl; continue;; } while(!wynik) { while(0 <= objetosc[iMniejsze]) { if(0 < objetosc[iMniejsze]) { ll tmp = objetosc[iMniejsze] * iMniejsze; energiaLewa += tmp; energiaPrawa -= tmp; objetoscLewa += objetosc[iMniejsze]; objetoscPrawa -= objetosc[iMniejsze]; } ++iMniejsze; } if(Max < iMniejsze || objetoscLewa < 1.0e-20) break; iKubek = iMniejsze; objetoscKubka = 0; energiaKubka = 0; while(0 >= objetosc[iKubek]) { if(0 > objetosc[iKubek]) { energiaKubka -= objetosc[iKubek] * iKubek; objetoscKubka -= objetosc[iKubek]; // pozostalaObjetosc += objetosc[iKubek]; } ++iKubek; } if(Max < iKubek) break; tempKubka = energiaKubka / objetoscKubka; tempLewa = energiaLewa / objetoscLewa; tempPrawa = energiaPrawa / objetoscPrawa; double objLewa = (tempKubka - tempPrawa) / (tempLewa - tempPrawa) * objetoscKubka; if(objLewa > objetoscLewa) break; objetoscLewa -= objLewa; objetoscPrawa -= objetoscKubka - objLewa; energiaLewa -= objLewa * tempLewa; energiaPrawa -= (objetoscKubka - objLewa) * tempPrawa; if(energiaPrawa < 1.0e-20)//(pozostalaObjetosc == 0) wynik = true; } cout << (wynik ? "TAK": "NIE") << endl; } while(--t > 0); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #ifdef _MSC_VER #ifndef __GNUC__ #pragma warning(disable: 4996) #endif #define main main0 #endif #include <algorithm> #include <iostream> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; const int Max = 1000000+1; ll objetosc[Max+3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; do { fill_n(objetosc + 1, Max, 0); objetosc[Max+1] = -1; // ograniczniki objetosc[Max+2] = 1; bool wynik = false; int n, iMniejsze = 1, iKubek = 1; ll roznicaEnergii = 0;//, pozostalaObjetosc = 0; double objetoscLewa = 0, objetoscPrawa = 0, objetoscKubka = 0; double energiaLewa = 0, energiaPrawa = 0, energiaKubka = 0; double tempKubka, tempLewa, tempPrawa; cin >> n; for(int i = 0, l, a, b; i < n; ++i) { cin >> l >> a >> b; // pozostalaObjetosc += l; objetoscPrawa += l; roznicaEnergii += (a - b) * l; energiaPrawa += a * l; objetosc[a] += l; objetosc[b] -= l; } if(roznicaEnergii != 0) { cout << "NIE" << endl; continue;; } while(!wynik) { while(0 <= objetosc[iMniejsze]) { if(0 < objetosc[iMniejsze]) { ll tmp = objetosc[iMniejsze] * iMniejsze; energiaLewa += tmp; energiaPrawa -= tmp; objetoscLewa += objetosc[iMniejsze]; objetoscPrawa -= objetosc[iMniejsze]; } ++iMniejsze; } if(Max < iMniejsze || objetoscLewa < 1.0e-20) break; iKubek = iMniejsze; objetoscKubka = 0; energiaKubka = 0; while(0 >= objetosc[iKubek]) { if(0 > objetosc[iKubek]) { energiaKubka -= objetosc[iKubek] * iKubek; objetoscKubka -= objetosc[iKubek]; // pozostalaObjetosc += objetosc[iKubek]; } ++iKubek; } if(Max < iKubek) break; tempKubka = energiaKubka / objetoscKubka; tempLewa = energiaLewa / objetoscLewa; tempPrawa = energiaPrawa / objetoscPrawa; double objLewa = (tempKubka - tempPrawa) / (tempLewa - tempPrawa) * objetoscKubka; if(objLewa > objetoscLewa) break; objetoscLewa -= objLewa; objetoscPrawa -= objetoscKubka - objLewa; energiaLewa -= objLewa * tempLewa; energiaPrawa -= (objetoscKubka - objLewa) * tempPrawa; if(energiaPrawa < 1.0e-20)//(pozostalaObjetosc == 0) wynik = true; } cout << (wynik ? "TAK": "NIE") << endl; } while(--t > 0); return 0; } |