Этим контестом мы хотим всех поздравить с наступившим новым учебным годом. Желаем отличных оценок, халяв на сессии и Accepted на контестах. Пусть этот год принесет вам много новых интересных знаний!
Артем Рахов и команда Codeforces
P. S. Обратите внимание, что раунд пройдет по правилам Codeforces. Ознакомьтесь с правилами до начала соревнования. Удачи!
UPD:
- Задачи
- Результаты
- Победитель: AnshAryan
- Разбор
А в первом дивизионе не судьба? Либо хотят самоутвердиться?
Вот поэтому желательно бы делать отдельные соревнования для обоих дивов в одно время
А то куча "умных" среди первых мест. Хоть я и не претендую на первые строчки даже во 2м диве, все равно мало приятного
Задачи отличные!
За контест спасибо. :-)
Однако печально, что очевидный способ взлома по первой задаче, когда подаёшь n=3000 и ряд из 3000 чисел, некоторые не предусмотрели. +4 взлома )
Было круто!
Also need this test!
5
-1 -2 -6 -3 -4
Btw, how are you getting the tests?
Or any hints about C?
4
1 2 3 4
??
answers are:
(1)
3
1 2 4
(2)
3
1 3 4
3000
1 2 3 4 5 6...... 3000
;)
the answer is 3001
Try this:
Input:
1
2
Output:
1
My Submission ID is 111986
- p_x>p_z & p_z>p_y (won x and lost to y) => p_x>p_y (y better x)
- p_x<p_z & p_z<p_y (lost to x and won y) => p_x<p_y (x better y)
Otherwise we cannot define outcome and able to output any.Just as SKYDOS 's TopSort.
Ну в задаче C всего 2 варианта. Либо есть решение и такая подпоследовательность всегда длиной 3, либо нет. Если есть то ищем в какой точке экстремум и выводим например
1 [номер экстремума] n
Если же нет, то выводим 0
Но кстати моя программа выдала бы
1 7 8
Так что первый все-таки вполне себе участник)
Ну да) Не подумал, в моем решении было не вывод n в конце, а вывод следующего после экстремума (причем если например 3 2 2 2 3 2, то учитывается 2 на позиции 4, то есть моя программа выдавала 1 4 5) =)
Спасибо, что поправили. Действительно я ошибся) Извините
I did it like
cout<<num1<<" "<<num2<<endl;
but I got P.E. on test 1
#include <iostream>
#include <cstring>
using namespace std;
int games[60][60];
int winsto[60][60];
bool getsToWinTo(int i, int j)
{
for(int ii=1; ii<=60; ii++)
{
if(winsto[i][ii] && winsto[ii][j])
return true;
}
return false;
}
int main()
{
int n;
cin>>n;
int a,b;
memset(games,0,sizeof(games));
int t=n*(n-1);
t/=2;
t--;
//cout<<tope<<endl;
for(int i=0; i<t; i++)
{
cin>>a>>b;
games[a][b]=1;
games[b][a]=1;
winsto[a][b]=1;
}
bool done=false;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i==j) continue;
if(!games[i][j] && getsToWinTo(i,j))
{
cout<<i<<' '<<j<<endl;
done=true;
break;
}
}
if(done) break;
}
//cin>>a;
return 0;
}
That's the reason of PE, not the ' '.
Ошибка представления данных на тесте 1
Can someone post an idea for Problem E ?
Thanx ! :)
hope can do something to you.
i want to know how to do C and E.
B и C не прошла из-за ошибки представления данных на тесте 1
3-ая
Даже такое выдает "Ошибку презентации".
var
mv,ml:array[1..100,1..100] of longint;
i1,q,q1,n,m,i,j,x,y:longint;
begin
write(4,' ',3);
end.
попробуй переписать на С++ или на другом языке, который знаешь.
Если хочешь могу проверить твой же код, но на шарпе.
PE не от этого был, а от того, что программа ничего не выводила вовсе.
Но почему выше код, который я указал выдает ПЕ непонятно... там же или ВА (если не равно сэмплу) либо АС и ВА на втором тесте.
И действительно странно, что вот это
#include <cstdio>
int main() {
puts("4 3");
return 0;
}
PE #1.
Это
#include <cstdio>
int main() {
puts("3 4");
return 0;
}
- PE #1.
А это
#include <cstdio>
int main() {
puts("1 2");
return 0;
}
WA #1.
o_O
сам заметил такое и с Дельфи и Фри Паскалем.
Поддерживаю Макса.
ЧЗХ?
#include <cstdio>
int s;
int main() {
scanf("%d", &s);
if ( s == 4 )
puts("4 3");
else
puts("1 2");
return 0;
}
WA #1.
#include <cstdio>
int main() {
puts("3 1");
return 0;
}
WA #2
Значит на входе у нас скорее всего N = 3, а мы тут ему хоп - 4 3 выдаём. А откуда у тебя 4 если N = 3? Вот тебе Ошибка представления данных.
Только не знаю, нормальное ли это поведение для чекера.
А ещё, возможно, нехорошо, что сэмплтест не является первым финальным тестом.
Other solution for problem E could be:
* Factorize N (assume that M will be the number of prime factors) -- O(sqrt(N))
* Calculate all the possible arrays b[1..M'] (M' <= M) multiplying i prime factors of N (with i: 0 <= i <= m) -- O(M * 2 ^ M))
* Sort the resulting array b[1..M'] in non-increasing order -- O(M' log M')
* Calculate a number X (X = 2 ^ (b[1] - 1) * 3 ^ (b[2] - 1]) * 5 ^ (b[3] - 1) ...) -- O(M' log N)
* Take the minimum X among all the possible arrays -- O(sqrt(N) + M * 2 ^ M * (M' log M' + M' log N)). This algorithm will run in time.
For example,
N = 16
* b = [2, 2, 2, 2] -> 210
* b = [4, 2, 2] -> 120
* b = [4, 4] -> 216
* b = [8, 2] -> 384
* b = [16] -> 32678
(Some arrays may appear several times)
I wanted to share this information with you, but, IMO DP is a more elegant (and shorter) solution for this problem =).
int a[100010], b[3];
int n;
bool res;
int main() {
int k = 1;
scanf("%d", &n);
scanf("%d %d", &a[0], &a[1]);
for (int i = 2; i < n; ++i) {
scanf("%d", &a[i]);
if (a[0] > a[k]) {
if (a[k] < a[i]) { b[2] = i + 1; res = true; break; }
else ++k;
} else {
if (a[k] > a[i]) { b[2] = i + 1; res = true; break; }
else ++k;
}
}
b[0] = 1;
b[1] = k + 1;
if (res == false) printf("0\n");
else printf("3\n%d %d %d\n", b[0], b[1], b[2]);
return 0;
}
I`m getting WA :((