Can someone give me some tests? I have a greedy solution.

as topic says^^

Hi,

I looked through the archive of old online contests here at Timus and got intrested in how the scores are calculated. Any one who can give me a pointer to information on this? Would be nice to know how the competitions are set up also (how long are they open etc).

/Robert

Can anyone that had problem with test #10 help me pass it? I've been trying for a few hours and I can't find where am I mistaken.

my solution

#include<string>
#include<iostream>
using namespace std;
int main()
{char a[4][4],c[4][4];
int  b[4][4],i,j,t;


for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
cin>>c[i][j];
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)

cin>>a[i][j];
cout<<endl;
//1 qator
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='X')
cout<<a[i][j];
//2-qator
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='X')
  c[j][5-i]='1';


  for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='1')
cout<<a[i][j];

//3-qator

for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='1')
c[j][5-i]='2';

for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='2')
cout<<a[i][j];

for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='2')
c[j][5-i]='3';
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
if(c[i][j]=='3')
cout<<a[i][j];
}

Suppose
* n in uneven,
* the first (n-1)/2 seats and the last (n-1)/2 seat has the same number of people already sitting and
* the person sitting in seat (n+1)/2 arrives.
The description does not say if he will choose left or right.
I got AC by assuming he will not choose the same side as Vasya.

Edited by author 23.09.2011 20:23

Notice that there are 18*3=54 participants, 64bit-type should be used for masks.

Test my code, please.


#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int N;

bool proverka(vector <int> &used, queue <int> &Q){
    if (!Q.empty()) return true;
    for (int i=0;i<N;i++)
        if (!used[i]) return true;
    return false;
}

int main(){
    cin>>N;
    vector <int> T1(N);
    vector <int> T2(N);
    vector <int> T3(N);
    for (int i=0;i<N;i++)
        cin>>T1[i]>>T2[i]>>T3[i];
    vector <int> used(N,0);
    queue <int> Q;
    int res=0;
    int tres=0;
    for (int m=0;m<4*N;m++){
        int t=-1;
        for (int i=0;i<N;i++)
            if (!used[i] && (t==-1 || T1[i]<T1[t]))
                t=i;

        //cout<<t+1<<": "<<T1[t]<<" "<<T2[t]<<" "<<T3[t]<<" "<<Q.front()<<endl;
        if (Q.empty() && t==-1)
            continue;

        if (Q.empty()){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[i]=1;
                    }
                }
            continue;
        }

        if (t==-1){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            Q.pop();
            continue;
        }

        if (T1[t]<T2[Q.front()]){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            T2[Q.front()]-=T1[t];
            if (T2[Q.front()]<=0)
                Q.pop();
            continue;
        }

        if (T1[t]>T2[Q.front()]){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            for (int i=0;i<N;i++)
                if (!used[i]){
                    T1[i]-=T2[Q.front()];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            Q.pop();
            continue;
        }

    }

    cout<<tres<<endl;
    return 0;
}

To pass this test you should use int64 or long long.Good luck!

I've really learned much more about Gauss integers while solving this problem. I didn't even suspect that most of algebraic theorems and definitions  also take place in complex algebra (I mean Gauss integers, of course). Great thanks to authors for creating that.
For anyway, this test helped me to pass WA#21:
3
2 1 3 5 0 0
4 0 5 0 6 0
0 1 -5 -1 8 12
0 9
One of possible answers is -1 -3

I keep getting WA for test #7, any tips?

when m=1, the answer must be 0, but my AC submission's answer is 1!!

Edited by author 22.09.2011 18:12

program sdf;
var i,j,k,l,n,m,max:longint;
    a:array[1..58]of longint;
    str,str1:ansistring;
begin
    //while not eof do begin
        readln(str);
        for i:=1 to length(str) do
          inc(a[ord(str[i])-64]);
        max:=0;
        for i:=1 to 58 do
        if max<a[i] then
        max:=a[i];
        for i:=1 to length(str) do
        if a[ord(str[i])-64]=max then begin
            write(str[i]);
            a[ord(str[i])-64]:=-1;
        end;
        writeln;
    //end;
end.

It's 1-st point and two others.

Edited by author 22.09.2011 15:24

can U tell me why?

can U tell me why?

What is test No. 6 ?

Not clearly... The Data goes in the char arr[] without " "? 121314162023242625? Two sign numbers?
Early thank you very much!