SRM 478

Division 1: Khongor, Chamka
Division 2: XaCaHaa, lmo0731, gmunkhbaatarmn, ChNbLd, nursoltan_h, almabek

Дээрх өнгөнүүд нь оролцсоны дараах өнгө гэдгийг анхаарна уу.


Цөөхүүлээ орох шивдээ.

Div 1-Easy/Div 2-Medium :

Өгүүлбэр: Тоон шулуун дээр туулай x цэг дээр байрлаж байна. Тэр одоо байгаа байрнаасаа (4*x+3) эсвэл (8*x+7) цэг рүү үсэрч чадах ба дээд тал нь 100000 удаа үсэрч чадна. Тоон шулууны (10^9+7)-д хуваагддаг цэг бүр дээр лууван байгаа бол хамгийн цөөндөө хэдэн удаа үсрээд лууван авч чадах вэ?

Бодолт: Туулай дээрх хоёр үсрэлтүүдийг ямар ч дарааллаар яаж ч гүйцэтгэсэн эцэст нь 2^n*(x+1)-1 хэлбэрт тавигдах цэг рүү л хүрч чадна (индукцээр батал). Цаашлаад a удаа (4x+3) b удаа (8x+7) үсрэлтийг хийхэд (дараалал хамаагүй) 2^(2a+3b)*(x+1)-1 цэг дээр очно. Дээд тал нь 100000 гэсэн учраас n=2..300000 утгыг авах ба (2^n*(x+1)-1) % 1000000007 = 0 байх хамгийн бага n-г олоод ceil(n/3)-г буцаавал хариу болно. (11 минут 26 секунд).

Code:
#define m 1000000007
class CarrotJumping
{
public:
int theJump(int x)
{
int a=(2*x+1)%m;
for (int n=2;n<=300000;n++){ a=(a*2+1)%m; if (a==0) return (n+2)/3; } return -1; } };

Challenge Phase: Онц юм болсонгүй :).

System testing Phase: Easy даваад 61-р өслөө. 1848(Max)+61=1909(Max) :D.

Div 2-Hard: (for practice)

Эхлээд бүх subset-g байгуулъя. Тэгээд ямар нэгэн subset-н хувьд xi-р улаан алимны тоог, yi-р ногоон алимны тоог тэмдэглэе. Тэгвэл хариу маань (x1/(x1+y1)+x2/(x2+y2)+x3/(x3+y3)+...)/(2^n-1) болно. Мэдээж энэ бодолт амжихгүй O(2^n). x1/(x1+y1)+... нийлбэрийг яаж хурдан олох талаар бодъё. Эдгээр энгийн бутархайнуудын хүртвэр ба хуваар нь бодлогын нөхцөл ёсоор 1..500 хооронд оршино. f[x][y]-р x/y хэлбэртэй хичнээн бутархай байгааг тэмдэглэвэл уг нийлбэр Summa(f[x][y]*(x/y))[x=1..500,y=1..500] байх нь тодорхой. Бүх f[x][y]-г хялбархан DP ашиглаад O(N*500*500)-д олж чадна.

long long f[501][501];
class RandomAppleEasy
{
public:
double theRed(vector <int> red, vector <int> green)
{
int n=red.size(),r=0,g=0;
for (int i=0;i<n;i++) r+=red[i],g+=green[i];
memset(f,0,sizeof(f));
f[0][0]=1;
for (int i=0;i<n;i++)
for (int x=r;x>=0;x--)
for (int y=g;y>=0;y--)
if (f[x][y]) f[x+red[i]][y+green[i]]+=f[x][y];
double ret=0.0;
for (int x=1;x<=r;x++)
for (int y=1;y<=g;y++)
ret+=f[x][y]*((double)x/(x+y));
return ret/((1LL<<n)-1);
}
};