I need help with code 1409:

#include <stdio.h>
int main()
{
    int a,b,c,d;
    scanf("%d%d",&a,&b);
    printf("%d\n",c=10-a,d=10-b, c+d<10);
    scanf("%d%d",&c,&d);
    getchar(), getchar();
    return 0;
}

Confusing question: HOW ARE THE BLANKS CHOSEN?

Let's see example
2 3 4 - initial blanks
I choose blanks 2 and 4 - they are different so I cut off piece of length 2 from the long blank (4).
After that we have blanks: 2 3 2 - two blanks coincide so one is eliminated: 2 3 they are different so we cut of blank with length 3. We have: 2 1. Cut again we have 1 1. Eliminate one blank and we get a result - 1.

You may try other ways to choose blank - but you will get same answer. So,
NO MATTER HOW TO CHOOSE 2 blanks.

Moral: What is not said does not matters ;)

By the way algorithm is very very easy... try to think

don't use longint. do it using int64

I know English bad and ask the question in Russian too.

1. I got AC with using "*2": ET = 0.015 s;
2. I replaced "*2" to "shl 1": ET = 0.001 s;
3. I tried to replace "(n-1)" to "Prev(n)": ET = 0.015 s;
4. I returned "(n-1)" instead "Prev(n)": ET = 0.015 s;

Code #4 and code #2 are identical but ET different. Why?

In Russian.

Теперь по-русски.
Прогу написал, послал -- ответ положительный, время выполнения 0,015 сек.
Заменил умножение на 2 смещением влево на 1: время выполнения 0,001 сек.
Заменил вычитание на Pred(n): Время опять 0,015;
Вернул все как было, а время выполнения не поменялось. Почему, кто скажет.

Edited by author 02.10.2010 21:48

Why WA15?
I use binarysearch in the range [-2*10^9;2*10^9]

My program seems to work correctly on all tests I tried, including all the tests that could be found in topics of this problem's discussion. Nevertheless, I always have WA #1 when I submit it as a solution, so I guess something is wrong not with the algorithm, but with I/O code. Here it is (I know that the rules of the board deny posting code, but this is only input/output code, no part of algorithm is exposed):

int main(int argc, char **argv){
  int n;
  std::cin >> n;

  Labyrinth lab(n);

  for(int i = 0; i < n; i++){
    std::string s;
    std::getline(std::cin, s);
    // strip the last linebreak, if any
    if(s[s.length() - 1] == '\n') s.resize(s.length() - 1);
    // if the string is empty
    // (for example,  after reading the
    // number from the first line),
    // reread it (modifying the current line index)
    if(s.length() == 0) { i--; continue; }
    for(int j = 0; j < n; j++){
      if(s[j] == '#') lab.add_wall_block(j, i);
    }
  }
  std::cout << 9 * lab.total_walls_visible() << std::endl;
  return 0;
}

