Bits and Bitmask

Эхлээд битийн үйлдлүүдийн талаар товчхоон тайлбарлая. Хоёртын үйлдлүүд болох (& and), (| or), (~ not), (^ xor) нь дараахь үнэний хүснэгтэд тулгуурлаж хариуг гаргадаг.

Өгөгдсөн тоонуудын хувьд хоёртын үйлдэл хийнэ гэдэг маань тухайн тоонуудын хоёртын бичиглэл дахь ижил байранд байгаа бит (0, 1) болгонд үйлдэл хийж шинэ битийг гаргахыг хэлэх юм. Жишээ нь A=10, B=12 гэсэн хоёр тоонд битийн үйлдлүүд хийж үзье. Энэ тохиолдолд А тооны хоёртын бичиглэл = 1010, B тооны хоёртын бичиглэл=1100 юм.

• A & B = 1000 = 8
  
• A | B = 1110 = 13
  
• A ^ B = 0110 = 5

Өөр нэг чухал үйлдэл бол бит шилжүүлэлт <<, >> юм. a << b энэ үйлдэл нь a-н хоёртын бичиглэл дахь бүх битүүдийг зүүн тийш b удаа шилжүүлэх юм. a>>b гэвэл эсрэгээрээ a-н бүх битүүдийг баруун тийш b удаа шилжүүлэх юм. Шилжүүлсний дараах хуучин оронг 0 болгоно. Жишээ нь: 3<<1 гэвэл хариу 6 болно( 3 = 11_2, 3<<1 = 110₂ = 6). Хэрэв бит шилжүүлэлтийн үйлдэлийг сайн ажиглах юм бол a << b энэ нь a-г 2^b-ээр үржүүлсэнтэй тэнцүү a >> b нь a-г 2^b-д хуваасантай тэнцүү. Энэ үйлдэлийг ихэвчлэн өгөгдсөн тооны тодорхой байрлалд байгаа бит-д хандахад хэрэглэдэг юм. Жишээ нь С тооны хоёртын бичиглэлийн b-р бит нь 1 мөнүү гэдэгийг шалгая гэвэл if( C&(1 << b) ) [битийг дугаарлахдаа зүүн талаас нь дугаарладаг!].
За одоо bitmask-н талаар тайлбарлая.
Бидэнд өгөгдсөн олонлогийн бүх дэд олонлогийг байгуул гэсэн бодлого өгөдсөн байг. N элементтэй олонлогийн бүх дэд олонлог 2^N ширхэг байдаг. Тэгвэл яаж дэд олонлогуудаа байгуулах вэ? Тайлбарлахын тулд бодлогоо илүү энгийн болгоё.
Танд алим, жүрж, киви гэсэн гурван жимс байг. Тэгвэл жимснүүдээ хэдэн янзаар сонгож авч болох вэ?
Бодолт:
Жимс бүрийг нэг бит тоо гэж үзээд дэд олонлогоо үүсгэхдээ тухайн жимсийг сонгосон бол 1, сонгоогүй бол 0-ээр тэмдэглэе. Жишээ нь эхний удаад
ямар ч жимс сонгохгүй байвал 000,
зөвхөн киви сонговол 001,
зөвхөн жүрж сонговол 010,
зөвхөн алим сонговол 100,
алим киви сонговол 101, ийм сонголт нийтдээ 2^3 ширхэг байгаа. Хэрэв сайн ажиглавал 0 - 2³-1 тоо бүр нэг сонголтыг(дэд олонлогийг) илэрхийлж байна.
0 - 000
1 - 001
2 - 010
3 - 011
4 - 100
5 - 101
6 - 110
7 - 111
Дээрх тайлбараас бодолт тодорхой болсон байх гэж бодож байна.

За тэгээд bitmask гэж ерөнхийдөө дээрх аргыг хэлнэ. Bitmask-н хувьд хугацааны үнэлгээ O(2^N) болохоор үнэхээр битмаск мөнүү бишүү гэдэгийг сайн бодож бодоорой.

me

someday

ACM ICPC Regional Dalian 2011

