Edited by author 18.11.2017 03:29

If you got WA #28 - check int64 overflow

The limitation on N was changed to reflect the actual test data. Instead of the old N < 10^600 the limitation was set to 0 < N < 10^300.

Note that this is not the limitation on the input, but rather on the output. The number given to the input has about twice as many digits, previously up to ~1200 digits, now up to ~600 digits, but the actual test data was always only up to ~600 digits. Edge case N=0 was also missing in the test data, and is now explicitly disallowed by the limitation.

New thorough tests were added within the new limitations. The time limit was reduced from 2.0 sec to 1.0 sec.

All solutions have been rejudged. 192 authors lost, and 12 other authors gained the Solved status for the problem.

Bugs fixed in the checker program.

1. The total length of dangerous segments was not always correctly verified against the canonical answer. Most prominently, the following output was previously accepted for the sample input (test 1), which has the total dangerous length 1.0 with the optimal one being 0.8:

2
1.0 1.5
0.0 1.5

2. Precision issues were fixed that were causing solutions with certain output rounding strategies being rejected (most commonly, WA8).

The limitation on the number of pieces of furniture N was updated in the problem statements from N >= 0 to N >= 1 to reflect the actual test data.

Additionally, the time limit was reduced from 2.0 sec to 1.0 sec.

All solutions have been rejudged. 21 authors lost, and 2 other authors gained the Solved status for the problem.

import java.io.IOException;


import java.util.Scanner;

public class Main {
    public static int rent = 100;

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int numberOfFriends = Integer.parseInt(scanner.nextLine());
        int totalGuests = 2;
        for (int i = 0; i < numberOfFriends; i++) {
            String answer = scanner.nextLine();

            if (answer.contains("+")){
                totalGuests += 2;
            }else{
                totalGuests++;
            }
        }
        if (totalGuests == 13){
            totalGuests++;
        }
        int total = totalGuests*rent;
        System.out.println(total);

        scanner.close();
    }
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k , n;
    cin >> k >> n;
    int sum = 0;
    while(n--)
    {
        int a;
        cin >> a;
        sum += a;
        sum -= min(sum , k);
    }
    cout << sum;
}

the solution is n-th fibonaci number
write every option for evidence


#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    //the answer is F[n] - fibonnaci number
    //76 > 3
    vector <long long> dp(n + 2);
    dp[1] = 2;
    dp[2] = 2;
    for(int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2];
    cout << dp[n];
}

All the trouble are caused by precision.

The first submittion includes the code:
angle_ACB = math.acos((x1*x2+y1*y2+z1*z2) / (len_CA*len_CB))
Then I got RE#8 in python, WA#8 in C++.

Next I change the code to:
angle_ACB = math.acos(0.5*(CA_sqr + CB_sqr - len_AB**2) / (len_CA*len_CB)) in python
angle_ACB = acos(0.5* (CA_sqr + CB_sqr - sqr(len_AB))/(len_CA*len_CB)) in C++
Then I got RE#48 in python, WA#48 in C++.

So I am sure the trouble is caused by the precision because of the function sqrt()!
Sometimes, the cos(angle_ACB) is smaller than -1.
Then the problem occurred by using acos(x) if x<-1.
You need to handle this situation.

Pls, anyone give me some hint about test #2 ! Thanks

be carefull you cann't create a dsu of size 10^9 given becasue max array size limit is roughly 10^7.
hint: you do not need to track all the node parents instead need to track parents of those which only appears in the question.

here is my soulution(c++):

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// priority_queue<type, std::vector<type>, decltype(cmp)> pq(cmp);
// set/multiset<type, decltype(cmp)> s(cmp);
// map<key_type, val_type, decltype(cmp)> m(cmp);
// sort(v.begin(), v.end(), cmp)
// cmp = custom_lamda_compare_function|syntax: [capture](parameters) -> return_type {}
// typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

using namespace std;
using namespace __gnu_pbds;
using namespace std;

class DSU{
private:
     map<int,pair<int, int>> parent;
public:
     DSU(int size){}

     pair<int, int> find(int node){
          if(parent.find(node) == parent.end()){
               return {node, -1};
          }
          return parent[node];
     }

     bool union_set(int node1, int node2, int p){
          auto it = find(node2);
          int root = it.first;
          int rootP = it.second;
          if(rootP == -1){
               parent[node2] = {node1, p};
               return true;
          }
          else if(root < node1){
               parent[node2] = {node1, p};
               return union_set(root, node1 - 1, rootP ^ p);
          }
          else if(root > node1){
               return union_set(node1, root - 1, rootP ^ p);
          }
          else{
               if(rootP == p) return true;
               else return false;
          }
     }
};

int main(){
     //////////////////////////////////////////////////////
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     //////////////////////////////////////////////////////
     int t;
     // cin>>t;
     // int ct = 0;
     t = 1;
     while(t--){
          while(true){
               int n;
               cin>>n;
               if(n == -1){
                    break;
               }
               DSU dsu(n);
               int q;
               cin>>q;
               int ans = 0;
               bool b = false;
               while(q--){
                    int x, y, p;
                    string str;
                    cin>>x>>y>>str;
                    p = (str == "even") ? 0 : 1;
                    bool is = dsu.union_set(x, y, p);
                    if(is && !b){
                         ans++;
                    }
                    else{
                         b = true;
                    }
               }
               cout<<ans<<'\n';
          }
     }
}

