Добрый день!
Приглашаю всех принять участие в соревновании, завершающем серию заочных олимпиад ЗКШ для школьников и одновременно являющемся очередным Codeforces-раундом. Начало соревнования - 12 декабря, в 11:00 по московскому времени.
Соревнование пройдет по правилам ACM-ICPC, продолжительность контеста - 3 часа.
Как и предыдущие школьные индивидуальные олимпиады, соревнование будет рейтинговым для всех участников (и для школьников, и для остальных). Рейтинг будет вычисляться в соответствии с объединенной таблицей результатов.
В качестве авторов задач снова выступаем я и Дмитрий Матов. Спасибо Геральду Агапову и Артему Рахову за помощь в подготовке задач и Марии Беловой за перевод условий.
Всем удачи!
UPD. Соревнование завершено. Доступны результаты. В школьной индивидуальной олимпиаде победил scottai1, в Codeforces Beta Round - ilyakor. Поздравляем победителей!
Опубликован авторский разбор задач. Теперь в разбор добавлены также задачи G и H.
Спасибо всем, кто принял участие в серии заочных олимпиад ЗКШ в конкурсе и вне конкурса!
Он сейчас в Минске на математической олимпиаде. Так что, и хотел бы досрочно OpenCup отрешать, не смог бы.
Да и не хотел.
И всё-таки выбор между школьной олимпиадой и opencup, где в это время будут все профи, очевиден.
Кто-нибудь знает, OpenCup сегодня точно будет? А то пока нет ни объявления о регистрации, ни ссылки Enter Contest. Обычно они появлялись за день-два.
1 19 - 10 + 19 = 28
доезжаем до 3й колонки, а не до второй
У меня задача разбилась на 3 части:
1) Предположим, что Ваня выграет - bfs'ом ищем путь к (0, 0)
2) D[0][0] == INF - Ваня не может выграть. Тогда, если есть цикл, то возможна ничья. Цикл ищем обычным dfs
3) Ваня проиграет, но теперь мы знаем, что граф ациклический - обычный dp на ациклических графах
Вот такой вот 3 в 1
const int N = 100010;
long long bk[N];
long long a[N];
int n;
int main()
{
int i, j, k;
scanf("%d",&n);
memset(bk,0,sizeof(bk));
for(i = 1; i<=n;i++)
{
scanf("%lld",&a[i]);
bk[a[i]]++;
}
i=1;
while(i+1<=n&&bk[i]>=bk[i+1])i++;
if(i<n) printf("-1\n");
else{
printf("%lld\n",bk[1]);
printf("%lld",bk[a[1]]--);
for(i = 2; i <=n;i++)
printf(" %lld",bk[a[i]]--);
}
scanf("%d",&i);
return 0;
}
Possibly that's a mistake:
yeah
my first code got presentation error on test 5 too.
i had to change my code completely and then got AC.but still i don't know where i made the mistake.
1
5
Correct answer is -1, you print
0
1
http://codepad.org/kS4YaBTk
When a car is located at station X and you refueled your car K times before (let's say initial moment also counts as refuel, so K >= 1), then the amount of fuel in the tank at station X is equal to [alpha * K - X * 10]. You can easily see that:
- if you had to stop at station X, then [alpha * K - X * 10] < 10 because otherwise you would have reached the next station without refuel
- if you didn't have to stop at station X, then [alpha * K - X * 10] >= 10
So, input values give you a set of less/greater conditions on alpha, so you can calculate alpha_lo and alpha_hi for the input data. Then you have to check a few forward station indices X and see if [alpha_lo, alpha_hi) is non-empty for them using the same algorithm. If you find a single matching value X, then the answer is unique. Otherwise it's not.
So, that gives you linear complexity in respect to the max station index.
this is my code(my reply to Narashy appeared below the filix's post!!)
#include<iostream>
#include<vector>
using namespace std;
vector<int> per[100010];
int a[100010],num[100010],lab[100010];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
num[a[i]-1]++;
for(int i=0;i<n;i++)
{
for(int k=0;k<num[i];k++)
{
per[k].push_back(i+1);
if(per[k].size()>1)
{
if(per[k][per[k].size()-1]!=per[k][per[k].size()-1])
{
cout<<"-1";
return 0;
}
}
if(per[k].size()==1&&per[k][0]!=1)
{
cout<<"-1";
return 0;
}
}
}
int l=0;
while(per[l].size()>0)
{
l++;
}
cout<<l<<endl;
for(int i=0;i<n;i++)
{
cout<<++lab[a[i]]<<" ";
}
return 0;
}
Why?
it seems large and it is because i don't know how to post a code here!
please tell me!!!thanks
Кто-то по-мойму даже +203 к рейтингу получал. (Здесь, а не на TopCoder-е).
Но всё равно поздравляю.
посмотри на первый контест.
Это смотря как выступать.
На топкодере за счет учета волатильности прыжки куда больше могут быть.
Petr за 5 контестов с 1866 до 3000 (227 в среднем), TTLovePP за 2 контеста 1944-2757 (569+244).
Я даже после двух загавняканых контестов всё равно остался жёлтым... хотя на tc я зелёный :) Мне не нравится что там нужно создавать класс.. я так и не научился там быстро его создавать и чекать тесты, хотя впечатлений от tc всё равно было море. Щас уже где то полгода не участвовал.
http://codeforces.me/profile/qujun51319
+264 сегодня
+756
http://www.topcoder.com/tc?module=MemberProfile&cr=22755328
:)
Почему-то на TCO08 есть люди с нулевым рейтингом и прыжками +1900.
THX
Ну а если даже и будет, что с того? Меньше народу будет здесь дорешивать? Да и слава богу, меньше нагрузка на сервер. Ведь за дорешивание все равно никаких бонусов нет.
А прилепить значок копирайта не трудно, естественно и здесь его надо использовать, вместе с еще какими-нибудь надписями.
Даже при верном решении могут возникать проблемы, такие как тут. А подобные проблемы иногда бывает очень сложно отловить без теста.
can anyone help me?!
my code gives the correct answer(-1)to the test case below:
1
5
i couldn't find my mistake,its good to put the test case 5 here.
can anyone help me?!
my code gives the correct answer(-1)to the test case below:
1
5
i couldn't find my mistake,its good to put the test case 5 here.
its right too!I'm really wondering !what's wrong with that!
i have posted my code(bud it's a little unreadable!)you can check it your self...thanks
Не... видимо это что то другое с моим кодом. Вроде подправил, всё равно ва4.
<cry>Хочу тест!!!!!</cry>
У меня в рейтинге по "Школьная индивидуальная олимпиада #1 (ЗКШ 2010/11) - Codeforces Beta Round #38 (ACM-ICPC Rules)" написано, что я занял нулевое место... баг
http://pastebin.com/VWkUw2Qj
6
Is this a correct solution?
In case this might be just a coincidence, This is the algorithm I applied;
using a counting sort, count the instances of each number while also storing the numbers in an array. Then, reading the numbers in the array one by one and simply printing its count and then reducing its count by 1.
http://codepad.org/GHUzcb2v this is the code if someone wants to go through it to understand what I have done.
If that is right then perhaps i made a mistake with my limits or something.
n is the number of planets.
problem B,what is it,answer?
Then you iterate over the entire matrix and calculate the sum in the small rectangle which can now be done in O(1) using the above matrix.
многоочень много?I got wrong answer in case no.7 ,,,problem - E -....plz any help
[code]
#include <string.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define all(c) c.begin(),c.end()
#define rep_(i,n) for(i=n-1;i>=0;i--)
#define rep(i,n) for(i=0;i<n;i++)
#define forr(i,a,b) for(i=a;i<=b;i++)
#define forr_(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) ( a>b? b : a )
#define max(a,b) ( a>b? a : b )
#define sz size()
#define pb(a) push_back(a)
#define mset(a,v) memset(a,v,sizeof(a))
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mi;
typedef vi::iterator it;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef pair<string,int> psi;
typedef vector<psi> vpsi;
typedef queue<int> qi;
typedef queue<pii> qpii;
typedef unsigned long long ubig;
typedef long long big;
typedef long double bigd;
template<class T> string tos(T x){stringstream ss; ss<<x; return ss.str();}
int Draw,Ivan,Zmey;
vpii v1,v2;
int i,h,t,r,m,n;
class Substitute
{
public:
};
void solve()
{
queue<pair<pair<int,int>,int> > q;
bool vis[1000][1000];
mset(vis,0);
pair<pair<int,int>,int> start(pair<int,int>(h,t),0),cur;
q.push(start);
int cc,ch,ct;
while(!q.empty())
{
cur=q.front();
cc=cur.second;
ch=cur.first.first;
ct=cur.first.second;
q.pop();
if(vis[ch][ct])
{
Draw=true;
}
else if(ch+ct>r)
{
Zmey=cc;
}
else if(!ch && !ct)
{
Ivan=cc;
return;
}
else
{
vis[ch][ct]=true;
int k,l;
rep( k , min(n,ch) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch-(k+1)+v1[k].first,ct+v1[k].second),cc+1));
rep( l , min(m,ct) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch+v2[l].first,ct-(l+1)+v2[l].second),cc+1));
}
}
}
int main()
{
cin>>h>>t>>r>>n;
v1.resize(n);
rep(i,n)cin>>v1[i].first>>v1[i].second;
cin>>m;
v2.resize(m);
rep(i,m)cin>>v2[i].first>>v2[i].second;
solve();
if(Ivan)cout<<"Ivan\n"<<Ivan<<endl;
else if(Draw)cout<<"Draw\n";
else cout<<"Zmey\n"<<Zmey<<endl;
return 0;
}
[/code]
iam using bfs
Please, edit your post.
Is there anyone know the test 6 for Problem C?thx
Если тест велик, то его можно кинуть сюда. :)
Заранее спасибо!
B: 5?
C: 8, 9, 17, 19, 25
D: 4, 9, 11
E: 4, 11, 25, 46
H: 9