9 сарын 23-25ны хооронд БНХАУ-н Далиан хотноо ACM ICPC бүсийн тэмцээн амжилттай болж өнгөрлөө. Уг тэмцээнд Хонгор, Мөнх-Очир, Баасанбат нарын бүрэлдэхүүнтэй S.M.C.S баг Монгол улсаа (блогоо :P) төлөөлөн оролцоод ирлээ. Манай баг 2009 онд Монгол улсын анхны хүрэл медал, 2010 онд амжилтаа бататган дахин хүрэл медал хүртээд байсан билээ.

9.23:

Бид Бээжин хотоос 12 цаг галт тэргээр явсаар 9.23-ны өглөө Далиан хотод ирлээ. Ингээд тэндээсээ шууд бүртгэлдээ очиж тэмцээний билэгдэл болох футболкоо авцгаалаа. Уг өдрөө тэр хавиараа жаахан танилцсан байдалтай л өнгөрүүллээ.

9.24:

Энэ өдөр бол дасгал тэмцээний өдөр. Дасгал тэмцээний гол зорилго нь систем болон компьютер, эдитор гэх зүйлүүдтэйгээ танилцах зорилготой өдөр юм. Гэхдээ уг өдөр сайн орвол сэтгэл зүйн хувьд дээшлэх байх гэж бодож байлаа. Гэтэл санаснаас хамаагүй тааруу орлоо :(.

9.25:

Жинхэнэ тэмцээний өдөр. Өмнөх дасгал дээр сайн ороогүй учир жаахан эмээж байсан. За тэмцээн эхэллээ.
A-J хүртэл дугаарлагдсан 10 бодлого. Олон бодлогоо хувааж аваад уншиж байх хооронд эхний баг D бодлого дээр AC авлаа. Хамт уншихад үнэхээр хялбархан simulation төрлийн бодлого байсан. Кодоо бичээд submit хийлээ, хариу ирээгүй байхад буруу гэдгээ шууд мэдэв - freopen :). Тэнэг froepen-оо хаагаад явуултал мэдээж AC кк.
Дараагийн бодлогоо хайж байтал E бодлогыг бас л өөр баг AC авчихлаа. Жаахан бодсоны эцэст DP бодолтыг олов. Бичээд явуултал AC. Board хартал 16 хавьцаа явж байна, бөөн баяр .....
Хялбар бодлого хайж нэлээд л удлаа. Гэтэл I бодлогыг E-с ч олон хүн бодсон байх юм. Нэг л барьцгүй эвгүй бодлого байв. Тэгээд G бодлогыг уншихад болмоор санагдаад нэлээд хурдан санаа олохыг оролдсон, эцэст нь санаагаа ч оллоо. Гэхдээ бодлогууд хугацааны хязгаарлалтууд тодорхойгүй болохоор TLE авахаас айж байсан ч бичихээр шийдээд бичлээ. Жишээ тестүүдийг давж байна, өөрсдөө үүсгэсэн tricky тестүүдийг ч давж байна. Submit хийлээ, AC :).
Бодлого хайсаар, I дээр гацсаар. Гэтэл C бодлогыг 2 баг бодсон мөртлөө болмоор санагдаад бодоод бичлээ. Нэлээд удсаны эцэст submit хийхэд WA, бид нэг л юм орхиод байгаа бололтой.
Сүүлийн 1 цаг эхэллээ, 2 цаг зүгээр суучихлаа, байдал эвгүй болж эхэлж байна ккк. Одоо манай эцсийн боломж I гэдгийг мэдэж байсан. I бодлогыг бодоход манайд хэрэгтэй байсан ганц зүйл нь 1^4+2^4+..+n^4 -г O(1)-д олдог томъёо. квадрат зэрэг, куб зэргийг мэдэж байсан ч 4 зэргийг мэддэггүй шүү. Томъёог нь гаргах гэж үзээд ч чадсангүй. n<=10^8 байсан болохоор нэг удаа precomputation хийчихвэл O(1)-д олж чадна. Гэхдээ л memory-д багтсангүй, TLE ч авлаа. 8 минут үлджээ, эцсийн эцсийн эцсийн арга гээд үзлээ. 1..10^8 хүртэл бүх утга биш харин 0-р төгссөн тоонуудыг нь хадгалчихвал ямар ч тоог ихдээ O(10) үйлдэл хийгээд олж чадна. Энэ бодолтоо Submit хийгээд 295 дахь минутанд AC. Хэзээ ч бодлого бодоод ингэж их баярлаж байсангүй кк. Дүнгийн хурал: Манайх мөнгө эсвэл хүрэл медал авах нь ойлгомжтой байсан. Хүрэл медалуудыг дуудсаар, манайх дуудагдсангүй :). Мөнгөн медал дээр S.M.C.S багийг дуудлаа. Ингээд анхны мөнгөн медалыг МУИС-МКС-н S.M.C.S баг хүртлээ.

