Can someone tell me what's test case 8? With set, all testcases pass but with Trie, I am getting WA at testcase 8.

Короче,у нас проходит некий турнир.Правила таковы: мы выбираем любых двух джедаев из оставшихся ,они между собой сражаются,из них по условию ровно один побеждает,проигравший исчезает с турнира. И так далее: снова выбираем двух джедаев,один остается,и т.д. По условию либо Джедай А сильнее Джедая Б либо наоборот. Сильнее значит не менее чем по двум параметрам один джедай выигрывает у другого(т.е. соответствующие значения строго больше). Нам нужно найти всех возможных победителей,т.е. тех,кто останется последним. Мы можем как угодно формировать расписание турнира,т.е. выбирать кто с кем из оставшихся будет драться. Победитель может провести всего 1 бой,а может 2,а может 3,... .Расписание мы САМИ формируем!!!

У кого нет идей,советую узнать про алгоритм Тарьяна и граф конденсации.

Edited by author 31.08.2015 22:18

Input:
trams trolleybuses trambus
bus
Output:
Bus driver

Input:
tram tramtrolleybus bus
Output:
Tram driver

Input:
trams trolleybus
trolleybus tram! tram.
Output:
Bus driver

Input:
bus bus tratrolleybus
trolleybu tra.
Output:
Bus driver

I've been struggling hard to overcome WA4 and WA9...
In the problem statement, it says "Sentences in a message consist of words, spaces and punctuation marks".
Then I've made these test cases and got AC in one go... :)
Try these cases if u get WA...

Case 1:
WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?
Ans:
Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

Case 2:
 WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?
Ans:
 Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

(It looks same to case 1, but it has an initial space character in the first line and I think this was causing WA9 for me...)

Case 3:
AND BEING CARELESS, WE ARE DESTROYING THE EARTH.
?????
WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?

WHY DID U DO THIS?
UUUUUUUU
UUUUUUUU IDIOT.
BYE.

Ans:
And being careless, we are destroying the earth.
?????
Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

why did u do this?
Uuuuuuuu
uuuuuuuu idiot.
Bye.

Case 4:
...ARE U THERE STILL?
PLEASE, ANSWER MEEEEEEEEE ,
ANSWER ME , ANSWER ME...
PLEASE
Ans:
...Are u there still?
Please, answer meeeeeeeee ,
answer me , answer me...
Please



Let me know if any1 finds any error...
Thanks.

I know heuristic solution to problem 1494 that passes all Timus tests but fails tests of some kind. The simplest test that it does not pass is
5
4
2
5
3
1

I need help, I got WA on test case 5, and I do not know what's the problem.
Here my code:
#include <bits/stdc++.h>
using namespace std;
string getPrefix(string s, int n){
    string result;
    if(n >= s.size())result = s;
    else result = s.substr(0,n);
    return result;
}
string getSuffix(string s, int n){
    int newN;
    string result;
    if(n >= s.size()) result = s;
    else result = s.substr(s.size() - n);
    return result;
}
int main(){
    string s, a, b;
    int m;
    while(cin>>s>>a>>b>>m){
        vector<pair<string, string> > v(m + 10, {"",""});
        vector<long long int> cnt(m + 10, 0);
        v[1] = {a, a}; cnt[1] = 0;
        v[2] = {b, b}; cnt[2] = 0;

        long long int maxi = 0;
        for(int i = 3, from, to; i <= m + 2;i++){
            cin>>from>>to;
            string text = v[from].second + v[to].first;
            string text2 = v[from].first + v[to].second;

            string prefix = getPrefix(text, s.size() - 1);
            string suffix = getSuffix(text, s.size() - 1);

            string prefixNew = getPrefix(text2, s.size() - 1);
            string suffixNew = getSuffix(text2, s.size() - 1);

            v[i] = {prefixNew, suffixNew};

            cnt[i] = (cnt[from] + cnt[to]) % 1000000007;
            if(text.size() >= s.size()){
                for(int j = 0 ; j < text.size() - s.size() + 1; j++){
                    if(s == text.substr(j,s.size()) ) cnt[i] = (cnt[i] + 1) % 1000000007;
                }
            }
        }
        long long int sol = 0;
        for(int i = 1; i <= m + 2; i++){
            sol = max(sol, cnt[i]);
        }
        cout<<sol<<endl;
    }
    return 0;
}

