Test məsələsi haqqında Kliklər
Bu tapşırıqda sizə Kliklər məsələsi üçün həll təklif olunur.
Bu həll, təəssüf ki, Accepted almır, lakin yenə də O(2^N) vaxtında işləyir.
// i - cari zirvə, p - cari zirvələr çoxluğu long long go( int i, long long p ) { if (p == 0) // əgər p çoxluğu boşdursa return 1; counter++; // proqramın iş vaxtı while (((p » i) 1) == 0) // i zirvəsi p çoxluğunda yerləşirmi i++; p ^= 1LL « i; // i zirvəsini p çoxluğundan çıxarmaq if ((p c[i]) == p) // c[i] - i zirvəsi ilə kənarla birləşən // zirvələr çoxluğu return 2 * go(i, p); // p c[i] - p və c[i] çoxluqlarının kəsişməsi return go(i, p) + go(i, p c[i]); } counter = 0; // proqramın iş vaxtını sıfırlayırıq result = go(0, (1LL « n) - 1); // bütün zirvələr çoxluğundan başlayırıq
Sizin tapşırığınız - bu həllin Time Limit-ə sığmayacağı bir test hazırlamaqdır. Proqramın işləmə müddəti counter dəyişəninin dəyəri ilə müəyyən edilir.
Giriş verilənləri
N - qurmalı olduğunuz qrafın zirvələrinin sayı.
Məsələdə cəmi 2 test var.
Birinci test N = 20 ehtiva edir. Bu testdə proqramın sonunda counter dəyişəni ən az 5000 olmalıdır.
İkinci test N = 40 ehtiva edir. Bu testdə proqramın sonunda counter dəyişəni ən az 50000000 olmalıdır.
Çıxış verilənləri
Testi çıxarın. Test Kliklər məsələsinin giriş məlumatları formatına uyğun olmalıdır.