Тэмцээн - 1

Юуны өмнө тэмцээнд оролцсон хүмүүст баярлалаа. Бас эхний байруудад орсон idiot, tvvv, Adya 3т баяр хүргэе.
Одооноос кодер дээрх тэмцээнүүдийг Тэмцээн тэд гэж нэрлэнээ. хэхэ, гадны сайтуудыг л дагаж байнадаа. Тэмцээний цагийг бас иймэрхүү орой хийвэл яаж байна саналаа үлдээгэрэй. Бодлогуудын хувьд бас л гадны сайтуудаас бодсон бодлогуудаас ишлэж зохиосон, тэстүүдэд бас их цаг гаргаж TRICKY тэстүүд их оруулсан. Ингээд бодлогын анализ хийе.
Эргэлт
Энэ хамгийн амархан бодлого байсан байх. Мөрийн дагуу хэд эргэх баганы дагуу хэд эргэхийг бодож үзсэн бол хариу: min(n*2-2, m*2-1)
35
Мэдээж цөөн сав хэрэглэхийн тулд аль болох 5-н сав ашиглах хэрэгтэй. Хэрэв N тоо 5-д хуваагдахгүй бол ядаж нэг удаа 3-н сав ашиглаж ёстой.
Бага тоо
Шууд хүчээр тоог 1-ээр ихэсгээд бодлогын шаардлагыг хангах тоог гаргаж авж болно. Хэрэв саяас илүү удаа 1-ээр нэмэгдүүлэх үйлдэл хийсэн бол шийдгүй юм. Өөр нэгэн бодолт өгөгдсөн тоон оронгийн тоонуудыг бүх боломжоор сэлгэж бодлогын хариуг гаргаж болно. N<=999999 учир бид хамгийн ихдээ 6! үйлдэл хийгдэх юм.

Тэгш өнцөгт

Энэ бодлогын өгүүлбэрийг их буруу бичсэнүү, хүмүүс ойлгох гэж цагаа их алдсан байх. Энэ бодлого нь codeforces.com дээр бүх боломжийг шалгахаар бодож болохоор өгөгдсөн ба та эндээс харж болно. Харин би хязгаарлалтыг сая болгож бүх боломжийг шалгах боломжгүй болгосон юм. Миний бодолт бол динамик програмчлал ашиглах ба left[i]-ээр тухайн i-р тэгш өнцөгтийн зүүн талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү урттай тэгш өнцөгтийн тоог тэмдэглэнэ. Үүнтэй адилаар right[i]-ээр i-аар хайрцагны баруун талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү өндөртэй тэгш өнцөгтүүдийн тоог тэмдэглэв. Тэгвэл хариу max(left[i]+right[i]) (i=1..n). Бодолт O(N)

Тэгийн тоо

Факториалын сүүлийн 0-үүдийн тоог яаж олдог хүмүүс бол бодох л байсан бодлого. Бодлогын хариунд тооцогдож болох үржвэрийн тэгүүдийн тоо нь min(fac2, fac5) юм. Энд fac2, fac5 нь 2 болон 5ууд тус бүр хэдэн удаа үржвэрт байгааг илэрхийлнэ. Энэ нь бидэнд бодлогыхоо хариуг гаргаж авахад заавал бүх тоог үржүүлэхээс зайлсхийх боломжийг олгох юм. Одоо бодлогоо динамик програмчлал ашиглан хоёр өөр маршрут гаргаж авна. Нэг нь үржвэрт хамгийн бага 2 орсон, нөгөө нь мэдээж хамгийн бага 5 орсон. Тэгвэл хариу нь уг 2 маршрутын бага нь болно. Бодолтыг O(N^2)-аар шийднэ.

Mario on Box
Энэ бодлогыг одоохондоо бичихгүйгээр шийдлээ.

Модтой тоглоё 6

IOI2010-n 2dahi odoriin Traffic Congestion bodlogiig bodloo. tgj bgad nemelt tailbar hiinee. Source-g ni tavichii.

