first test is not sample.

Edited by author 26.10.2010 19:06

I have wrong answer on test 2, but all tests that I checked have right answer. Please, give me some tests to check my code.

kek

Get me test, please! I use kmp.

Check (AB,CD)==0 (orthogonality).
Check (AB, CD, DA) ==0 (planarity).
Check AD>AC>AB,  AC>BC,  BD>BC (order).
Check whether the projections to XY,  YZ,  XZ craddle each other continuations.
It is sufficient to check only the projections to XY plane to get Accepted verdict.

I always get ML, and i cant understand what sould i do?

I tried to use Scanner and BufferedReader.

Please tell me method to solve this.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Task1787
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] kMinute = Console.ReadLine().Split(new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            int k = int.Parse(kMinute[0]);
            int n = int.Parse(kMinute[1]);
            string[] nCam = Console.ReadLine().Split(new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            int sum = 0;
            foreach (var item in nCam)
            {
                sum += int.Parse(item);
            }
            Console.WriteLine(sum - (k * n));
        }
    }
}

In this problem,many people use the BFS(breadth first search).However,you can't search it from the two numbers which are in the last line,you should search it from the plate you need.Because of this,I was wrong before at test#6.

If your can't understand it,you can test the sample input,the right answer is-
2
1
2
but not 2
4
2

And pay attention at the number of routes-1 to 2000.

Believe me!!!

Sorry to my English...I'm a Chinese...

Good luck to you.:)

Possible with doubles, but quite complicated. Easy exact solution is possible with rational numbers (fractions), e.g., in the second case it is 390/43.

cin.sync_with_stdio(false);

Ignore the notes. G++ is faster than Clang++, while Visual C++ 2017 gives TL.

3 line python code

#include <bits/stdc++.h>
using namespace std;

#define re return
#define pb push_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;

vi l, r;

int main() {
    //freopen("input.txt", "r", stdin);
    string str;
    while (getline(cin, str)) {
        l.clear(), r.clear();
        if (isalpha(str[0])) l.pb(0);
        fo(i, (int)str.size() - 1) {
            if (!isalpha(str[i]) && isalpha(str[i + 1])) l.pb(i + 1);
            if (isalpha(str[i]) && !isalpha(str[i + 1])) r.pb(i + 1);
        }
        if (isalpha(str.back())) r.pb(str.size());
        fo(i, l.size()) reverse(str.begin() + l[i], str.begin() + r[i]);
        cout << str << '\n';
        str.clear();
    }
}

What is maximum number of the rectangles? According to my idea this is equal 6. I found the surfaces of these rectangles but Wrong answer #5.

Edited by author 20.11.2016 19:45

Here is my code:
# include <bits/stdc++.h>

using namespace std;

string s[300];

string conv(int x) {
    string str;
    while(x) {
        str.push_back(x % 10 + '0');
        x /= 20;
    }
    reverse(str.begin(), str.end());
    return str;
}

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            s[i] += "sin(" + conv(j);
            if(j != i) {
                if(j % 2)
                    s[i].push_back('-');
                else
                    s[i].push_back('+');
            }
        }
        for(int j = 1; j <= i; j++)
            s[i].push_back(')');
    }

    for(int i = 1; i < n; i++) cout << '(';
    for(int i = 1; i <= n; i++) {
        cout << s[i] << '+' << n - i + 1;
        if(i != n)
            cout << ')';
    }
    cout << endl;
    return 0;
}

Edited by author 13.11.2015 09:37

Edited by author 13.11.2015 09:37

del

Edited by author 11.03.2018 11:13

Edited by author 11.03.2018 11:13

If i use hash-table, i get WA. Because due to the small MOD ~10^6, i get probably a coincidence of some hashes.
(I used the degree = 31 and tried modules 1000003,... etc.)

If i use simply linear hash (in common vector) and sorting i get TL.

If i keep hash of each string in separate vectors, and then use a binary search, then again i get TL.

