Edited by author 06.04.2009 19:06

Does non-decreasing mean that is an increasing sequence of numbers?

Consider the following test:

7
Wayne 2 Bruce Dick
Bruce 1 Brown
Dick 1 Grayson
Brown 1 Gordon
Grayson 1 Gordon
Gordon 1 Stephanie
Stephanie 1 Wayne
Master Wayne is going to disguise as Batman and stop the Joker! I must prepare the Batmobile for his quest!

My solution fails to print Stephanie as a person who received the tweet about the earthquake. My solution uses a shortest path algorithm and that is why it takes into consideration only the shortest tweet reaching Gordon(the tweet sent by Grayson). So Gordon will try to send the tweet that he received(on the path Wayne Dick Grayson) preappended with "RT @Grayson: "(which is 13 characters long), totalling 141 characters. So the algorithm concludes that Stephanie will receive no tweet. But if we take the path Wayne, Bruce, Brown to Gordon, Gordon will receive a longer tweet than on the other path, but Stephanie will receive a tweet totalling 140 characters so she will actually be notified by a tweet too, although my algo fails to notice this.

I believe that there are great chances that other shortest path algos implemented by other users behave the same, so please try to consider improving the tests with a test similar with mine,

Regards,
Ciprian

Edited by author 15.10.2012 00:16

if you get WA 4 and you solve the problem from the end, than (maybe) you must take into account that sensor return only possitive number or null    ans   intermediate value can be >= 0.

Edited by author 15.10.2012 02:29

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException  {
        Scanner sc = new Scanner(System.in);
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = sc.nextInt();
        String S[] = new String[n];
        for (int i = 0; i < n; i++) {
            S[i] = sc.next();
        }
        int m = sc.nextInt();
        String[] S2 = new String[m];
        for (int i = 0; i < m; i++) {
            S2[i] = bf.readLine();
        }


        int count = 0, tempcont = 0;
        boolean isFineded = false;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                StringTokenizer st = new StringTokenizer(S2[i]);
                count -= tempcont;
                tempcont = 0;
                while (st.hasMoreTokens()) {
                    tempcont++;
                    String temp = st.nextToken();
                    if (isExits(temp, S[j])) {
                        count++;
                        isFineded = true;
                        System.out.println(i + 1 + " " + count);
                    } else {
                        count++;
                    }
                }
            }
            tempcont = 0;
        }

        if (isFineded == false) {
            System.out.println("Passed");
        }

    }
    static boolean isExits(String src, String str) {
        boolean bol=false;
        if (str.length() > src.length()) {
            return false;
        } else if (str.equals(src)) {
            return true;
        } else {
            for (int i = 0; i <= src.length() - str.length(); i++) {
                if (str.equals(src.substring(i, i + str.length()))) {
                    bol=true;
                }
                }
            return bol;
        }

    }
}

var
n,i,k:byte;
x,d,y:integer;
m:array[0..100] of integer;
begin
read(n,x);
for i:=1 to n do
read(m[i]);
k:=0;
y:=n;

if x<0 then begin

for i:=1 to y do begin
if (m[i]>x) and (m[i]<0) then
begin writeln('Impossible'); k:=k+1;end
else
begin if m[i]<0 then begin y:=abs(x); end;
if m[i]>0 then d:=m[i];
end;
if m[i]<d then d:=m[i];end;
writeln(d+d+abs(x));
writeln(y);

end;

if x>0 then begin
for i:=1 to n do begin
if (m[i]<x) and (m[i]>0) then begin writeln('Impossible'); k:=k+1;end
else
begin if (m[i]>x) and (m[i]>0) then begin d:=x; writeln(d);end;
if m[i]<0 then d:=m[i];end;
if (m[i]<0) and (m[i]>d) then d:=m[i];
end;
writeln(abs(d)+abs(d)+x);
end;




end.

Sorry for Russian...
моё решение задачи... перевожу число в двоичную чистему исчисления.. считаю количество единичек.. если это количество четное, то выиграл второй, если нечетное, то первый... Почему такое решение проходит все тесты??? Оно же неверное.. например при N=5 моя прога выдаст, что выиграл второй, хотя на самом деле выигрывает первый, взяв 2 камня...

found my mistake


Edited by author 26.06.2012 01:56

I've got AC by stupid brute force, like if (i % 2) k++;.
But i think that there is a easier way to solve this task. Topic.

input:
3
72
30
50

output:
120.00

But the task is to find the minimal weight!
I wonder how 120.00 (2*sqrt(72*50)) can be minimal? It's maximal!