//Task: IOI2010_2_2
//by Dunno
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
static int N,P[1000000],S[1000000],D[1000000];
int n;
vector<int> v[1000000];
int prev[1000000];
int col[1000000];
int sum;
int *p;

int go(int x) {
    int ans = p[x];
    int m = 0;
    for (int i = 0; i < (int) v[x].size(); i++) {
       int u = v[x][i];
       if (u == prev[x])
          continue;
       prev[u] = x;
       int tmp = go(u);
       m = max(m, tmp);
       ans += tmp;
    }
    m = max(m, sum - ans);
    col[x] = m;
return ans;
}

int LocateCentre(int n, int *p, int *s, int *d) {
    ::n = n;
    ::p = p;
    sum = accumulate(p, p + n, 0); 
    for(int i=0; i<n; i++){
       v[s[i]].push_back(d[i]);
       v[d[i]].push_back(s[i]);
    }

    prev[0] = -1;
    go(0);
    int id = 0;
    int best = col[0];
    for (int i = 1; i < n; i++) {
        if (col[i] < best) {
        best = col[i];
        id = i;
        }
    }

return id;
}
int main(){
   int i;
   freopen("grader.in","r",stdin);
   freopen("grader.out","w",stdout);
   scanf("%d",&N);
   for (i=0;i<N;i++) scanf("%d",&P[i]);
   for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
   int r = LocateCentre(N,P,S,D);
   printf("%d\n",r);
   return 0;
}

let me know about errors, if any

Програмчлалын улсын 21-р олимпиадын бодлогууд

2-р өдрийн 1-р бодлого.

Гурвалжинг судлая

Хугацааны хязгаарлалт: 2 сек

Координатын эх О-цэгийн баруун талд (эерэг талд) ОХ-тэнхлэг дээр бүхэл координаттай С цэг тэмдэглэв. Ингэхэд О цэгээс с-зайтай, С-цэгээс а-зайтай эерэг хагас (ОХ-тэнхлэгээс дээш) хавтгайд орших цор ганц В-цэг олдоно. Үүний дараа та дараах 2 даалгаварыг гүйцэтгэ.

1-рт нь:
ОВ-хэрчим дээр С1, С2, ... , Ск гэсэн ялгаатай цэгүүдийг ОС1, ОС2, ... , ОСк хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Дараа нь мөн ОС-хэрчим дээр В1, В2, ... , Вm гэсэн ялгаатай цэгүүдийг OB1, OB2, ... , OBm хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв. Эцэст нь BC хэрчим дээр A1, A2, ... , An гэсэн ялгаатай цэгүүдийг BA1, BA2, ... , BAn хэрчмүүдийн урт бүхэл тоо байхаар тэмдэглэв.

1-р даалгавар:
CCi, OAj, BBt хэрчмүүд нэг цэгт огтлолцдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= m)

2-рт нь:
1-р даалгавраа гүйцэтгэсний дараа, О-цэгээс зүүн талд (сөрөг талд) ОХ-тэнхлэг дээр D1, D2, ... , Dp гэсэн ялгаатай цэгүүдийг OD1, OD2, ... , ODp хэрчмийн урт бүхэл байхаар авав.

2-р даалгавар:
Ci, Aj, Dt цэгүүд нэг шулуун дээр оршдог байх бүх (i,j,t) гурвалуудыг ол. (1 <= i <= k, 1 <= j <= n, 1 <= t <= p)

