Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#1 2011-12-28 18:06:11
Розв’язки задач 2 туру
Почну нову тему, хоч il____ уже й почав викладати рішення в існуючих. По-моєму, зручніше буде, коли обговорення рішень проходить окремо від обговорення задач.
Викладаю код уже перевірених задач, поступово додаватиму коментарі.
SORTING
Загальна ідея:
назвемо "циклом" таку підмножину даної послідовності, що за будь-якої послідовності обмінів, кожен обмін двох елементів циклу ставитиме на "своє" місце не більше, ніж 1 число. Очевидно, що для сортування кожного циклу потрібно k-1 обмін, де k - кількість елементів циклу.
Якщо у нас m таких циклів, то відповіддю буде sum{i=1;m}(k_i-1)=sum{i=1;m}(k_i)-m;
Оскільки, sum{i=1;m}(k_i)=n, то відповіддь перетворюється на n-m. Де n - к-ть елементів у масиві, m - к-ть "циклів";
Код:
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int N,t,res;
cin>>N;
res=N;
vector<int> a(N);
for(int i=0;i<N;i++)cin>>a[i],a[i]--;
for(int i=0;i<N;i++)
{
if(a[i]==-1)continue;
t=i;
do
{
int T=t;
t=a[t];
a[T]=-1;
}while(t!=i&&t>=0);
res--;
}
cout<<res<<endl;
}SEQUENCE
Загальна ідея:
Позначимо за х шукане число. Тоді для пошуку ікса можна скласти квадратне рівняння. Після певної кількості перетворень сум отримаємо рівняння
x^2-2k^2 * x - k^2 * (2k+1).
Коренями цього рівняння будуть -k та k(2k+1)=k*n=n*(n-1)/2. Перший нам не підходить, а другий завжди задовольнятиме умові. Тобто відповіді "-1" бути не може.
Код:
#include <iostream>
using namespace std;
int main()
{
int N;
cin>>N;
cout<<N*(N-1)/2<<endl;
}PLUMS
Підійде будь-який алгоритм генерації магічних квадратів, описаний тут, оскільки у нашому квадраті умова про рівність сум має виконуватися тільки для рядків.
Код:
#include <vector>
#include <iostream>
using namespace std;
class almostMagic
{
int N;
vector<vector<int> > a;
public:
void init()
{
int x=0,y=N/2,cnt=1;
while(cnt<=N*N)
{
if(x<0){x=N-1;continue;}
if(y<0){y=N-1;continue;}
if(x>=N){x=0;continue;}
if(y>=N){y=0;continue;}
if(a[x][y]){x--;continue;}
a[x][y]=cnt;
cnt++;
x--;y++;
}
}
almostMagic(int n=0):N(n),a(n,vector<int>(n)){init();}
friend istream& operator>>(istream &in,almostMagic& rhs)
{
in>>rhs.N;
rhs.a.resize(rhs.N,vector<int>(rhs.N));
rhs.init();
}
friend ostream& operator<<(ostream& out,almostMagic& rhs)
{
for(vector<vector<int> >::iterator i=rhs.a.begin();i!=rhs.a.end();++i)
{
for(vector<int>::iterator j=i->begin();j!=i->end();++j)
out<<*j<<" ";
out<<endl;
}
}
};
int main()
{
almostMagic a;
cin>>a;
cout<<a;
}SumOfPowers
Відправив на перевірку версію з використанням STL, яка при використанні оптимізації компілятора -О2 працює 200мс на найгіршому тесті, але без оптимізації, на жаль, майже 2 секунди. Оскільки тут, як я нещодавно дізнався, оптимізації вимкнені, то я отримав ТЛ-и на кількох тестах и отримав результат 33 бали(
Викладаю модифіковану, менш чуттєву до прапорів компіляції. Набирає 40 балів.
Загальна ідея:
Задачу можна звести до задачі про банкомат з нескінченною кількістю банкнот. "Номіналами" виступатимуть чила виду i^K. Така задача розв’язується за допомогою ДП з асимптотикою O(N*L), де N - максимальне вхідне число, L - кількість номіналів. Оскільки номіналів у нас N^(1/K), то маємо асимптотику O(N(1+1/K)).
І все було б добре, якби не квадрати. Для них асимтотика O(N^1.5) працює занадто довго.
Можна помітити, що будь-яке число можна розкласти на суму не більше, ніж 4 квадратів. По моєму, це навіть кимось доведено математично. Скористаємося цим фактом. Можна було б розкладати кожне число(перевірити, чи є число квадратом можна за О(1), розкласти на 2 квадрати - за O(sqrt(N), на 3 квадрати - за O(N). Якщо розкладання не знайдено, то відповідь - 4). Але в такому разі асимптотика була б O(M*N), що при даних обмеженнях може бути навіть гірше ніж початкове O(N^1.5). Тому не будемо повністю "викидати" динаміку, адже ми все-одно неодноразово вирішуємо однакові підзадачі, що перекриваються. Заповнимо наш "банкоматний" масив тілько одиницями(O(sqrt(N)) та двійками (O(N)). далі розглядаємо в циклі всі наші числа, і якщо це число ще не розкладене на 1 чи 2 квадрати - пробуємо відняти від нього всі i, такі що i^2<=N. І якщо на місці різниці стоїть двійка, то відповідь 3. Якщо жодного разу такої ситуації не виникло - відповідь 4.
Таким чином, для квадратів отримали асимптотику O(N+M*sqrt(N))
Ну і ще деякі незначні оптимізації та хаки для крайніх випадків(при К=1, очевидно, відповідь для будь-кого числа - 1. А при К>=20 при даних обмеженнях відповіддю для будь-якого числа буде саме це число, оскільки 2^20>987654).
Код:
#include <iostream>
#include<algorithm>
#include<limits>
using namespace std;
typedef unsigned long long ull;
ull fast_pow(ull x,ull power)
{
ull res=1;
while(power)
{
if(power%2)res*=x;
x*=x;
power>>=1;
}
return res;
}
int main()
{
int K,M,max=numeric_limits<int>::min();
cin>>K>>M;
static int a[9876];
for(int i=0;i<M;i++)cin>>a[i],max=std::max(max,a[i]);
if(K>=20)
{
for(int i=0;i<M;i++)cout<<a[i]<<" ";
return 0;
}
if(K==1)
{
for(int i=0;i<M;i++)cout<<1<<" ";
return 0;
}
static int powers[1000],result[987656];
memset(result,0x7f,sizeof(result));
result[0]=0;
ull t;
for(int i=1;;i++)
{
t=fast_pow(i,K);
powers[i-1]=t;
if(t>max)break;
result[t]=1;
result[t+1]=2;
}
if(K==2)
{
for(int k=0;powers[k]<=max;k++)
for(int j=k;powers[j]+powers[k]<=max;j++)
if(result[powers[j]+powers[k]]!=1)result[powers[j]+powers[k]]=2;
for(int i=0;i<M;i++)
{
int res=result[a[i]]<=3?result[a[i]]:4;
for(int k=0;powers[k]<=a[i]&&res==4;k++)
{
if(result[a[i]-powers[k]]==2)res=3;
}
result[a[i]]=res;
cout<<res<<" ";
}
}
else
{
for(int i=2;i<=max;i++)
{
for(int j=0;powers[j]<=i/2;j++)
{
if(result[i]<=2)break;
if(result[i-powers[j]]+1<result[i])result[i]=result[i-powers[j]]+1;
}
}
for(int i=0;i<M;i++)
cout<<result[a[i]]<<" ";
}
}Platforms
Як і багато інших, я провтикав можливість стрибати назад і отримав 12 балів. Як і у багатьох інших, після додавання однієї умови задача пройшла на 40 балів.
Принцип роботи пояснювати, думаю, не має сенсу - банальна динаміка. Але якщо комусь потрібно все-таки описати алгоритм, то опишу)
Код:
#include <vector>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
int N;
cin>>N;
vector<ll> a(N),b(N),c(N);
for(int i=0;i<N;i++)cin>>a[i];
b[0]=c[0]=0;
b[1]=llabs(a[1]-a[0]);
c[1]=(a[1]-a[0])*(a[1]-a[0]);
for(int i=2;i<N;i++)
{
b[i]=min(b[i-1]+llabs(a[i]-a[i-1]),b[i-2]+3*llabs(a[i]-a[i-2]));
c[i]=min(c[i-1]+(a[i-1]-a[i-2])*(a[i-1]-a[i-2])+3*(a[i]-a[i-2])*(a[i]-a[i-2]),min(c[i-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),c[i-2]+3*(a[i]-a[i-2])*(a[i]-a[i-2])));
}
cout<<b.back()<<" "<<c.back()<<endl;
}Відредаговано Dim_ov (2011-12-30 12:47:15)
Поза форумом
#2 2011-12-29 10:55:51
Re: Розв’язки задач 2 туру
(И.Н. Порублёв А.Б. Ставровский Алгоритмы и программы решение олимпиадных задач)
вроде этот код посимпатичнее будет... 
Код:
//Plums
#include <iostream>
using namespace std;
int main() {
int N,NN;
cin >> N;
NN=N*N;
for(int i=1,n; i<=N; i++)
{
n=i;
cout << n;
while(n<=NN)
{
if (n%N == 0) n++; else n=n+N+1;
if (n<=NN) cout<<" "<<n;
}
cout << endl;
}
return 0;
}А задачу SumOfPowers на 40 баллов решило всего 10 человек!
Интересно, поделится кто-нибудь решением, или нет?
Відредаговано LVV (2011-12-30 10:47:01)
Вік живи - вік навчайся.
Поза форумом
#3 2011-12-29 13:30:55
- Unknown
- Новий користувач
- Зареєстрований: 2011-10-28
- Повідомлень: 31
Re: Розв’язки задач 2 туру
Platforms - 40 : (после того, как узнал про вариант прыжка назад, добавил 2 строчки и сдал 
)
Код:
#include <iostream>
using namespace std;
long long MINIMUM(long long a,long long b){
if(a<b)return a;
else return b;
}
long long A(long long z){
return z>0 ? z : -z ;
}
main(){
long long a[50001],b[50001],c[50001];
int i,n;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
b[0]=0;
b[1]=0;
b[2]=A(a[2]-a[1]);
c[0]=0;
c[1]=0;
c[2]=(a[2]-a[1])*(a[2]-a[1]);
for(i=3;i<=n;i++){
long long b1,b2; //два варианта, чтоб не запутаться (1 задача)
long long c1,c2,c3; //три варианта, чтоб не запутаться (2 задача)
b1=A( a[i]-a[i-1] )+b[i-1]; //вариант прыжка с соседней платформы
b2=A( 3*(a[i]-a[i-2]) )+b[i-2]; //вариант прыжка через платформу
b[i]=MINIMUM(b1,b2);
c1=(a[i]-a[i-1])*(a[i]-a[i-1])+c[i-1]; //вариант прыжка с соседней платформы
c2=3*(a[i]-a[i-2])*(a[i]-a[i-2])+c[i-2]; //вариант прыжка через платформу
c3=( (a[i-1]-a[i-2])*(a[i-1]-a[i-2])+c[i-1] ) + 3*(a[i]-a[i-2])*(a[i]-a[i-2]); //вариант прыжка с соседней назад, и через платформу
c[i]=MINIMUM( MINIMUM(c1,c2),c3 );
}
cout<<b[n]<<" "<<c[n];
}Відредаговано Unknown (2011-12-29 13:37:32)
Поза форумом
#5 2011-12-29 19:16:53
- Ilya Porublyov
- журі
- Зареєстрований: 2005-10-27
- Повідомлень: 130
Re: Розв’язки задач 2 туру
Щодо SumOfPowers
Основний алгоритм такий.
Заводимо одновимірний масив DP[] від 0 до maxN (максимального зі згаданих у вхідних даних Ni).
Ініціалізуємо його як DP[i]=i, тому що яким би не був показник K завжди можна набрати i як суму i штук 1^K. Далі перебираємо всі такі основи j, що j^K <= maxN, і для кожного з них дивимося, чи може використання такого степеню зменшити кількість доданків:
DP[i + j^K] = min(DP[i + j^K] , DP[i]+1), де i знов-таки перебираються всі можливі.
Після завершення цих (вкладених) циклів, просто виводимо для кожного вхідного Ni відповідний елемент DP[Ni].
АЛЕ!!! Хоча описаний алгоритм формально правильний для всіх можливих вхідних даних, фактично його доцільно використовувати виключно при 3<=K<=19.
При K>=20 відповідь для будь-якого Ni все одно гарантовано буде Ni, тому що навіть 2^K вже більше за Ni.
При K=1 цей алгоритм працюватиме дуже довго, вертаючи для будь-якого Ni гарантовану відповідь 1, бо будь-яке Ni можна подати у вигляді одного доданку Ni^1
Найменш очевидний момент -- при K=2 алгоритм теж працює занадто довго. Треба було знайти у літературі/Інтернеті/ще_де-небудь факт, що будь-яке натуральне число може бути подане у вигляді суми не більш як чотирьох квадратів натуральних чисел, а також ознаки, для яких саме чисел ця кількість буде 1, для яких 2, для яких 3 і для яких 4.
І для K=1 та K=2 доцільно НЕ заповнювати табличку DP, а просто розв"язувати окремо для кожного введеного Ni.
Можливо, в якійсь невеликій мірі все це (різні алгоритми при різних K) і брудний хак. Але, на моє тверде переконання, лише в зовсім невеликій. У значно меншій, ніж, наприклад, масив констант.
Поза форумом
#6 2011-12-29 19:40:24
Re: Розв’язки задач 2 туру
Ilya Porublyov написав:
Можливо, в якійсь невеликій мірі все це (різні алгоритми при різних K) і брудний хак. Але, на моє тверде переконання, лише в зовсім невеликій. У значно меншій, ніж, наприклад, масив констант.
До речі, журі не відстежували, скільки було спроб таки відправити мегабайти захардкоджених відповідей?
Поза форумом
#7 2011-12-29 20:11:24
- Зевс
- Новий користувач
- Зареєстрований: 2009-11-03
- Повідомлень: 62
Re: Розв’язки задач 2 туру
Dim_ov написав:
то маємо асимптотику O(N(1+1/K))
А если k=3? Ведь тогда асимптотика N*N^{1/3} = 10^6 * 10^2 = 10^8. Многовато, разве нет? Или уже решения, которые делают 10^8 операций, принимаются? (безусловно сейчас на неплохих компьютерах/серверах такие решения влазят в 1с, но...).
Лично у меня было написано такое же решение, которое было описано выше Ilya Porublyov, но я подумал, что отправив его, для небольших k в ТЛ оно не влезит.
Может кто-то подсказать, почему код:
#include <iostream>
using namespace std;
int main()
{
int k, m, n;
scanf("%d%d", &k, &m);
for (int i=0; i<m; (i != (m-1)) ? printf(" ") : printf("\n"), ++i) {
scanf("%d", &n);
if (k >= 20) printf("%d", n); else
if (k >= 13) printf("%d", (n/(1<<k)) + (n%(1<<k))); else
if (k == 1) printf("1"); else
printf("0");
}
}
на некоторых тестах работает больше секунды и получает ТЛ (на онлайн проверке)?
Відредаговано Зевс (2011-12-29 20:16:43)
Поза форумом
#8 2011-12-29 20:49:00
Re: Розв’язки задач 2 туру
Зевс написав:
А если k=3? Ведь тогда асимптотика N*N^{1/3} = 10^6 * 10^2 = 10^8. Многовато, разве нет? Или уже решения, которые делают 10^8 операций, принимаются? (безусловно сейчас на неплохих компьютерах/серверах такие решения влазят в 1с, но...).
Лично у меня было написано такое же решение, которое было описано выше Ilya Porublyov, но я подумал, что отправив его, для небольших k в ТЛ оно не влезит.
Ну, я вирішив не гадати, влізе чи не влізе, а просто спробувати І працює воно ~400ms без оптимізацій та ~200ms з -О2. ДП для квадратів працювало, якщо не помиляюся, близько 2-3 секунд, тобто удесятеро довше, ніж для кубів. Що, в принципі й логічно (10^9/10^8=10, зі збільшенням К час зменшується експоненціально). Ну і комп’ютер у мене не самий швидкий(2.33 ГГц). Так що в секунду влазить із запасом навіть на не найсучаснішому сервері.
Чому код отримує ТЛ-и навіть не уявляю
UPD: Схоже причина - перемішування введення та виведення. Якщо читати в масив, а потім опрацьовувати - то без ТЛ-ів. Мабуть різні тести по-різному вводяться перевіряючою системою в програму.
Відредаговано Dim_ov (2011-12-29 21:31:01)
Поза форумом
#9 2011-12-29 22:43:12
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Розв’язки задач 2 туру
Хм... я чогось думав що scanf і printf не в iostream, а в stdio.h
у мене цей код навіть не компілиться... а север приймає... і перевіряє
Дивина...
Поза форумом
#10 2011-12-30 09:15:23
Re: Розв’язки задач 2 туру
Dim_ov написав:
Оновив шапку
В Visual Studio 2010 Ваш код SumOfPowers не компилируется.
в
Код:
ull fast_pow(ull x,ull power)
ull - не определён.
Відредаговано LVV (2011-12-30 11:09:39)
Вік живи - вік навчайся.
Поза форумом
#11 2011-12-30 10:34:09
Re: Розв’язки задач 2 туру
Ilya Porublyov написав:
Щодо SumOfPowers
Основний алгоритм такий...........
Ну, с алгоритмом более-менее понятно.
А нельзя ли увидеть код рабочей программы.
Просто я был уверен в правильности свого решения, но полный набор тестов оно не прошло. И не попричине тайм-лимита, а по причине неверных результатов.
Вот и хотелось бы сравнить и проверить кое-что.
Поскольку полные наборы тестов являются секретом до самого завершения олимпиады, то хотелось бы всё таки хоть один рабочий код полнобальной программы SumOfPowers увидеть, чтобы Новый год встретить спокойно
С наступающим!
Вік живи - вік навчайся.
Поза форумом
#12 2011-12-30 11:01:14
Re: Розв’язки задач 2 туру
Зевс написав:
Может кто-то подсказать, почему код:
#include <iostream>
using namespace std;
int main()
{
int k, m, n;
scanf("%d%d", &k, &m);
for (int i=0; i<m; (i != (m-1)) ? printf(" ") : printf("\n"), ++i) {
scanf("%d", &n);
if (k >= 20) printf("%d", n); else
if (k >= 13) printf("%d", (n/(1<<k)) + (n%(1<<k))); else
if (k == 1) printf("1"); else
printf("0");
}
}
на некоторых тестах работает больше секунды и получает ТЛ (на онлайн проверке)?
MItornaDOS написав:
Хм... я чогось думав що scanf і printf не в iostream, а в stdio.h
у мене цей код навіть не компілиться... а север приймає... і перевіряє
Дивина...
У Visual Studio компілює нормально...
Але результати видає абсурдні: навіть на стандпртний тест 2 3 9 17 6 видає три нулі.
Вік живи - вік навчайся.
Поза форумом
#13 2011-12-30 12:27:33
Re: Розв’язки задач 2 туру
LVV написав:
Але результати видає абсурдні: навіть на стандпртний тест 2 3 9 17 6 видає три нулі.
Якщо я все правильно зрозумів, результати і не претендують на правильність. Питання було у тому, чому цей код, який має працювати за О(М), видає ТЛ-и на онлайн-перевірці.
Поза форумом
#14 2011-12-30 12:39:50
- Зевс
- Новий користувач
- Зареєстрований: 2009-11-03
- Повідомлень: 62
Re: Розв’язки задач 2 туру
Конечно даже на стандартный тест этот код выдает нули, так как это не код рабочей программы . Мой код рабочей программы не проходит некоторые тесты по ТЛ, хотя все остальные отрабатывает правильно за 0,01с - 0,02с. И я не могу понять почему. Вот я его и упростил - конечно же теперь все тесты FAILED, только дело в том, что вот такой простой кусок кода на тех же самых тестах получает ТЛ. И не ясно, почему. Я тоже думал, что возможно дело в том, что идет поочередный ввод/вывод, но во-первых большинство-то тестов проходит. А во-вторых чем же это плохо, если программа выводит ответ сразу, а не сохраняет все ответы в массив и потом их выводит. Еще ни на одной олимпиаде, ни на одной проверяющей системе такой проблемы я не встречал. Хотя все-равно довольно странным остается то, что большинство тестов проходят.
Уважаемое Жюри, если проблема действительно в поочередном вводе/выводе, можете написать, пожалуйста, об этом. Мне хотелось бы разобраться с образовавшейся ситуации, чтобы в следующий раз не делать подобных ошибок. Заранее спасибо.
Поза форумом
#16 2011-12-30 13:03:54
- shadybaby
- Новий користувач
- Зареєстрований: 2011-11-22
- Повідомлень: 3
Re: Розв’язки задач 2 туру
LVV
що до SumOfPowers..
введи 3 1 32
що виводить?
Поза форумом
#17 2011-12-30 15:45:17
Re: Розв’язки задач 2 туру
shadybaby написав:
LVV
що до SumOfPowers..
введи 3 1 32
що виводить?
Да Вы прямо мои мысли читаете.
Действительно:
32 = 2^3+2^3+2^3+2^3 (4 слагаемых)
А у меня не так.
Выходит, мой алгоритм никудышний, хоть и набрал 11 баллов...)
Спасибо за пример.
С Наступающим!
Відредаговано LVV (2011-12-31 06:51:58)
Вік живи - вік навчайся.
Поза форумом
#18 2011-12-31 13:19:11
- iama
- Новий користувач
- Зареєстрований: 2011-12-26
- Повідомлень: 3
Re: Розв’язки задач 2 туру
Мій SumOfPowers, надіслав не ту версію і втратив 3 бали
Код:
#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAX_N 1000001
using namespace std;
int mpow (long long a, long long n)
{
long long p = 1 % n;
while (n)
{
if (n % 2)
p = p * a;
if (n /= 2)
a = a * a;
if (p > MAX_N)
return MAX_N;
}
return p;
}
int d[MAX_N], dp[1001], sv[10000], n, m, k, qp, i, j;
int main()
{
cin >> k >> n;
for (i = 0; i < n; i++)
cin >> sv[i];
if (k == 1)
{
cout << '1';
for (i = 1; i < n; i++)
cout << " 1";
cout << endl;
// return 0; -3 бали тут :(
}
if (k == 2)
{
char s2[MAX_N] = {}, s3[MAX_N] = {};
for (i = 1; i <= 1000; i++)
dp[i] = i*i;
for (i = 1; i <= 1000; i++)
for (j = 1; dp[i] + dp[j] < MAX_N; j++)
s2[dp[i] + dp[j]] = 1;
for (i = 0; i < n; i++)
{
d[sv[i]] = 4;
int sq = sqrt(double(sv[i]));
if (sq * sq == sv[i])
{
d[sv[i]] = 1;
continue;
}
if (s2[sv[i]])
{
d[sv[i]] = 2;
continue;
}
d[sv[i]] = 4;
for (j = 1; j*j <= sv[i]; j++)
if (s2[sv[i] - j*j])
{
d[sv[i]] = 3;
continue;
}
}
cout << d[sv[0]];
for (i = 1; i < n; i++)
cout << ' ' << d[sv[i]];
cout << endl;
return 0;
}
m = 0;
for (i = 1; dp[i-1] < MAX_N; i++)
dp[i] = mpow(i, k), m++;
d[0] = 0;
for (i = 1; i < MAX_N; i++)
{
d[i] = i;
for (j = 1; dp[j] <= i; j++)
{
qp = d[i - dp[j]] + 1;
if (d[i] > qp)
d[i] = qp;
}
}
cout << d[sv[0]];
for (i = 1; i < n; i++)
cout << ' ' << d[sv[i]];
cout << endl;
return 0;
}Поза форумом
#19 2011-12-31 18:35:04
- Unknown
- Новий користувач
- Зареєстрований: 2011-10-28
- Повідомлень: 31
Re: Розв’язки задач 2 туру
iama написав:
втратив 3 бали
Можете сказать на каких примерно тестах потеряли? Просто потерял примерно столько, сколько и вы
Поза форумом
#20 2011-12-31 18:52:20
- iama
- Новий користувач
- Зареєстрований: 2011-12-26
- Повідомлень: 3
Re: Розв’язки задач 2 туру
Unknown написав:
iama написав:
втратив 3 бали
Можете сказать на каких примерно тестах потеряли? Просто потерял примерно столько, сколько и вы
Тесты, в которых k = 1, получил RE из-за того, что забыл прерывать выполнение после вывода правильного ответа. Если раскомментировать return 0; - будет заходить в полный балл.
Відредаговано iama (2011-12-31 18:53:12)
Поза форумом
#21 2011-12-31 19:08:15
- Unknown
- Новий користувач
- Зареєстрований: 2011-10-28
- Повідомлень: 31
Re: Розв’язки задач 2 туру
iama написав:
Тесты, в которых k = 1, получил RE из-за того, что забыл прерывать выполнение после вывода правильного ответа. Если раскомментировать return 0; - будет заходить в полный балл.
Ясно, я не из-за этого точно
Поза форумом
#22 2012-01-01 12:51:55
- valikluks95
- Новий користувач
- Звідки: Александрия
- Зареєстрований: 2010-12-03
- Повідомлень: 5
Re: Розв’язки задач 2 туру
Когда будет работать онлайн-проверка? Сейчас выдает "Произошла техническая ошибка"
Поза форумом
#24 2012-01-01 15:16:34
- valikluks95
- Новий користувач
- Звідки: Александрия
- Зареєстрований: 2010-12-03
- Повідомлень: 5
Re: Розв’язки задач 2 туру
Дякую, я був неуважний
Поза форумом
#25 2012-01-02 12:39:16
Re: Розв’язки задач 2 туру
Якщо в умові задачі Sorting "є певна надлишковість", то в умові Platforms є певна, на мою думку, недосказанність.
Вважаючи умову Platforms дуже вдалою, я все таки хотів би зауважити, що хоч стрибки назад і можна вважати вдалою родзинкою задачі, то це лише тому, що ніхто на форумі не поставив питання щодо можливості таких стрибків. А якби таке питання було, то автори (чи журі) були б зобов'язані дати на нього вичерпну відповідь. І тоді ця "таємниця" перестала би бути таємницею. А значить учасники що вже встигли відправити свої рішення опинились би в гірших умовах, ніж ті учасники, що ще не зробили цього (і сдідкують за форумом).
Доречі, учасники, що не встигли прочитати повідомлення "Мимопроходящего", теж опинились в гірших умовах.
Хотів би також відзначити дуже велику розбіжність у складності задач ІІ туру. Порівняти хоча б задачу Sequence з Platforms чи з SumOfPowers.
А взагалі, я хочу подякувати авторам, що умови задач перших двох турів були продуманими, вичерпними і чіткими. Завдяки цому на форумі майже не "ломали списів" стосовно умов завдань, чи результатів туру.
Усіх з Новим роком.
Відредаговано LVV (2012-01-02 12:42:00)
Вік живи - вік навчайся.
Поза форумом