Edited by author 26.10.2013 22:11

use modulo for a-z:

(ascii_char_code + 2) % 3 + 1,

Could anybody tell your solution?

Что проверяет 5 тест(

#include<stdio.h>

int main(){
int n,sum=0,i;
scanf("%d",&n);-

if(n>0){
  sum=(n*(n+1))/2;
}
else if(n<0){
        sum=(n*(-1*n+1))/2;
}
printf("%d",sum);


}

i have tried this problem several years....while preparing for contests and it's always WA and it's not at all the heardest of problems.....
i made an O (n log n) alg using heaps ....as usual
it's WA at test 2

could someone put some tests around??? i ageve my self some and nothing....bad
could somebody explain why??????????????:
1 2 3 2 3
my result:
1: 2 4
2: 1 3 6
3: 2 5
4: 1
5: 3
6: 2
AC result:
1: 2 4
2: 1 3 6
3: 2 5
4: 1
5: 1  //5 is not even conected to 1???????
6: 3




Edited by author 13.10.2006 04:08

Edited by author 13.10.2006 04:40

4
1 3
1 4
2 4
1
2 4

The correct answer is 1.

Why I don't get AC
here is my code:

var n,k,m,AC:integer;
begin
readln(n,k);
m:=n div 2;
if k=m then AC:=0;
if k<m then AC:=m-k;
if k>m then AC:=k-m-1;
write(AC);
end.

my solution passing all test from my head
can you advice what's wrong:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import static java.util.stream.Collectors.toList;

/**
 * solution for http://acm.timus.ru/problem.aspx?space=1&num=1002
 */
public class Step {

    private static Map<Character, List<Character>> mapping;

    public static void main(String[] args) throws IOException {
        new Step().solveMe(new BufferedReader(new InputStreamReader(System.in)));
    }

    public static Map<Character, List<Character>> buildMapping() {
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('1', Arrays.asList('i', 'j'));
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h'));
        map.put('5', Arrays.asList('k', 'l'));
        map.put('6', Arrays.asList('m', 'n'));
        map.put('7', Arrays.asList('p', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y'));
        map.put('0', Arrays.asList('o', 'q', 'z'));
        return map;
    }

    public static Trie buildTrie(List<String> dictionary) {
        return dictionary.stream().reduce(
                Trie.EMPTY_TRIE, (node, word) -> node.buildTree(node, word),
                (node, node2) -> node.append(node));
    }

    private void solveMe(BufferedReader in) throws IOException {
        String n;
        mapping = buildMapping();
        Map<String, Trie> input = new HashMap<>();
        while (!(n = in.readLine()).equals("-1")) {
            int s = Integer.parseInt(in.readLine());
            List<String> dict = in.lines().limit(s).collect(toList());
            input.compute(n, (key, val) -> buildTrie(dict));
        }
        input.forEach((s, trie) -> System.out.println(solution(s, trie)));
    }

    public String solution(String number, Trie root) {

        List<List<String>> result = root.filter(number);
        if (result.isEmpty()) {
            return "No solution.";
        }
        List<String> bestShot = result.stream().reduce((List<String> minList, List<String> other) -> {
            if (minList.size() >= other.size()) {
                return other;
            }
            return minList;
        }).get();
        return String.join(" ", bestShot);
    }

    public static class Trie {

        public static final Trie EMPTY_TRIE = new Trie((char) 0);
        private final Character ch;
        private final Map<Character, Trie> nexts;
        private final boolean isWord;

        public Trie(Character ch) {
            this(ch, new HashMap<>(), false);
        }

        private Trie(Character ch, boolean isWord) {
            this(ch, new HashMap<>(), isWord);
        }

        private Trie(Character ch, Map<Character, Trie> nexts, boolean isWord) {
            this.ch = ch;
            this.nexts = nexts;
            this.isWord = isWord;
        }

        public List<List<String>> filter(String number) {
            List<List<String>> lists = new ArrayList<>();
            List<String> e = new ArrayList<>();
            filterHelper(lists, e, number, "", this);
            return lists;
        }

        private void filterHelper(List<List<String>> acc, List<String> result, String number, String word, Trie node) {
            if (node.isWord) {
                if (number.length() == 0) {
                    result.add(word);
                    acc.add(result);
                    return;
                }
                List<String> res = new ArrayList<>(result);
                res.add(word);
                filterHelper(acc, res, number, "", this);
            }

            List<Character> maps = mapping.get(number.charAt(0));
            maps.forEach(e -> {
                Trie next = node.nexts.get(e);
                if (next != null) {
                    filterHelper(acc, new ArrayList<>(result), number.substring(1), word + next.ch, next);
                }
            });
        }

        public Trie buildTree(Trie root, String word) {
            char c = word.charAt(0);
            if (word.length() == 1) {
                Trie newTrie = new Trie(c, true);
                return root.append(newTrie);
            } else {
                Trie newTrie = new Trie(c, false);
                return root.append(buildTree(newTrie, word.substring(1)));
            }
        }

        public Trie append(Trie other) {
            Trie trieCopy = new Trie(this.ch, this.nexts, this.isWord);
            Trie newVal = other;
            if (trieCopy.nexts.containsKey(newVal.ch)) {
                Trie next = trieCopy.nexts.get(newVal.ch);
                Trie initial = new Trie(next.ch, next.nexts, next.isWord);
                newVal = newVal.nexts.values().stream().reduce(initial, Trie::append);
            }
            trieCopy.nexts.put(newVal.ch, newVal);
            return trieCopy;
        }

        @Override
        public String toString() {
            StringBuilder bld = new StringBuilder();
            bld.append(ch).append(" = [");
            nexts.forEach((c, n) -> bld.append(n).append(" "));
            return bld.append("]").append(isWord ? " = true" : "").toString();
        }
    }
}

Hi guys, any ideas on test #4? getting WA there

Does anybody had Acces Violation? And if so , how did you fix it?

плиз напишите решение задачи 1877. Велосипедные коды
please help piton 3.6

Edited by author 17.12.2018 19:09

Why use a binary search. How can we say that the value of the hash of 4x4 > 3x3 > 2x2 > 1x1? I don`t understand why to use binary search.
plz, help me...

5000 -> 143882158
4856 -> 977177749
4257 -> 755678035
4000 -> 757298829
3500 -> 997776483

My solution is based on string hashing. Let's say that the strings from the input are s[1], s[2], ... , s[n]. First, let's iterate over all possible lengths from 1 to 100 (since the maximal length of a string is 100). Let's fix some length "len" and create a vector "all" which will contain all possible hashes of substrings of length "len" of all the strings s[i]. Additionally, for each i from 1 to n create a vector a[i] which will contain the hashes of substrings of length "len" of only the string s[i]. Now, sort all the vectors we've created so that we could binary search on them. Finally, go through each i from 1 to n and then for each of the substrings of s[i], using binary search count the number of occurrences of its hash in the vector "all" and the vector a[i]. If these numbers are equal, then this substring occurred only in the string s[i] and can be used as a key substring. By changing the base and modulo of the hash, you can pass the WA caused by collision of hashes (I used p = 2313 and mod = 1000000123). The time complexity will be O(max_len * n^2 * log(n)), where max_len is the maximal length of a string.

Please, give me some tests

3
50 100
-50 70
51 70

My accepted solution prints
1
2

While the correct answer should be
2
3 1

Edited by author 04.06.2020 23:13

Solve with Python and use eval() to calculate boolean expression