Оролт (tr.in)
Оролтын файл 10 мөрөөс тогтоно.
Эхний мөрөнд С цэгийн координат болох "b" гэсэн 10000-аас хэтрэхгүй натурал тоо байна.
2-р мөрөнд B-цэгийг олоход хэрэглэх "c" ба "a" гэсэн 2 натурал тоо хоосон зайгаар тусгаарлагдан өгөгдөнө.
Эдгээр тоонууд мөн 10000-аас хэтрэхгүй. (2 < a,b,c <= 10000)
3-р мөрөнд k-гэсэн натурал тоо байна. (k <= 150)
Дараагийн мөрөнд OC1, OC2, ... , OCk хэрчмүүдийн уртыг илэрхийлэх c1, c2, ... , ck гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ci < c, i=1..k)
5-р мөрөнд m гэсэн натурал тоо байна. (m <= 150)
Дараагийн мөрөнд OB1, OB2, ... , OBm хэрчмүүдийн уртыг илэрхийлэх b1, b2, ... , bm гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (bi < b, i=1..m)
7-р мөрөнд n гэсэн натурал тоо байна. (n <= 150)
Дараагийн мөрөнд BA1, BA2, ... , BAn хэрчмүүдийн уртыг илэрхийлэх a1, a2, ... , an гэсэн ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана. (ai < a, i=1..n)
9-р мөрөнд p-гэсэн натурал тоо байна. (p <= 150)
Эцсийн мөрөнд OD1, OD2, ... , ODp хэрчмүүдийн уртыг илэрхийлэх d1, d2, ... , dp гэсэн 10000-аас хэтрэхгүй ялгаатай натурал тоонууд хоосон зайгаар тусгаарлагдан байрлана.

Гаралт (tr.out)
Мөр бүрт 1-р даалгаврын хариу болох (i, j, t) гурвалуудыг илэрхийлэх i, j, t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудыг хэвлэхдээ i-гийн координатаар өсөхөөр эрэмбэлж гаргана, хэрэв i-нь тэнцүү бол i-координатаар нь өсөхөөр эрэмбэлж гаргана. Жишээ нь: (1,3,2) (2,2,3) (2,3,1) гэсэн дарааллаар хэвлэнэ.
1-р даалгаврын бүх хариуг хэвлэж дууссаны дараа "PART 2" гэсэн тэмдэгт мөр хэвлэнэ. (1-р даалгавар нэг ч хариугүй байсан ч PART 2 гэж хэвлэнэ)
Үүний араас мөр бүрт 2-р даалгаварын хариу болох (i,j,t) гурвалуудыг илэрхийлэх i,j,t гэсэн 3 тоо хоосон зайгаар тусгаарлагдан байрлана. Тус гурвалуудаа хэвлэх дараалал нь өмнөхтэй адил байна.

Жишээ оролт

8
10 12
2
1 5
3
1 5 4
2
7 6
3
2 4 1000

Жишээ гаралт

2 2 3
PART 2

Тайлбар
CC2 = 5, OA2 = 6, BB3 = 4 хэрчмүүд нэг цэгт огтлолцох тул 2 2 3 гэж гаргана.
Ci, Aj, Dt цэгүүд дунд нэг шулуун дээр орших гурвал олдохгүй байна.

Улсын програмчлалын 21-р олимпиадын дүн

Өнгөрсөн амралтын өдрүүдээр буюу 4 сарын 23-24 өдрүүдэд Улсын Програмчлалын 21-р олимпиад КТМС дээр зохиогдож дүнгээ гаргалаа. Ингээд нийлбэр дүнгээр

1. Өсөхбаатар МУИС-МТС - 240
2. Хонгор МУИС-МКС - 210
3. Мөнх-Очир МУИС-МКС - 200
4. Чинбат КТМС - 195
5. Амар КТМС - 185
6. Амгаланбаатар КТМС - 185

Багийн дүнгээр МУИС-МТС 1-р баг түрүүлж шилжин явах цомын эзэд боллоо. Амжилттай оролцсон хүмүүстээ баяр хүргэе!

Програмчлалын Улсын 21-р олимпиадын алдаа

Энэ удаад олимпиадын дүнг танилцуулахаас өмнө алдаануудыг бичихээр шийдлээ.

Эхний өдөр:
Ороод суухад лабораторын компьютерийн бэлтгэл ажил муу байсан. Жишээлбэл анх ороод суухад Deep Freeze програмыг унтраагаагүй байсан, үүнийг мэдэж байсан туршлагатай оюутнууд л хаалгасан. Эндээс үүдэж гарсан хамгийн муу үр дүн нь Дархан хотоос зорьж ирсэн Мөнхбаатарын эхний өдрийн бүх Source устсан. Бид бодолтоо тулгасан ба Мөнхбаатар дор хаяж 130 оноо авах байсан. Энэ бол КтМС-н цэвэр хариуцлагагүй байдал.
Ингээд эхний өдрийн дүн гарахад миний оноо 145 байсан ба 150 авна гэдэгтээ маш итгэлтэй байсан. Өргөдөл бичиж ороод би өөрөө тестийн алдааг олж илрүүлээд комисс хүлээн зөвшөөрч 4 хүүхэд 5 оноо нэмж авсан. Ороогүй байсан бол тэмцээний дүнд том өөрчлөлт орох байсан.

