Проверяйте пограничные ситуации, когда номер билета на входе 000000 или 999999

double check lazy calculations

Edited by author 25.10.2012 03:55

deleted

Edited by author 26.10.2021 22:50

I think my idea completely right What's wrong??????


import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        String s[][] = new String[n][3];
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                s[i][j] = in.next();
            }
        }
        boolean all[][] = new boolean[n][3];
        String ss[][] = new String[3*n][3*n];
        ss[0][0] = "Isenbaev";
        int []index = new int[3*n];
        for(int i=0;i<n;i++){
            index[i] = 0;
        }
        index[0] = 1;
        int d = 1;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))all[i][j] = true;
            }
        }
        boolean BOR = false;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))BOR = true;
            }
        }
        for(int q=0;q<3*n;q++){
            boolean bormi = false;
            for(int i=0;i<n;i++){
                boolean bor = false;
                for(int j=0;j<3;j++){
                    for(int t=0;t<index[d-1];t++){
                        if(ss[d-1][t].equalsIgnoreCase(s[i][j])){
                            bor = true;
                            break;
                        }
                    }if(bor)break;
                }
                if(bor){
                    for(int j=0;j<3;j++){
                        if(!all[i][j]){
                            ss[d][index[d]++] = s[i][j];
                            all[i][j]  = true;
                            bormi = true;
                            for(int g=0;g<n;g++){
                                for(int h=0;h<3;h++){
                                    if(s[g][h].equalsIgnoreCase(s[i][j]))all[g][h] = true;
                                }
                            }
                        }
                    }
                }
            }
            if(bormi)d++;
        }
        String []sss = new String[3*n];
        int []son = new int[3*n];
        for(int i=0;i<3*n;i++){
            son[i] = -1;
        }
        int koef = 0;
        for(int i=0;i<d;i++){
            if(i==0){
                if(BOR){
                    BOR = false;
                }else i++;
            }
            for(int j=0;j<index[i];j++){
                sss[koef] = ss[i][j];
                son[koef++] = i;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(!all[i][j]){
                    boolean top = true;
                    for(int p=0;p<koef;p++){
                        if(sss[p].equalsIgnoreCase(ss[i][j]))top = false;
                    }
                    if(top)sss[koef++] = s[i][j];
                }
            }
        }


        n = koef;
        for(int i=0;i<n-1;i++){
            if(sss[i].compareTo(sss[i+1])>0){
                String S = sss[i];
                sss[i] = sss[i+1];
                sss[i+1] = S;
                int SS = son[i];
                son[i] = son[i+1];
                son[i+1] = SS;
                i=-1;
            }
        }

        for(int i=0;i<koef;i++){
            if(son[i]!=-1)System.out.println(sss[i] + " " + son[i]);
            else System.out.println(sss[i] + " undefined" );
        }
    }
}

Edited by author 25.07.2018 00:30

Edited by author 27.07.2018 23:09

You can make this problem even harder by setting TL to 1s. My current solution runs in 0.96s and there are two optimizations that aren't too hard to come up with that can speed up program significantly (probably sub 0.1s).

Firstly, for any complete graph on N vertices the answer is 2^N.
Secondly, if you program has TL issues look up 3-regular graphs, they are the worst case of my algorithm.

My solution uses no random, there is a nice deterministic solution, i.e. no hashes or shuffling.

The following tests should be enough to get rid of all WAs

Tests:

3
001
000
100

Answer: 5

6
000001
001001
010000
000001
000000
110100

Answer: 11

6
010010
101010
010100
001011
110100
000100

Answer: 15

4
0011
0000
1001
1010

Answer: 9

4
0110
1011
1101
0110

Answer: 12

4
0001
0000
0000
1000

Answer: 6

10
0001111111
0011111111
0101111111
1110111101
1111011110
1111100111
1111100111
1111111000
1110111001
1111011010

Answer: 195

7
0111101
1011110
1100111
1100111
1111000
0111001
1011010

Answer: 39

Edited by author 24.07.2018 19:09

> I use the segment tree,but I can't find anything wrong...
> Could you please give me some tests so that I can find out my program's problem?
> Thank you.

But now I got WA #5,and I have considered the following tests:
6
+ 9
- 3
- 3
+ 3
+ 3
+ 3
And I think the answer is:
9
9
9
9
9
3
But I still WA #5,Could someone can give me some hints or some tests?

Edited by author 20.06.2013 10:52

Edited by author 20.06.2013 10:52

#include <iostream>

using namespace std;

int main(){
    int n(0),m(0),last(0),temp_f(0),temp_s(0),end_(0);
    cin >> n >> m;
    for(int i = 0;i<n;++i){
        cin >> temp_f >> temp_s;
        last += temp_f-2-temp_s;
    }
    end_ = last + (m - 2);
    if(end_ < 0)cout << "Big Bang!";
    else cout << end_;

    return 0;
}

can I import the numpy library

type
a = array[1..50000] of integer;
b = array[1..50000] of integer;


  Var c,d,i,k,g: integer;
  Var n: a; Var p: b;

  begin
  d:= 0;
  read(c);
  for i:= 1 to c do read(n[i]);
  read(k);
  for i:= 1 to k do read(p[i]);

  for i:=1 to c do
  for g:=1 to k do
  begin
  if (n[i] + p[g] = 10000) then
  begin
  writeln('YES');
  exit;
  end
  else if (i = c) and (g = k) and (n[i] + p[g] <> 10000) then
  begin
  writeln('NO');
  exit;
  end;
  end;
  end.

Also pay attention to the fact that according to the example - segment is (a;b]. I used this approach and got accepted. (O (N*N) btw :) )

think the four edges as four mirror...... :)

I think this is very interesting and hard problem
so who can tell me the solution of this problem
what is the author's solution

I've used Ford-Fulkerson algo and got TL on test 22.(in java)

What is the O(N^2) solution of this problem?

I wrote simply Kraskal & DFS with assimptoty O(E * Log(E) + V * E) and got Accepted in 1.156... I want to know O(N^2) solution of this problem...

Подскажите, добрые люди, как же сделать так, чтобы не отправлять по сто раз решения на сервер, чтобы узнать работают они или нет.. для этого нужно отлаживать программу с помощью текстовых файлов, как же с ними работать?
для паскаля в руководстве написано вот это:
var
   a, b: longint;
begin
{$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
{$ENDIF}
   readln(a, b);
   writeln(a + b);
{$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
{$ENDIF}
end.
может кто-нибудь написать такую же для python3???

What answer on test
10 2.0
5 10 0 -1
5 -10 0 1
?

I think answer "Yes"

Give me some tests

Edited by author 20.07.2018 19:14

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int n,k=0;
    char t,s;
    cin>>n;
    string a[1001];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-1;i++)
    {
        t=a[i][0];
        s=a[i+1][0];

        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='A' || s=='P' || s=='O' || s=='R'))
           k+=0;
        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='B' || s=='M' || s=='S'))
           k+=1;
        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=2;

        if((t=='B' || t=='M' || t=='S') &&
           (s=='B' || s=='M' || s=='S'))
           k+=0;
        if((t=='B' || t=='M' || t=='S') &&
           (s=='A' || s=='P' || s=='O' || s=='R'||
            s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=1;

        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=0;
        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='B' || s=='M' || s=='S'))
           k+=1;
        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='A' || s=='P' || s=='O' || s=='R'))
           k+=2;
    }

    cout<<k;
    return 0;
}

Edited by author 27.07.2018 02:09