Обсуждение @ 1821. Биатлон @ Timus Online Judge

Mikhail accepted // Задача 1821. Биатлон 22 июн 2018 17:20

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

vector< tuple <int, int, string> > v;
vs ans;

int calc() {
    string ans;
    cin >> ans;
    re (ans[0] - '0') * 6000 + (ans[1] - '0') * 600 + (ans[3] - '0') * 100 + (ans[4] - '0') * 10 + (ans[6] - '0');
}

int main() {
    int best = (int) 1e9, n, cur;
    cin >> n;
    string str;
    fo(i, n) {
        cin >> str;
        cur = calc();
        v.pb(make_tuple(cur + i * 300, cur, str));
    }
    sort(all(v));
    int finish, res;
    fo(i, v.size()) {
        tie(finish, res, str) = v[i];
        if (res < best) {
            best = res;
            ans.pb(str);
        }
    }
    sort(all(ans));
    cout << ans.size() << endl;
    for (auto &j : ans) cout << j << '\n';
    re 0;
}

Edited by author 22.06.2018 17:22

panLevan What is test #4? [2] // Задача 1821. Биатлон 5 май 2013 15:15

Denis Astanin (KPI) WA 8? [3] // Задача 1821. Биатлон 19 мар 2011 16:52

Milovanov Maxim Why WA 2 ? [12] // Задача 1821. Биатлон 19 мар 2011 15:50

Give me test 2

MOPDOBOPOT (USU) Re: Why WA 2 ? [11] // Задача 1821. Биатлон 19 мар 2011 17:33

3
Masha 91:0.0
Sasha 90:0.0
Vasya 3:0.0

ans:
1
Vasya

Edited by author 20.03.2011 12:37

Milovanov Maxim Re: Why WA 2 ? [1] // Задача 1821. Биатлон 19 мар 2011 17:39

Thank

Amrodis Re: Why WA 2 ? // Задача 1821. Биатлон 19 мар 2011 18:11

Edited by author 22.03.2011 02:51

daftcoder [Yaroslavl SU] Re: Why WA 2 ? [3] // Задача 1821. Биатлон 19 мар 2011 18:40

Bot not only Vasya?

My AC program says
1
Vasya

==
BTW check test
5
E 1:20.0
D 1:10.0
C 0:30.0
B 0:20.0
A 0.10.0

Ans should be
4
A
B
C
E

Amrodis Re: Why WA 2 ? // Задача 1821. Биатлон 19 мар 2011 19:02

My solution also says
1
Vasia

and for the BTW check test the same answer.
but i have wa 4.

please give me some other examples.
thanks.

MOPDOBOPOT (USU) Re: Why WA 2 ? // Задача 1821. Биатлон 20 мар 2011 12:39

I'm sorry, of course the answer will be
1
Vasya

BiteBoy [ONU] Re: Why WA 2 ? // Задача 1821. Биатлон 27 июл 2011 20:46

To daftcoder [Yaroslavl SU]:
Your test has a mistake in the last line. It should be like this:
5
E 1:20.0
D 1:10.0
C 0:30.0
B 0:20.0
A 0:10.0

Edited by author 27.07.2011 20:48

daminus Re: Why WA 2 ? [3] // Задача 1821. Биатлон 1 мар 2012 22:22

MOPDOBOPOT (USU) писал(a) 19 марта 2011 17:33

3
Masha 91:0.0
Sasha 90:0.0
Vasya 3:0.0

ans:
1
Vasya

Edited by author 20.03.2011 12:37

It is not TRUE!!!!!!!!!!!!!!!!!!

ramon93i7 Re: Why WA 2 ? [2] // Задача 1821. Биатлон 24 авг 2012 20:28

It's obviously true.

Furhat Re: Why WA 2 ? // Задача 1821. Биатлон 20 ноя 2012 11:56

Furhat Re: Why WA 2 ? // Задача 1821. Биатлон 20 ноя 2012 12:04

Edited by author 20.11.2012 12:16

Andros Re: Why WA 2 ? // Задача 1821. Биатлон 18 июн 2014 18:52

MOPDOBOPOT (USU) писал(a) 19 марта 2011 17:33

3
Masha 91:0.0
Sasha 90:0.0
Vasya 3:0.0

But in the statement it says it's in MM:SS.D format, so shouldn't it be 91:00.0, 03:00.0, etc.?

Testme HelpPlease (Java) // Задача 1821. Биатлон 18 мар 2014 00:37

What is wrong with mycode? it is working in mycomputer but failing in test2

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* Created by sherxon on 3/17/14.
*/
public class Biathlon {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=Integer.parseInt(in.nextLine());
        String s, name, time;
        Double min, sec;
        int j=0;
        List<String> a= new ArrayList();
        ArrayList<Double> b= new ArrayList();
        int thirty=0;