Хоёр дах өдөр:
Мөнхбаатарын бодолтыг сэргээж чадсангүй, ингээд тэдний хариуцлагагүй байдлаас болж бүхэл бүтэн 130 оноо алдаж байр эзлэх ямар ч найдваргүй болсон. Дүн гарлаа, уг нь дор хаяж 100 оноо авна гэсэн итгэлтэй байсан би 40 15 5 оноо авсан байв. 40 оноог бол би хүлээн зөвшөөрнө, 15-г ойлгож болно, 5 оноог огт ойлгосонгүй. Тэд өргөдөл хүлээн авах боломж өгөлгүй хүчээр бүх өргөмжлөлүүдийг бэлдээд бараг хүчээр дүнгийн хурал эхлүүлэв. 15 оноо авсан бодлого тест хэтэрхий сул байснаас Brute Force буюу хамгийн арга барсан аргаар бодсон хүмүүс 50 авч гайхал төрүүлэв.

Тэмцээний дараа Мөнх-Очир бид 2 миний 5 авсан буюу "tr" бодлогын бодолтыг зөв гэдэгт итгэлтэй байсан тул тестүүдийг аваад шалгаж үзтэл ихэнх тест бодлогын нөхцлийг хангаагүй буюу Гурвалжны тэнцэтгэл биш хангахааргүй өгөгдсөн байв. Мэдээж гурвалжин үүсэхгүй бол ямар хариу хэвлэх вэ дээ? Гэтэл зохиогч болон Өсөхбаатар-н бодолтууд хаанаас ч юм хариу олж хэвлээд тэдгээр нь таарсан. Би гурвалжны тэнцэтгэл биш нөхцлийг хангахгүй бол юу ч хэвлэхгүй гэдгийг кодондоо бичсэн. Энэ бодлогоны тест буруу байсан нь хамгийн том алдаа, хэрвээ энэ алдаа байгаагүй бол Би 1-рт байрт орж багаараа дахин цом хүртэх байлаа. Тэд өргөдөл хүлээж авах ёстой байсан, хэрэв хүлээж авсан бол би тэр алдааг дорхноо илрүүлж бүгдийг өөрчлөх байсан.

Бүх юм дууссан болохоор дараа жилийнхдээ л сайн бэлдэе дээ :)

Гэхдээ бид ижилхэн л оролцогчид учраас Өсөхбаатарт баяр хүргэе!

MNPC 2011 - SMCS багийн тэмдэглэл

Би (SMCS - Э.Хонгор) энд багийнхаа MNPC 2011-т хэрхэн оролцсон тухай бичихээр шийдлээ. Юуны өмнө MNPC 2011 нь Мөнх-Очир бид хоёрын хувьд оролцох боломжтой сүүлийн жил байсан болохоор амжилттай оролцохыг хүсч байсан ба санасандаа хүртэл оролцсондоо таатай байна. Мөн багийн уламжлал ёсоор дахин нэг гишүүн маань солигдсон билээ :p. Багийн шинэ гишүүн маань уг блог-н идэвхтэй админ болох Баасанбат юм. Тэмцээний үеэр олон бодлого байсан болохоор хэн яг ямар бодлого оролдож уншсаныг мартчихаж, багийн ажиллагаа байсан гэж ойлгоорой :).