I got 89 for the example: 2 10, not 90, why? Any one know this?

Try abasajhdabba
the answer should be 'abba'

#include <iostream>
#include <cmath>
using namespace std;

int minCoins(int coins[], int m, int V)
{
    int table[V+1];

    table[0] = 0;

    for (int i=1; i<=V; i++)
        table[i] = INT_MAX;

    for (int i=1; i<=V; i++)
    {
        for (int j=0; j<m; j++)
            if (coins[j] <= i)
            {
                int subResult = table[i-coins[j]];
                if (subResult != INT_MAX && subResult + 1 < table[i])
                    table[i] = subResult + 1;
            }
    }
    return table[V];
}

int main()
{
    int V;
    cin>>V;
    int coins[1000];
    int i;


    for(i=1;i<=sqrt(V);i++)
    {
        coins[i-1] = (i)*(i);
    }
    int m = sqrt(V);

    cout<< minCoins(coins, m, V)<<endl;
    return 0;
}



This problem can be translated to get the minimum amout of coins to get the value N.(We must just check that the coins are the actual square numbers).

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


namespace Problem_1001
{
    class Program
    {
        static void Main(string[] args)
        {

            ulong[] input = new ulong[4];
            for (int i = 0; i < input.Length; i++)
            {
                input[i] = ulong.Parse(Console.ReadLine());
            }

            for (int i = input.Length - 1; i >= 0; i--)
            {

                Console.WriteLine(String.Format("{0:F4}",Math.Sqrt(input[i])));
            }

            //Console.ReadLine();
        }
    }
}

Edited by author 26.08.2016 20:54

got AC but for the following rectangle ((12, 0), (100, 12), (88, 100), (0, 88)) - you can shift it in any position, my solution will choose 'circle'

The new time limit for the problem id 4 seconds. With old time limit 5 seconds bruteforce solutions could pass all tests.

Can anybody explain the problem of test 3? I'm getiing WA again and again :(

Edited by author 22.06.2016 19:38

using System;

namespace CSharp_1197
{
    public class Program
    {
       static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string str2 = "";
            for (int i = 1; i <= n; i++)
            {
                string str1 = Console.ReadLine();
                if (str1 == "a1" || str1 == "h1" || str1 == "a8" || str1 == "h8") str2 = str2 + 2 + " ";
                else if(str1 == "b1" || str1 == "g1" || str1 == "b8" || str1 == "g8" || str1 == "a2" || str1 == "h2" || str1 == "a7" || str1 == "h7") str2 = str2 + 3 + " ";
                else if(str1 == "b2" || str1 == "g2" || str1 == "b7" || str1 == "g7" || str1 == "a3" || str1 == "h3" || str1 == "a6" || str1 == "h6" || str1 == "c1" || str1 == "f1" || str1 == "d1" || str1 == "e1" || str1 == "c8" || str1 == "f8" || str1 == "d8" || str1 == "e8" || str1 == "a4" || str1 == "h4" || str1 == "a5" || str1 == "h5") str2 = str2 + 4 + " ";
                else if (str1 == "b3" || str1 == "g3" || str1 == "b6" || str1 == "g6" || str1 == "c2" || str1 == "f2" || str1 == "d2" || str1 == "e2" || str1 == "c7" || str1 == "f7" || str1 == "d7" || str1 == "e7" || str1 == "b4" || str1 == "g4" || str1 == "b5" || str1 == "g5") str2 = str2 + 6 + " ";
                else str2 = str2 + 8 + " ";
            }
            Console.WriteLine(str2);
        }
    }
}

См. пример. Лично меня это сбило

Edited by author 07.03.2016 21:36

what can i do if i struck on a problem,becoz there are no solutions n hints availabe here :(

for(int m=i+2;m<=j;m++)
    if((m-i)%2==1)
    {
        t2+=t1;
        if(t2<-8000000000LL||(t2>8000000000LL))//Look at this line.
            break;
    }
    else
    {
        t1+=t2;
        if(t1<-8000000000LL||(t1>8000000000LL))//Look at this line.
            break;
    }

----
    Sorry for my bad English