           for (int i = 0; i <n ; i++) {

               s = in.nextLine();

            name=s.split(" ")[0];

            sec=Double.parseDouble(s.split(" ")[1].split(":")[1])+60*(Double.parseDouble(s.split(" ")[1].split(":")[0]));
               sec+=thirty;
               //System.out.println(sec);
               double eachsec=0.0;
               double eachsecs=0.0;
                boolean bl=true;

               for (int k = 0; k<a.size() ; k++) {
                 // System.out.println(sec-thirty + " " + (b.get(k)-eachsec) + " " +(sec) + " " + b.get(k));

                   if(sec-thirty<b.get(k)-eachsec&&sec<b.get(k)){
                       b.remove(k);
                       a.remove(k);
                       k--;
                   }
                   eachsec+=30;
               }
               for (int k = 0; k <a.size() ; k++) {
                   if(sec-thirty>b.get(k)-eachsecs){
                       bl=false;
                   }
                   eachsecs+=30;
               }
                if(bl){
               a.add(name);
               b.add(sec);
                }

               thirty+=30;
        }
        Collections.sort(a);
        System.out.println(a.size());

        for (int i = 0; i <a.size() ; i++) {
            System.out.println(a.get(i));
        }
    }
}

Лерник Казарян WHAT IS TEST #17 // Задача 1821. Биатлон 26 дек 2013 19:20

Iuhenio{PSU} WHY "Runtime error" ????!!!!!! // Задача 1821. Биатлон 12 фев 2013 23:06

using System;
class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        if (N > 0 && N <= 100)
        {
            string[,] IData = new string[N, 3];
            string[] buf = new string[2];

            for (int i = 0; i < N; i++)
            {
                buf = Console.ReadLine().Split(' ');
                IData[i, 0] = buf[0];
                IData[i, 1] = buf[1];
                IData[i, 2] = Convert.ToString(i + 1);
            }

            String[] Win = new string[N];
            string[] Lider = new string[2];
            Lider = IData[0, 1].Split(':');
            int k = 0;

            for (int i = 1; i < N+1; i++)
            {
                buf = IData[i, 1].Split(':');
                if (int.Parse(Lider[0]) > int.Parse(buf[0]))
                {
                    if (i == 1 && (60 - double.Parse(buf[1].Replace(".", ",")) + double.Parse(Lider[1].Replace(".", ",")) < 30))
                    {
                        Win[k] = IData[0,0];
                        k++;
                    }
                    Win[k] = IData[i, 0];
                    k++;
                    Lider = IData[i, 1].Split(':');

                }
                if (int.Parse(Lider[0]) == int.Parse(buf[0]))
                {
                    if (double.Parse(Lider[1].Replace(".", ",")) > double.Parse(buf[1].Replace(".", ",")))
                    {
                        double tmp = double.Parse(Lider[1].Replace(".", ",")) - double.Parse(buf[1].Replace(".", ","));
                        if (i == 1 && tmp < 30)
                        {
                            Win[k] = IData[0, 0];
                            k++;
                        }
                        Win[k] = IData[i, 0];
                        k++;
                        Lider = IData[i, 1].Split(':');
                    }
                }
                if (int.Parse(Lider[0]) < int.Parse(buf[0]))
                {
                    Win[k] = IData[0, 0];
                    k++;
                }
            }
            Console.WriteLine(k);
            Array.Sort(Win);
            for (int i = 0; i < k; i++)
            {
                Console.WriteLine(Win[i]);
            }
        }
    }
}

Edited by author 12.02.2013 23:07

Bpgdan Spilniy Решение [4] // Задача 1821. Биатлон 19 мар 2011 21:12

DENISKA(SSAU) what WA#22 ? [1] // Задача 1821. Биатлон 19 мар 2011 16:27

green_smile Help PLEASE, i don't understand [1] // Задача 1821. Биатлон 9 окт 2012 23:25

input
6
Zaitseva 21:38.2
Hauswald 21:21.0
Boulygina 22:04.4
Henkel 22:06.1
Wilhelm 21:11.1
Jonsson 22:05.8
My program:
4
Hauswald
Henkel
Wilhelm
Zaitseva

explain me please what's wrong???
why Henkel isn't in Test?

green_smile Re: Help PLEASE, i don't understand // Задача 1821. Биатлон 9 окт 2012 23:27

it's code

program z1821;
var n,i,j,m,x,max,ol:integer;
s,s1:string;
names:array[1..100]of string;
times:array[1..100]of integer;
reznames:array[1..100] of string;