За ингээд тэмцээнээ эхэлье :). Тэмцээн эхлэв 10 бодлого ирлээ. Бодлогыг хувааж аваад уншив аа, тэгтэл J бодлого N тооны эрэмбээрээ голын тоог ол гэнэ. Шууд STL-н sort ашиглаж бичээд явуултал TLE. N<=10^6 бас multicase 10 ширхэг байсан болохоор амжсангүй. Ингээд шууд хаяад A бодлогыг хартал өгөгдсөн тоонуудын нийлбэрийг ол гэнэ. Ингээд явуулаад 6 дахь минутанд AC. Тэгтэл манайхаас өмнө 2 баг AC авсан байв, J-г хэрэггүй оролдлоо :p. C бодлого N-с хэтрэхгүй хуваарьтай бүх зөв энгийн бутархайг эрэмбэлж гаргах бодлого байв, N жижигхэн байсан болохоор шууд бичээд AC (11 минут). Ингээд тэмцээний дүнг хартал маш бага хугацааны зөрүүгээр нэгт орлоо. Амархан бодлого олохын тулд бүх бодлогыг уншиж их цаг авав, тэгээд I бодлогыг уншиж дуусахад жаахан нуугдмал Bipartite Matching байсныг олоод шууд бичээд AC (41 минут). Дүнгээ хартал бас л тэнцчихсэн, хугацаагаараа арай бага болохоор 1т. Board-с ажиглаад B бодлого хялбар байж магадгүй санагдаад B-г Мөнх-Очиртой цуг жаахан бодсоны эцэст шууд томъёог олоод AC авав (64 минут). Дараагийн бодлого - F, уг бодлого өгүүлбэрээ ойлгосны дараа жижигсэн DP байсныг олов, бичиж байх зуураа дүн хартал дахиад л тэнцчихлээ, MTC-н 1-р багтай үнэхээр ширүүн өрсөлдөж байна даа, ингээд F-ээ дуусгаад AC(75 минут). Ингээд 5 бодлоготой болоод 1 оноогоор холдсон ч удалгүй өрсөлдөгч баг маань 5 бодлоготой болж тэнцэв. Бодлогуудаа уншсаар л, амархан бодогдчих бодлого олдолгүй удав. E бодлого MIS 2D(Maximum Interval Sum) -г олох бодлого, Мөнх-Очиртой хамтраад бичиж байтал арай жаахан удаж магадгүй санагдаад дуусгалгүй өөр бодлого харав. Тэгээд Баасанбатын уншиж байсан H-г DP + BFS гэдгийг харлаа. Маш урт өгүүлбэртэй бодлого байсан болохоор Баска-н тусламжтай хурдан ойлгоод бичив. Bug гарсан болохоор гурвуулаа нийлж тестлэж засаад явуулав. Алдаж магадгүй гэсэн айдастай байсан ч AC авлаа (154 минут). Яг энэ үед манайх 7 оноотой өрсөлдөгч 5 оноотой байсан болохоор жаахан тайвширлаа. Юмаа идэх нь идээд усаа уух нь уугаад бие засах нь заслаа. Ороод иртэл нөгөө баг 6 болчихжээ, яарахгүй бол болохгүй нь. Одоо бодох дутуу гурван бодлого нь D, G, J. J бодлогыг яг баталгаатай бодох арга олоогүй ч эцсийн арга гээд нэг арга олчихсон. D бодлогыг анх хараад ямар ч санаа олсонгүй. Brute Force бичээд жижиг тохиолдлоос зүй тогтлыг олов. Гурвуулаа нийлж байгаад томъёо гаргаад явуултал WA. Итгэлгүй байсан болохоор орхив. Тэмцээний дүнд өөрчлөлт ороогүй байсан болохоор өрсөлдөгч баг манайхыг ялахын тулд дор хаяж 2 бодлого нэмж бодох ёстой ба цаг бага үлдсэн байсан болохоор тайван байлаа, гэхдээ хамаагүй тайвширч болохгүйгээ мэдэж байсан болохоор J-г эцсийн аргаараа үзээд AC авав (228 минут). Одоо л тайвширч болохоор боллоо, гэхдээ D-г эцсээ хүртэл оролдсоор байв. Ингээд манай баг дахин түрүүлж хошой аварга боллоо. Бодлогын анализ дээр зохиогч D-н бодолтоо тайлбарлатал томъёо нь яг таарж байсан ба бодолтоо тулгатал маш жижигхэн алдаа байсан ба манай бодолт зөв болж rejudge хийхэд AC авав (208 минут). Ингээд 9 оноотой гэсэн үг, гэхдээ бусад багуудын аль нь ч бодож чадаагүй болохоор ялгаагүй гэж үзээд манай баг 8 оноотой үлдэхээр шийдсэн.

Бодлого Оролдлого Минут
A 1 6
C 1 11
I 1 41
B 1 64
F 1 75
H 1 154
E 1 170
D 1 203
J 6 228

Багийнхандаа баяр хүргэе!

P.S: Удахгүй бүх бодлогын өгүүлбэрийг оруулах болно.

Монголын Үндэсний Програмчлалын III Олимпиад