:(

WA6:
#include <iostream>
#pragma comment(linker, "/STACK:46777216")
#include <vector>
using namespace std;

#define ll int64_t

const int MAXN = 50005;

ll t[4*MAXN], add[4*MAXN], sz[MAXN];
ll n, q, x, cnt;
ll y, z, value[MAXN];
char c[15];
vector <ll> g[MAXN];
ll p[MAXN], pos[MAXN];


void init(ll v, ll tl, ll tr)
{
   if(tl == tr) add[v]=(ll)0, t[v]=value[tl];
   else
   {
      ll m=(tl+tr)/2;
      init(2*v, tl, m);
      init(2*v+1, m+1,tr);
      add[v]=(ll)0, t[v]=t[2*v]+t[2*v+1];
   }
}

ll sum(ll v, ll tl, ll tr, ll l, ll r)
{
   if(tl == l && tr == r) return t[v];
   else
   {
        ll m = (tl + tr) /2 ;
        ll a = add[v] * (ll)(r-l+1);
        if(r<=m) return a+sum(2*v, tl, m, l, r);
        if(l>m) return a+sum(2*v + 1, m+1, tr, l, r);
        return a+sum(2*v, tl, m, l, m) + sum(2*v + 1, m+1, tr, m+1, r);
   }
}


void update(ll v, ll tl, ll tr, ll l, ll r, ll val)
{
   if(tl == l && tr == r) add[v]+=val, t[v]+=val*(ll)(tr-tl+1);
   else
   {
        ll m = (tl + tr) /2;
        if(r<=m) update(2*v , tl, m, l, r, val);
        else
        {
            if(l>m) update(2*v  + 1, m+1, tr, l, r, val);
            else update(2*v , tl, m, l, m, val), update(2*v  + 1, m+1, tr, m+1, r, val);
        }
        t[v]=t[2*v]+t[2*v +1];
   }
};




void dfs(ll v, ll par = -1)
{
    p[v] = par, pos[v] = ++cnt, sz[v] = (ll)1;
    for (ll i = 0; i < (ll) g[v].size(); i++)
    {
        ll to = g[v][i];
        if (to == par) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
}



int main()
{
    scanf("%lld %lld %lld", &n, &q, &value[1]);
    for (ll i = 2; i <= n; i++)
    {
       scanf("%lld %lld\n", &x, &value[i]);
       x++;
       g[x].push_back(i);
       g[i].push_back(x);
    }

    cnt = 0;
    dfs(1);

    init(1, 1, n);

    for (ll i = 1; i <= q; i++)
    {
        scanf("%s %lld %lld %lld\n",&c, &x, &y, &z);
        x++;
        if (c[0] == 'e')
        {
            ll salary=sum(1,1,n,pos[x],pos[x]);
            if(salary<y) update(1,1,n,pos[x],pos[x],z);
        }
        else
        {
           ll departament = sum(1,1,n,pos[x],pos[x]+sz[x]-1);
           if(departament<y*sz[x]) update(1,1,n,pos[x],pos[x]+sz[x]-1,z);
        }
    }

    for(ll i=1;i<=n;i++)
    {
       ll salary=sum(1,1,n,pos[i],pos[i]);
       printf("%lld", salary);
       if(i<n) printf("\n");
    }

    return 0;
}


WA8:
#include <iostream>
#pragma comment(linker, "/STACK:46777216")
#include <vector>
using namespace std;

#define ll unsigned long long

const int MAXN = 50005;

ll sum[MAXN], add[MAXN], sz[MAXN], L[MAXN], R[MAXN];
int n, q, x, cnt, c;
ll y, z, value[MAXN], len;
char str[15];
vector <int> g[MAXN];
int p[MAXN], pos[MAXN], ind[MAXN];


void Create()
{
   len=(ll)1;
   while(len*len<n) len++;
   if(len*len>n) len--;
   c= n / len;
   for(int i=1;i<=c;i++) L[i]=(ll)(1+len*(i-1)), R[i]=(ll)(len*i);
   if(c*len<n) c++, L[c]=R[c-1]+1, R[c]=n;

   for(int i=1;i<=c;i++)
   {
      sum[i]=(ll)0, add[i]=(ll)0;
      for(int j=L[i];j<=R[i];j++) sum[i]+=value[j], ind[j]=i;
   }
}


void Update(int l, int r, ll val)
{
   int k1=ind[l];
   int k2=ind[r];

   for(int i=k1+1;i<=k2-1;i++) sum[i]+=val*(ll)(R[i]-L[i]+1), add[i]+=val;

   if(k1==k2)
   {
      for(int i=l;i<=r;i++) value[i]+=val, sum[k1]+=val;
   }
   else
   {
      if(l==L[k1]) sum[k1]+=val*(ll)(R[k1]-L[k1]+1), add[k1]+=val;
      else
      {
         for(int i=l;i<=R[k1];i++) value[i]+=val, sum[k1]+=val;
      }

      if(r=R[k2]) sum[k2]+=val*(ll)(R[k2]-L[k2]+1), add[k2]+=val;
      else
      {
         for(int i=L[k2];i<=r;i++) value[i]+=val, sum[k2]+=val;
      }
   }
}


ll Sum(int l, int r)
{
   int k1=ind[l];
   int k2=ind[r];
   ll res=(ll)0;

   for(int i=k1+1;i<=k2-1;i++) res+=sum[i];

   if(k1==k2)
   {
      for(int i=l;i<=r;i++) res+=value[i];
      res+=add[k1]*(ll)(r-l+1);
   }
   else
   {
      for(int i=l;i<=R[k1];i++) res+=value[i];
      res+=add[k1]*(ll)(R[k1]-l+1);

      for(int i=L[k2];i<=r;i++) res+=value[i];
      res+=add[k2]*(ll)(r-L[k2]+1);
   }
   return res;
}


void Dfs(int v, int par = -1)
{
    p[v] = par, pos[v] = ++cnt, sz[v] = (ll)1;
    for (int i = 0; i < (int) g[v].size(); i++)
    {
        int to = g[v][i];
        if (to == par) continue;
        Dfs(to, v);
        sz[v] += sz[to];
    }
}


int main()
{
    scanf("%d%d%lld\n", &n, &q, &value[1]);
    for (int i = 2; i <= n; i++)
    {
       scanf("%d%lld\n", &x, &value[i]);
       x++;
       g[x].push_back(i);
       g[i].push_back(x);
    }

    Dfs(1);
    Create();

    scanf("\n");
    for (int i = 1; i <= q; i++)
    {
        scanf("%s%d%lld%lld\n",&str, &x, &y, &z);
        x++;
        if (str[0] == 'e')
        {
            ll salary=Sum(pos[x],pos[x]);
            if(salary<y) Update(pos[x],pos[x],z);
        }
        else
        {
           ll departament = Sum(pos[x],pos[x]+sz[x]-1);
           if(departament<y*sz[x]) Update(pos[x],pos[x]+sz[x]-1,z);
        }
    }

    for(int i=1;i<=n;i++)
    {
       ll salary=Sum(pos[i],pos[i]);
       printf("%lld", salary);
       if(i<n) printf("\n");
    }

    return 0;
}



Edited by author 10.03.2018 23:40