begin
readln(n);
j:=1;
for i:=1 to n do begin
    readln (s);
    while s[j]<>' ' do begin
    inc(j);
    end;
    names[i]:=copy(s,1,j);    //
    delete(s1,1,length(s1)); //
    s1:=copy(s,j+1,2);        //
    val(s1,times[i],ol);      //
    delete(s1,1,2);           //
    s1:=copy(s,j+4,2);        //
    times[i]:=times[i]*600;   //
    val(s1,x,ol);             //
    times[i]:=times[i]+x*10; //
    delete(s1,1,1);           //
    s1:=copy(s,j+7,1);        //
    val(s1,x,ol);             //
    times[i]:=times[i]+x;     //
    j:=1;                     //it's input, don't look on it =)
end;
    for i:=2 to n do
    times[i]:=times[i]-300*(i-1);
    max:=times[1]+1;
    m:=0;
j:=1;
    for i:=1 to n do begin
        if times[i]<max then begin
            max:=times[i];
            reznames[j]:=names[i];
            m:=m+1;
      j:=j+1;
        end;
    end;

        for i := 1 to m-1 do
        for j := 1 to m-i do
            if reznames[j] > reznames[j+1] then begin
                s1 := copy(reznames[j],1,length(reznames[j]));
                reznames[j] :=copy(reznames[j+1],1,length(reznames[j+1]));
                reznames[j+1] :=copy(s1,1,length(s1));
            end;
writeln(m);
    for i := 1 to m do
        writeln(reznames[i]);
end.

Edited by author 09.10.2012 23:47

Dima help [1] // Задача 1821. Биатлон 1 авг 2012 04:48

Andrew Sboev WA6 [2] // Задача 1821. Биатлон 28 апр 2012 16:22

Geeks_Club Why wa1? [6] // Задача 1821. Биатлон 19 мар 2011 14:47

My answer to the example is as follows:
3
Hauswald
Wilhelm
Zaitseva

Check my solution please !

Nathalie Re: Why wa1? [4] // Задача 1821. Биатлон 19 мар 2011 14:50

Maybe you have extra spaces in the end of each line?

SmartCoder Re: Why wa1? [3] // Задача 1821. Биатлон 19 мар 2011 14:54

the same i think my solution is true and no extra spaces

Geeks_Club Re: Why wa1? [2] // Задача 1821. Биатлон 19 мар 2011 18:17

why is wa 1? here the code of the my solution pleas chek:
uses
SysUtils,math;

Type m = record
     name:string[21];
     min:integer;
     seconds:real;
     pos:integer;
end;
Var n,i,c:integer;
   tmp:string;
   mas:array[1..101]of m;
   tmpG1:m;
   j,Size,k:integer;
   TopName:array[1..101] of m;
   t:m;

function CompareStr1(const S1, S2: string): Integer; assembler;
asm
        PUSH    ESI
        PUSH    EDI
        MOV     ESI,EAX
        MOV     EDI,EDX
        OR      EAX,EAX
        JE      @@1
        MOV     EAX,[EAX-4]
@@1:    OR      EDX,EDX
        JE      @@2
        MOV     EDX,[EDX-4]
@@2:    MOV     ECX,EAX
        CMP     ECX,EDX
        JBE     @@3
        MOV     ECX,EDX
@@3:    CMP     ECX,ECX
        REPE    CMPSB
        JE      @@4
        MOVZX   EAX,BYTE PTR [ESI-1]
        MOVZX   EDX,BYTE PTR [EDI-1]
@@4:    SUB     EAX,EDX
        POP     EDI
        POP     ESI
end;
function timeCompare(m1:integer;S1:real;d1:integer; m2:integer; s2:real; d2:integer):boolean;
Var ch:boolean;
begin
if (m1+(floor(d1+s1) div 60))>(m2+(floor(d2+s1) div 60)) then
begin
ch:=true;
end
else if(m1+(floor(d1+s1) div 60))=(m2+(floor(d2+s1) div 60))
then
   begin
   if (s1+d1-(floor(s1+d1) div 60)*60)>(s2+d2-(floor(s2+d2) div 60)*60) then ch:=true
   else ch:=false;
   end
else ch:=false;
result:=ch;
end;

begin
readln(n);
for i:=1 to n do
begin
    readln(tmp);
    mas[i].name:=Copy(tmp,1,pos(' ',tmp)-1);
    Delete(tmp,1,pos(' ',tmp));
    Val(copy(tmp,1,pos(':',tmp)),mas[i].min,c);
    Delete(tmp,1,pos(':',tmp));
    Val(tmp,mas[i].seconds,c);
    mas[i].pos:=i-1;
end;
tmpG1:=mas[1];
TopName[1]:=Mas[1];
j:=1;
for i:=2 to n do
if timeCompare(TmpG1.min,TmpG1.seconds,TmpG1.pos*30, Mas[i].min,Mas[i].seconds,Mas[i].pos*30){Min>mas[i]} then
begin
for k:=j downto 1 do
   if timeCompare(TopName[k].min,TopName[k].seconds,TopName[k].pos*30,Mas[i].min,Mas[i].seconds,Mas[i].pos*30) then dec(j);
   inc(j);
   TopName[j]:=Mas[i];