Монголын их дээд сургуулуудын оюутнуудын багуудын хооронд зохион байгуулагддаг Үндэсний Програмчлалын олимпиад 4.9-нд гурав дахь удаагаа амжилттай болж өндөрлөлөө. Тэмцээний дүнгээс дурдвал

1. МУИС - МКС 1-р баг - 8 оноо
Бүрэлдэхүүн : Хонгор, Мөнх-Очир, Баасанбат
2. МУИС - МТС 1-р баг - 6 оноо
Бүрэлдэхүүн : Өсөхбаатар, Жамсрандорж, Мөнхжаргал
3. МУИС - МТС 2-р баг - 6 оноо
Бүрэлдэхүүн : Хуягбаатар, Чинболд, Дөлгөөн
4. ШУТИС - КТМС 1-р баг - 4 оноо
Бүрэлдэхүүн : Амар, Адъяа, Гансүх
5. МУИС - МКС 2-р баг - 4 оноо
Бүрэлдэхүүн : Ганбат, Гончигдорж, Дөлгөөн
6. ШУТИС - КТМС 2-р баг - 4 оноо
Бүрэлдэхүүн : Баярмагнай, Чинбат, ?

Чигчийхэн ба Чимэд ах

Тавил:
Online-Judge системд оролтын өгөгдлүүд тэст бүр дээр ижилхэн 1 байхад, гаралтын өгөгдлүүдийг тэст бүр дээр ялгаатай буюу 1-ээс N (тэстүүдийн тоо, N < 9) хүртэлх тоонууд байхаар хэвлэ.

Бодолтын санаа:
Шууд тэст дуудах болгонд random-ээр 1-ээс N хүртэлх тоог үүсгээд хэвлэнэ гэвэл 1/2^N хэмжээний магадлалтай болно. Энэ бол боломжгүй шахуу зүйл юм. Иймээс өөр арга олох хэрэгтэй.

Тэст дуудагдах болгонд буюу програм ажиллах болгон өөрчлөгддөг хэдэн зүйл бий. Тэдгээрийн нэг нь цаг хугацаа буюу unixtime. Үүнийг ашиглан бодож болно.
Online-Judge системд i-р тэстийг давсан тохиолдолд i+1 дэхь тэстийг програмд уншуулдаг. Мөн i-р тэстийг шалгаад дууссан бол бараг л шууд i+1 дэхь тэстийг уншуулж эхэлдэг. За энэ хооронд үүсэх хугацааны алдагдлыг хамгийн ихээр бодоход 0.5 секунд гэж үзье. (coder.mn дээр 0.2 секунд байл уу даа?)
1-р тэстийг unixtime-н секундээр T1=X*10+1 дэхь секундэд ажиллуулна гэж үзье. Тэгвэл програм маань гаралтын утгыг (T1 % 10) гэж хэвлэчихээд хугацааг T2=X*10+2 секунд болтол өөр дээрээ delay ажиллуулна. T2=X*10+2 секунд өнгөрөнгүүт програм зогсож, online judge маань дараагийн тэстийг програм руу оруулна. Энэ удаад T2 хугацаа маань хамгийн ихээр бодоход (T2 + 0.5) болж өөрчлөгдөнө. Програм энэ удаад (T2 % 10) гэсэн утгыг хэвлэчихээд дахиад хугацааг T3=X*10+3 секунд болтол delay ажиллуулна. Гэхмэтчилэн хэвлэсээр байгаад бүх тэстийг дуусгана.

Энэ маягаар бодоход шууд нэг удаа бодлогыг илгээгээд ажиллуулах магадлал бага юм. Таны илгээсэн соорс online-judge системд хөрвүүлэгдээд яг ажиллах үед, системийн цаг хугацаа unixtime-н секундээр 10-д хуваахад 1 үлдэгдэл өгж болж байвал бүрэн зөв ажиллаж чадна гэсэн үг.

Тэгэхээр онолын хувьд бол 10 удаа бодолтоо илгээхэд нэг удаад нь бүрэн дүүрэн бодолт хийх магадлалтай ба, хэрвээ та овсгоотой бол шууд нэгхэн илгээгээд удаа unixtime-аар яг 10*X+1 дэхь секундэд програмаа бүрэн зөв ажиллуулах боломжтой юм :)