I did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance

It can be done with only 3 cables with max value of 1.  Got AC

In Go you should use `fmt.Scanf("%d %d\n", &a, &b)` instead of `fmt.Scanf("%d %d", &a, &b)`! Using the latter results in reading zeroes.

My max value is 13:
########
#@ $.$.#
#  $.$.#
#$ $.$.#
#. $.$.#
#$ $.$.#
#.   $.#
########

Has anybody found more?

Hint 1: The teams with same scores follow their original order, top to bottom.

Hint 2: You can implement stable sort by yourself.

Hint 3: M is given <=100.

Hint 4: Group all the teams with the same score together in a container.

Solution : Use an array of arrays, with size 101. You can add the input as it comes in the array with the index equal to its score. Output starting from the end, iterating over the array of arrays.

C++ Code:


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

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> v(101);
    for(int i =0;i<n;i++)
    {
        int a,b;
        cin >>a >> b;
        v[b].push_back(a);
    }
    for(int i =100;i >= 0;i--)
    {
        if((v[i].size()))
        {
            for(auto a:v[i])
            {
                cout << a << " " << i << "\n";
            }
        }
    }
    return 0;
}

I tried with precalculating with map for setting up the index with 1 only rest will be auto 0 but miraculously WA at 4. so i figured out that the author only wants you to solve with his idea only. So good luck.

Missing checks added to the checker program. New tests added to the problem. The time limit increased from 1 sec to 2.5 sec to compensate for increased difficulty.

All solutions were rejudged. 20 out of 45 authors lost the Accepted status for the problem.

Test in you code example like this
4 3
1 5 6
Wrong Answer is 0.
Thrue Answer is 3.
Be confident!!!

/***************************************************************************************************
                         Anzmaul Haque Akash
                    DIU, Daffodil International University
                    E-mail: anzamul15-2297@diu.edu.bd
 Youtube:https://www.youtube.com/channel/UCXvXHUkxyLYKeQkIg_RyMBw
******************************************************************************************************/
#include<bits/stdc++.h>

#define ln     (int)1e6
#define pi     acos(-1.0)
#define pb     push_back
#define pf     push_front 1
#define mp     make_pair
#define F      first
#define S      second
#define INF    1000000000000000000
#define LES    -1000000000000000000
#define intlim 2147483648
#define ll     long long
#define ull    unsigned long long
#define str    string
#define in     insert

#define all(akash)       akash.begin(),akash.end()
#define ms(arr)          memset(arr,0,sizeof(arr))
#define msbooltrue(arr)  memset(arr,true,sizeof(arr))
#define msboolfalse(arr) memset(arr,false,sizeof(arr))
#define msINF(arr)       memset(arr,INF,sizeof(arr))
#define case1(cs)        cout<<"Case "<<cs<<": "
#define case2(cs)        cout<<"Case "<<cs<<":\n"
#define lb               cout<<"\n";

#define vec vector
#define qu  queue
#define li  list
#define pq  priority_queue
#define em  empty

#define fori(i,a,b) for(int i=0;i<b;i++)
#define ford(i,a,b) for(int i=b-1;i>=0;i--)
#define forc(ch);   for(char ch:str)

#define sc1(a)         scanf("%lld",&a)
#define sc2(a,b)       scanf("%lld %lld",&a,&b)
#define sc3(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define sc4(a,b,c,d)   scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sc5(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)

using namespace std;

void solve(ll n){

    ll temp_n=n;

    temp_n--;

    for(ll i=0; i<n-1; i++){
        cout<<"(";
    }
    cout<<"sin(1)+"<<n<<")"; //Segment 1.

    str s="sin(1-sin("; // if n>1 this one is using for the template.


    for(ll i=2;i<=n;i++){ //main loop.

        str temp;
        temp.clear();
        temp=s;


        for(ll x=2; x<i;x++){ //This one creat middle of Every part.

            if(x%2==0){ //' + ' for even ' - ' for odd.
                temp+=to_string(x);
                temp+="+sin(";
            }
            else{
                temp+=to_string(x);
                temp+="-sin(";
            }

        }

        temp+=to_string(i);

        for(ll y=1;y<=i;y++){ //for closing ' ) ' every equation.
            temp+=")";
        }

        cout<<temp; //print each segment.

        if(temp_n > 1){
            cout<<"+"<<temp_n<<")"; //Printing every segment last digit with out 1.
        }
        temp_n--;
    }

    cout<<"+1";lb//This one for end.
}

int main()
{
    ll n;
    sc1(n);

    if(n>1){
        solve(n); //solve function.
    }
    else if(n==1){
        cout<<"sin(1)+1";lb //for 1.
    }

    return 0;
}

AC with max travel dist = 6