(if the formatting is broken, here is the alternative: http://itpaste.ru/92461 )

Edited by author 01.10.2010 13:49

Edited by author 01.10.2010 12:24

Thanks to author

with TL < 0.25 it's more interesting, and that's enough even for Java && C#

This problem can be solved by equations, for example
we make equations for the input:

3
1 2 -1
1 2 3 -1
3 -1

whe construct the matrix

1 1 0 = 1
1 1 0 = 1
0 1 1 = 1

since 1st and 2nd equations are the same, it means that
you are free to choose the value for the 3rd variable,
but in fact if you choose its value arbitrarily,
answer length can be changed, two possible answers
are 1,2 and 3, but only 3 is the right answer, because
it's the shortest. What to do with that?

use array bigger then 100000, i used 101000 and got AC, with 100000 WA11

cheers

Does anyone know this test? Or at least can you say what figure is it?
My prog solves a problem even with ellipses and rectangles, because I don't know whether it should or not.

Edited by author 28.09.2010 01:34

I had WA 12, now I have WA 17. I still need your help!

Edited by author 28.09.2010 22:23

KMP, on test 17 I got WA, where is problem in this test?

anobody have any ideas ? i tested all from forum + generated, all are correct. code :

# include <iostream>

# include <vector>

# include <algorithm>

# include <cstdlib>

# include <string>

# include <map>

# include <climits>

# include <cmath>

# include <iomanip>
# include <queue>
# include <sstream>





# define LOOP(i,s,e) for(int i=s; i<e; ++i)



using namespace std;


struct P
{
    int x,y;
    int t;
    P(int a, int b): x(a),y(b) {};
    P() { P(0,0); }
};

int ar[12][12] = {0};
queue<P> que;

void go(int x , int y, string ch)
{
    if(ar[x][y] == 1)
    {
        cout << ch;
        que.push( P(x,y) );
        ar[x][y] = 0;
    }
}

void first(int n)
{
    int a,b;

    if (n == 0) cout << ".";
    else if (n == 1)
    {
        cin >> a >> b;
        cout << a << " " << b << endl << ".";
    }
    else
    {

        LOOP(i,0,n)
        {
            cin >> a >> b;
            if (i == 0) que.push( P(b,a) );
            ar[b][a] = 1;
        }

        cout << que.front().y << " " << que.front().x << endl;
        ar[que.front().x][que.front().y] = 0;

        while(!que.empty() )
        {
            P t = que.front();
            que.pop();

            go(t.x, t.y+1, "R");
            go(t.x-1, t.y, "B");
            go(t.x, t.y-1, "L");
            go(t.x+1, t.y, "T");

            cout << (que.empty() ? ".":",") << endl;
        }
    }
}

bool cmp(const P& a, const P& b)
{
    if (a.x == b.x) return (a.y < b.y);
    else return (a.x < b.x);
}

void calcule(string tmp, queue<P>& que, vector<P>& vec)
{
    P t = que.front();
    que.pop();
    vec.push_back( P(t.y, t.x) );

    LOOP(i,0,tmp.size()-1)
    {

        if (tmp[i] == 'T')  que.push( P(t.x+1, t.y) );
        else if (tmp[i] == 'R')  que.push( P(t.x, t.y+1) );
        else if (tmp[i] == 'B')  que.push( P(t.x-1, t.y) );
        else if (tmp[i] == 'L')  que.push( P(t.x, t.y-1) );

       // cout << tmp[i] << endl;
      //  cout << que.back().x << " " << que.back().y << endl;
    }
}

void second(int a, int b)
{
    string tmp;
    que.push( P(a,b) );

    vector<P> vec;

    while (42)
    {
        getline(cin, tmp);
        calcule(tmp, que, vec );
        if (tmp.find('.', 0) != string::npos) break;
    }
    sort(vec.begin(), vec.end(), cmp);
    cout << vec.size() << endl;

    LOOP(i,0,vec.size())
    {
        cout << vec[i].x << " " << vec[i].y << endl;
    }
}


int main()

{
    string str;
    getline(cin, str);
    for (int i=str.size()-1; i>=0; --i)
    {
        if (str[i] == ' ') str.erase(str.begin() +i);
        else break;
    }

    istringstream st(str);
    if (str.find(' ', 0) == string::npos)
    {
        int n;
        st >> n;
        first(n);
    }
    else
    {
        int a,b;
        st >> a >> b;
        second(b,a);
    }


    exit(0);

}

Test 2 is the case that output is 0.
For example:
Input
a - a
b
Output
0
(My output was nothing)

Test 4 is the case that some power would be 0.
For example:
Input
a^00 - b
1 - b*b^0
Output
b^2 - 2*b + 1

Good luck.

when I changed

char buf[100];
cin.getline(buf, 100);

to

char buf[1000];
cin.getline(buf, 1000);

I got AC, but problem statement says that polynom's length is no longer than 100 characters.

I got WA37 in 1285
and AC on 1075
I use not diffrens algos, only different input type.

I think correct add test and for 1075 too.