end
else
   if timeCompare(TmpG1.min,TmpG1.seconds,0,Mas[i].min,Mas[i].seconds,0) then
   begin
    inc(j);
    TopName[j]:=Mas[i];
    tmpG1:=mas[i];
   end;

Size:=j;
for i:=1 to Size do
for j:=1 to Size do
begin
if CompareStr1(TopName[i].name,TopName[j].name)<0 then
    begin
    t:=TopName[i];
    TopName[i]:=TopName[j];
    TopName[j]:=t;
    end;
end;
writeln(size);
for i:=1 to size do
writeln(Topname[i].name);
end.

Nikita++ Re: Why wa1? [1] // Задача 1821. Биатлон 19 мар 2011 18:42

Don't you think that your code is too long and it is difficult to understand?

psych069 Re: Why wa1? // Задача 1821. Биатлон 4 апр 2011 22:45

For sure u guys r not the only ones with that problem >.<

After i sent my solution i took WA at #1,
then i posted :
#include <iostream>
using namespace std;
int main()
{
cout << "3\nHauswald\nWilhelm\nZaitseva" ;
return 0;
}
and i took WA at #2;

Compiled both sources on my machine and the console output was exactly one and the same Q.Q
Give us a clue please!
Regards, B.P. !

zaycakitayca Re: Why wa1? // Задача 1821. Биатлон 5 май 2012 17:24

I don't understand well why it works, but when i've changed variable type for sportsmens counting from unsigned char to unsigned short, i've passed this test (despite of maximal count is 100, and correct input/output in my program). I think that if u have any troubles with it, u should try some different variable types and output commands

Enigma [UB of TUIT] Help please!!! I'dont understant problem!!! [4] // Задача 1821. Биатлон 12 сен 2011 15:21

Why input
6
Zaitseva 21:38.2
Hauswald 21:21.0
Boulygina 22:04.4
Henkel 22:06.1
Wilhelm 21:11.1
Jonsson 22:05.8
Answer:
3
Hauswald
Wilhelm
Zaitseva???????/

xerxe Re: Help please!!! I'dont understant problem!!! [3] // Задача 1821. Биатлон 14 дек 2011 17:04

I found the explanation a bit below: for a contestant to be in the answer, their time must be better than all the previous ones.
Complication: more than 1 contestant can be on the track at the same time.

I only just realized this. It is very frustrating to not understand the problem requirements, and to code something which turns out to be incorrect.

Edited by author 14.12.2011 17:20

OmarOthman Re: Help please!!! I'dont understant problem!!! [2] // Задача 1821. Биатлон 14 дек 2011 22:05

Please elaborate more, xerxe. I speak perfect English and yet I don't understand the wording of the problem!!

Edited by author 14.12.2011 22:07

xerxe Re: Help please!!! I'dont understant problem!!! [1] // Задача 1821. Биатлон 16 дек 2011 19:19

The problem states that contestants start each 30 seconds. Let's say that running times are:
- Runner1 30:00.0 (starting at 0:00.0, finishing at 30:00.0)
- Runner2 29:31.0 (starting at 0:30.0, finishing at 30:01.0)
This means that
- Runner1 has the best time after 30 minutes from the start of the race
- Runner2 has the best time, 1 second after Runner1
So they are both in the top.
However, if:
- Runner1 30:00.0 (starting at 0:00.0, finishing at 30:00.0)
- Runner2 29:29.0 (starting at 0:30.0, finishing at 29:59.0)
Then Runner2 finishes BEFORE Runner1, so Runner1 will never have a best time.

An explanation for the problem sample is a bit below (http://acm.timus.ru/forum/thread.aspx?id=26847&upd=634557023855807397). For me, it was easier to explain on this other example.

Hope this is clear, good luck!

P.S.: I see you already have AC, congratulations!

Edited by author 16.12.2011 19:35

Jumabek_Alihonov Re: Help please!!! I'dont understant problem!!! // Задача 1821. Биатлон 18 апр 2012 19:24

thank you xerxe for clearly explaination

DarkJedi WA #14 // Задача 1821. Биатлон 6 ноя 2011 13:29

DarkJedi Test 3 and 14 // Задача 1821. Биатлон 5 ноя 2011 16:47

liushujia How many names should I print every time？ [3] // Задача 1821. Биатлон 7 авг 2011 12:46

Uzbek boy WA #2 ? [1] // Задача 1821. Биатлон 11 окт 2011 03:25

Leonid (SLenik) Andrievskiy I thought test #4 wass conflicting with the description of the problem - I was wrong // Задача 1821. Биатлон 7 июн 2011 22:50

Nikita Sivukhin What test #19?? // Задача 1821. Биатлон 20 мар 2011 22:44

Обсуждение задачи 1821. Биатлон