На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Хоча ні, не варто...
Для мене Ви вже нічого не доведете. Інших це не цікавить:)
Поза форумом
А коли буде проходити четвертий тур і хто до нього проходить?
13.02.2011, там же написано.
А можете подсказать, где написано, что четвертый (очный) тур будет проходить 13.02.2011? Что-то не могу найти.
Почему спрашиваю - именно 13.02.2011 в Киеве проходит второй тур городской олимпиады по информатике . Обидно получится.
Відредаговано Зевс (2011-01-25 19:53:23)
Поза форумом
99%, що 12.02.2011.
А можливо, уже й 100%, а я ще не знаю
Поза форумом
неактивним написано:
Завдання 4-го Real-Time туру NetOI-2010 (13/02/10)
Поза форумом
MItornaDOS написав:
неактивним написано:
Завдання 4-го Real-Time туру NetOI-2010 (13/02/10)
Це у минулому році. У цей рік можуть бути деякі зміни.
Поза форумом
Хм... я вважав, що /10 - це просто очепятка
Поза форумом
LeonID написав:
Статистика 3-го туру на 14 годину 25 січня.
Задача Division - 93 варіанти розвязків;
Задача Prize - 105 варіантів розвязків;
Задача Column - 109 варіантів розвязків;
Задача Towns - 67 варіантів розвязків;
Задача Іnstigator - 45 варіантів розвязків.
Статистика 3-го туру на 14 годину 26 січня.
Задача Division - 94 варіанти розвязків;
Задача Prize - 106 варіантів розвязків;
Задача Column - 110 варіантів розвязків;
Задача Towns - 67 варіантів розвязків;
Задача Іnstigator - 45 варіантів розвязків.
Цікаво...
Поза форумом
Ці 3 нові розв'язки перевірятись не будуть
Поза форумом
Division
#include <iostream.h> long long a,b,p[100],k,i; long long divise(long long m, long long n, int r){ if(!r--)return n-m; long long x,y; x=m/p[r];y=n/p[r]; if(x==y)return divise(m,n,r); return divise(m,n,r)-divise(x,y,r); } int main(){ cin >> a >> b >> k; while(i<k)cin >> p[i++]; cout << divise(--a,b,k); return 0; }
Column
#include <iostream.h> int N, n0,n,n2,i,x; int main(){ cin >> N; while(i++<N){ cin >> x; n0+=!x; n2+=2*x-1; n<?=n2; } cout << n+n0; return 0; }
Prize
#include<iostream.h> int N,n,sum[101][101]; //we look for sum[0][0]; int pl[101][101],pl1[10001][2]; //pl[raw][column]=point. pl1[point][0] - raw, pl1[point][1]-column int num[10001],bet[10001],win[10001];//win[i] =1 if i-th point won. int trace[10001]; //to trail back traces positions. int main(){ int x,y; cin >> N; for(int i=1;i<=N;i++){ cin >> x; bet[x]=i; //куда поставил х num[i]=x; //кто поставил на i } x=y=0; while(n*n!=N)n++; // n=sqrt(N); for(int i=1;i<=N;i++){ // "fundamental" square; pl[x][y]=i; // 1 3 6 pl[2][1] = 7; pl1[i][0]=x; // 2 5 8 pl1[7][0] = 2; pl1[i][1]=y; // 4 7 9 pl1[7][1] = 1; x--;y++; if(y==n){y=2+x;x=n-1;} if(x<0){x=y;y=0;} } for(int i=n-1;i>=0;i--){ for(int j=n-1;j>=0;j--){ sum[i][j] = (sum[i][j+1] > sum[i+1][j])? sum[i][j+1] : sum[i+1][j]; trace[pl[i][j]]= (sum[i][j+1] > sum[i+1][j])? pl[i][j+1] : pl[i+1][j]; sum[i][j] += num[pl[i][j]]; } } win[num[1]]=1; x=1; while(x=trace[x])win[num[x]]=1; cout << sum[0][0] << "\n"; for(int i=1;i<=N;i++)if(win[i])cout << i << " "; return 0; }
Towns
#include <iostream.h> const int NMAX=555+1; int N,d[NMAX][NMAX],f[NMAX][NMAX],res; int main(){ cin >> N; for(int i=1;i<N;i++){ for(int j=i+1;j<=N;j++){ cin >> d[i][j]; f[i][j] = f[i-1][j] + d[i-1][i]; f[i][j] <?= f[i-1][i] + d[i-1][j]; if(i==2)f[i][j] = d[1][j] + d[1][2]; } res+=d[i][i+1]; } f[N][N] = f[N-1][N] + d[N-1][N]; cout << res << " " << f[N][N]; return 0; }
Поза форумом
andervish, яка ідея розвязку задачі division?
Поза форумом
Division вирішувати рекурсією - це утопія
Поза форумом
MItornaDOS написав:
Division вирішувати рекурсією - це утопія
Цей розвязок проходить тест 1е+18 на 30 перших дільників за 44 секунди на моєму слабенькому нетбуці(мій розвязок тратить на 10 секунд більше). Окрім цього мій розвязок такий довгий, що дочитавши його до кінця забуваєш що було на початку.
Відредаговано LeonID (2011-01-26 15:23:17)
Поза форумом
Точно! O_o
у мене працює 35 сек, а ця 25
Поза форумом
LeonID написав:
яка ідея розвязку задачі division?
Если ищем кол-во тех, которые не делятся на k указанных простых чисел, то сначала найдем количество таких, которые не делятся на k-1 первых простых divise(a,b,k-1) и из него вычтем все те, которые делятся на последнее простое число p[k-1], но не делятся на все остальные divise(a/p[k-1],b/p[k-1],k-1).
Осталось показать, почему то, что вычитаем равно divise(a/p[k-1],b/p[k-1],k-1).
Все, числа между a и b, которые делятся на p[k-1] можно представить в виде p[k-1]*m, где m пробегает значения от a/p[k-1] (не включительно) до b/p[k-1] включительно. Если m не делится на k-1 первых простых чисел, то и исходное число не делится.
Окончание рекурсии
1) divise(a,b,0) = b-a;
2) divise(a,a,k) = 0;
В дальнейшем при оптимизации отсек последний шаг рекурсии (увеличило скорость на ~10...15%) и сделал как в коде.
Старый более медленный исходник такой.
#include <iostream.h> long long a,b,p[100],k,i; long long divise(long long m, long long n, int r){ if(!r--)return n-m; if(m==n)return 0; return divise(m,n,r)-divise(m/p[r],n/p[r],r); } int main(){ cin >> a >> b >> k; while(i<k)cin >> p[i++]; cout << divise(--a,b,k); return 0; }
Поза форумом
Фух, мій розв'язок Division пройшов на 54 бали
я вже почав думати, що він і 30 не набере, після того, як виставили ідею andervish
Поза форумом
Сію хвилину бали ще не остаточні.
Остаточними бали будуть вважатися після того, як розішлють відповідного листа.
(якщо все гаразд -- дуже скоро).
Поза форумом
У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?
Поза форумом
Плз, киньте хтось ідею на Towns і Instigator
Поза форумом
programist написав:
У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?
Див. повідомлення Ilya Porublyov
Поза форумом
MItornaDOS написав:
Плз, киньте хтось ідею на Towns і Instigator
Towns -- Кормен, Лейзерсон, Ривест, Штайн, задача 15-1 (битоническая евклидова задача коммивояжера)
Instigator -- геометрія щоб з'ясовувати які пари вершин видимі одна з одної (не затуляють інші ребра), далі алгоритм Дейкстри або який-небудь аналог
programist написав:
У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?
Наскільки великий запас часу при он-лайн перевірці? Скопіюй час (по кожному тесту окремо) скільки працює ця програма і скільки працює яка-небудь дуже дурна, яка буде перевищувати ліміт часу абсолютно завжди. Якщо різниця по кільком тестам сумарною вартістю 8 балів мала -- ситуація нормальна і не підлягає апеляції.
==============================
А чому досі ніхто з учасників не виклав на форумі запит (адресу) який генерить сумарні результати за три тури? Зазвичай викладували раніше ніж у журі доходили руки писати цей запит...
А то я написав тільки http://www2.olymp.vinnica.ua/cgi-bin/v_ … nguage=ukr а всі 15 задач вписувати ліньки...
Відредаговано Ilya Porublyov (2011-01-26 18:28:53)
Поза форумом
Видаю свій код розвязку задачі division на аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended. Справа в тому, що множення довгих(int64) чисел займає набагато більше часу ніж додавання логарифмів цих чисел разом з наступним експонціюванням суми.
function dlinachisla(m:int64):extended; begin dlinachisla:=ln(m); end; var v:array[1..15]of integer; k,n,p,p1:integer; flag:boolean; procedure inicializacia; var i:integer; begin k:=0; for i:=n-p1+1 to n do begin inc(k); v[k]:=i; end; end; procedure novacombinacia; var i:integer; begin if v[1]>1 then dec(v[1]) else begin for i:=2 to p1 do if v[i]>i then begin dec(v[i]); break; end; for i:=i-1 downto 1 do v[i]:=v[i+1]-1; end; end; function novaformacia:boolean; var i:integer; begin novaformacia:=false; for i:=2 to p1 do begin if (v[i]-v[i-1]>1) then begin dec(v[i]); novaformacia:=true; break; end; end; for i:=i-1 downto 1 do v[i]:=v[i+1]-1; end; var i,j,f,ff:integer; a1,b1,sum,t,sumdiln,promsum:int64; q:array[1..100]of int64; lenge:array[1..100]of extended; lengb1,lenga1,dl:extended; begin read(a1,b1,n); if a1>b1 then begin sum:=a1;a1:=b1;b1:=sum;end; for i:=1 to n do begin read(sum); q[i]:=sum; end; for i:=1 to n do for j:=n downto i do if q[i]<q[j] then begin t:=q[i]; q[i]:=q[j]; q[j]:=t; end; for i:=1 to n do lenge[i]:=dlinachisla(q[i]); lengb1:=dlinachisla(b1); lenga1:=dlinachisla(a1); p:=n;f:=0; dl:=0;a1:=a1-1; for j:=n downto 1 do begin inc(f); dl:=dl+lenge[j]; if dl>lengb1 then begin break; end; p:=f; end; ff:=-1;sumdiln:=0; for i:=1 to p do begin p1:=i;ff:=-ff; inicializacia;flag:=false; promsum:=0; if (p1<p-1) then repeat sum:=1;dl:=0; for j:=1 to p1 do dl:=dl+lenge[v[j]]; if dl<=lengb1 then begin sum:=round(exp(dl)); if dl>lenga1 then promsum:=promsum+b1 div sum else promsum:=promsum+b1 div sum-a1 div sum; if v[p1]=p1 then flag:=true; novacombinacia; end else if novaformacia then flag:=false else flag:=true; until flag else repeat sum:=1;dl:=0; for j:=1 to p1 do dl:=dl+lenge[v[j]]; if dl<=lengb1 then begin for j:=1 to p1 do sum:=sum*q[v[j]]; if dl>lenga1 then promsum:=promsum+b1 div sum else promsum:=promsum+b1 div sum-a1 div sum; if v[p1]=p1 then flag:=true; novacombinacia; end else if novaformacia then flag:=false else flag:=true; until flag; sumdiln:=sumdiln+promsum*ff; end; writeln(b1-a1-sumdiln); end.
Поза форумом
LeonID написав:
Видаю свій код розвязку задачі division на аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended.
Не знаю, як щодо часу роботи, але загальновідомо що extended не забезпечує достатню кількість знаків щоб точно зберігати довільне значення з int64. А тести які не проходить -- time limit чи wrong answer?
Поза форумом
Ilya Porublyov написав:
LeonID написав:
Видаю свій код розвязку задачі division на аудиторію, незважаючи на те, що він набирає(поки, що) лише 51 бал. Думаю, я один хто використав у цій задачі тип extended.
Не знаю, як щодо часу роботи, але загальновідомо що extended не забезпечує достатню кількість знаків щоб точно зберігати довільне значення з int64. А тести які не проходить -- time limit чи wrong answer?
Щоб забезпечити точність прийшлось скоротити кількість доданків, всі помилки - time limit.
Поза форумом
Ilya Porublyov написав:
programist написав:
У статистиці у мене по задачі Prize - 52 бали. А на онлайн перевірці той самий розв'язок отримав 60 балів. Як таке може бути?
Наскільки великий запас часу при он-лайн перевірці? Скопіюй час (по кожному тесту окремо) скільки працює ця програма і скільки працює яка-небудь дуже дурна, яка буде перевищувати ліміт часу абсолютно завжди. Якщо різниця по кільком тестам сумарною вартістю 8 балів мала -- ситуація нормальна і не підлягає апеляції.
Дурна програма набрала 0 балів із Time Limit. Моя програма має час на 0-13 тестах: 0,01 секунди, а на останніх двох: 0,02 секунди.
Поза форумом