I try to parse digits by symbols this way:
using System;
using System.Text.RegularExpressions;
using System.Globalization;
using System.Collections.Generic; //Version 2

namespace CSharpV1
{
    class Program
    {
        //static readonly char[] splitChars = { ' ', '\t', '\n', '\r' }; //Version 1
        static void Main(string[] args)
        {
            var nfi = NumberFormatInfo.InvariantInfo;
            //Version 4. Symbolic input
            int curCharDigit;
            char curChar;
            var curDigitString = String.Empty;
            var rootsStack = new Stack<double>();
            while ((curCharDigit = Console.Read()) != -1)
            {
                curChar = Convert.ToChar(curCharDigit);
                if (char.IsDigit(curChar) || curChar == '.' || curChar == ',')
                {
                    curDigitString += curChar;
                }
                else
                {
                    if (curDigitString.Length != 0)
                    {
                        var curDigit = Convert.ToDouble(curDigitString, nfi);
                        var root = Math.Sqrt(curDigit);
                        rootsStack.Push(root);

                        curDigitString = String.Empty;
                    }
                }
            }
            while (rootsStack.Count != 0)
            {
                var curRootString = string.Format(nfi, "{0:F4}", rootsStack.Pop());
                Console.WriteLine(curRootString);
            }
            rootsStack = null;
        }
    }
}

And I get Wrong answer while test 3...
The code works fine with example input data. The digits are Integer.
What's wrong?

I uploaded the following solution but it only says "crash":


using System;

namespace Week2
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b;
            a = int.Parse(Console.ReadLine());
            b = int.Parse(Console.ReadLine());
            Console.WriteLine(a + b);
        }
    }
}

Pascal

var a,b:real;
begin
 readln(a);
 readln(b);
 writeln(a+b);
end.

Edited by author 10.10.2012 17:42

#include <iostream>
using namespace std;
int main() {
    int a, c, b, year;
    double a1, b1, c1;
    cin >> a >> b >> c;
    a1=static_cast <double>(a);
    if(a1<=1024*1024*1024*2-1 && b<=1024*1024*1024*2-1 && c>=1 && c<=100 && a>0 && b>0) {
    for(year=1; a1=a1*(100-c)/100; year++) {
                if (a1<=b) {
                        cout << year;
                        break;
                        }
                        }
                        }
    cin.get(); cin.get();
    return 0;
}

I have WA on test#10.

Please some body tell me why i am gettig wrong answer in this. My code is:

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <string.h>
#include <cstdlib>
#include <sstream>
#include <stack>
#include <queue>
#include <numeric>
#include <utility>
#include <cctype>
#include <list>
#include <climits>
#include <signal.h>
#include <ctime>
#include <map>
#include <set>

using namespace std;
#define ll long long int
ll i, j, k, ct=0, m, n, t, x, y, z, tc, a[200000],s;
    vector<ll> ans;
int main(){

    cin >> n >> s;

    for(i = 0; i < n; i++){
        cin >> a[i];
    }

    sort(a,a+n);

    for ( i = n-1; i > 0 ; i-- ) {
        if ( a[i] + a[i-1] <= s ) {
            break;
        }
    }

    //    cout << x << " " << y << endl;
    if(s%2==0){
        x = i+1;
        y = i;
        //z = n-1;
        while ( x < n && y >= 0 ) {

            ans.push_back( a[y] );
            ans.push_back( a[x] );

            x++;
            y--;
        }

        while ( x < n ) {
            ans.push_back( a[x] );
            x++;
        }


        while ( y >= 0 ) {
            ans.push_back( a[y] );
            y--;
        }
    }
    else {
        y = i;

        while ( i < n && a[i] == a[y]){
            ans.push_back( a[i] );
            i++;
        }
        y--;
        x = i;
        while (  x < n && y >= 0 ) {

            ans.push_back( a[x] );
            ans.push_back( a[y] );

            x++;
            y--;
        }
        while ( x < n ) {

            ans.push_back( a[x] );
            x++;
        }

        while ( y >= 0 ) {
            ans.push_back( a[y] );
            y--;
        }
    }


    ct = 0;

    for (  i = 0; i < ans.size(); ) {
        if( i == ans.size() - 1){
            ct++;
            i++;
        }
        else{
            if( ans[i] + ans[i+1] <= s){
                ct++;
                i+=2;
            }
            else{
                ct++;
                i++;
            }
        }
    }

    cout << ct << endl;
    for (  i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

Edited by author 13.10.2012 20:42

My god! When I use gcc I get the right anwer, but vc++2010 doesn't.
What should I do?

There is still time left in the competition...?