CSES - Datatähti 2020 alku - Results
Submission details
Task:Lukuvälit
Sender:jannejal
Submission time:2019-10-02 06:55:23 +0300
Language:Node.js
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED24
#3ACCEPTED64
Test results
testverdicttimegroup
#1ACCEPTED0.43 s1, 2, 3details
#2ACCEPTED0.43 s1, 2, 3details
#3ACCEPTED0.43 s1, 2, 3details
#4ACCEPTED0.43 s1, 2, 3details
#5ACCEPTED0.43 s1, 2, 3details
#6ACCEPTED0.43 s1, 2, 3details
#7ACCEPTED0.43 s1, 2, 3details
#8ACCEPTED0.43 s1, 2, 3details
#9ACCEPTED0.43 s1, 2, 3details
#10ACCEPTED0.43 s1, 2, 3details
#11ACCEPTED0.43 s1, 2, 3details
#12ACCEPTED0.43 s1, 2, 3details
#13ACCEPTED0.56 s2, 3details
#14ACCEPTED0.70 s2, 3details
#15ACCEPTED0.59 s2, 3details
#16ACCEPTED0.67 s2, 3details
#17ACCEPTED0.69 s2, 3details
#18ACCEPTED0.69 s2, 3details
#19ACCEPTED0.43 s2, 3details
#20ACCEPTED0.43 s2, 3details
#21ACCEPTED0.57 s3details
#22ACCEPTED0.79 s3details
#23ACCEPTED0.62 s3details
#24ACCEPTED0.84 s3details
#25ACCEPTED0.79 s3details
#26ACCEPTED0.74 s3details
#27ACCEPTED0.43 s3details
#28ACCEPTED0.43 s3details

Code

// TODO: big numbers library???

let readline = require('readline');
// const fs = require('fs');

var r = readline.createInterface({
    input: process.stdin, //fs.createReadStream("./c.data.txt"),
    output: process.stdout,
    terminal: false
});

let n = 0;
let strings = [];
r.on('line', line => {
    if (!n) n = Number(line);
    else {
        strings.push(line);
        if (strings.length === n) {
            run();
            process.exit();
        }
    }
});

const run = () => {
    console.time();
    let all = [];
    // console.log(strings.length);
    for (let i = 0; i < strings.length; i++) {
        const [a1, b1] = strings[i].split(" ");
        const a = getLowestUp(a1);
        const b = getBiggestUnder(b1);
        // console.log(a1, b1);
        all.push(binaryMinusPlusOne(a, b));
        // if (i % 100) {
        //     console.log(all.join("\n"));
        //     all = [];
        // }
    }
    console.log(all.join("\n"));
    // console.timeEnd();
};

const getBiggestUnder = x => {
    let start = String(x)
    if (start === "0") return "0";
    if (start[0] !== "1") return new Array(start.length).fill("1").join("");
    else {
        const endWithout10 = start.replace(/[0-1]+/, "");
        const lengthOf10 = start.length - endWithout10.length;
        if (lengthOf10 === start.length) return start;
        const firstPart = start.substring(0, lengthOf10) + new Array(endWithout10.length).fill("0").join("");
        const secondPart = getBiggestUnder(endWithout10);
        return addBinaries(firstPart, secondPart);
    }
};

// TODO: replace with binary substraction algorithm
const addBinaries = (a, b) => (parseInt(a, 2) + parseInt(b, 2)).toString(2);

const getLowestUp = x => {
    let start = String(x)
    if (start === "0") return "0";
    if (start[0] !== "1") return "1" + new Array(start.length).fill("0").join("");
    else {
        const endWithout10 = start.replace(/[0-1]+/, "");
        const lengthOf10 = start.length - endWithout10.length;
        if (lengthOf10 === start.length) return start;
        const firstPart = start.substring(0, lengthOf10) + new Array(endWithout10.length).fill("0").join("");
        const secondPart = getLowestUp(endWithout10);
        return addBinaries(firstPart, secondPart);
    }
};

// TODO: replace with binary substraction algorithm
const binaryMinusPlusOne = (a, b) => parseInt(b, 2) - parseInt(a, 2) + 1;

// console.log(getLowestUp(1), getBiggestUnder(5), binaryMinusPlusOne(1, 1));
// process.exit();

// console.log(getLowestUp("1"));
// console.log(getBiggestUnder("1"));
// console.log(binaryMinusPlusOne(getLowestUp("0"), getBiggestUnder("1")))
// process.exit();

// console.time();
// console.log("lowestUp", getLowestUp(236161597806217700));
// console.log("biggestUnder", getBiggestUnder(854038659947235000));
// console.log("binaryMinus", binaryMinusPlusOne("111111111111111111", "1000000000000000000"));
// console.log("parseInt", parseInt("1000000000000000000", 2))
// console.log("parseInt", parseInt("111111111111111111", 2))
// console.log(binaryMinusPlusOne(getLowestUp(236161597806217700), getBiggestUnder(854038659947235000)));
// console.timeEnd();
// process.exit();

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
4
0 10
1 5
3 4
11 11

correct output
3
1
0
1

user output
3
1
0
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
0 0

correct output
1

user output
1

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1000 1000

correct output
1

user output
1

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
16
0 0
0 1
0 2
1 1
...

correct output
1
2
2
1
1
...

user output
1
2
2
1
1
...

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
9
0 0
0 1
0 10
0 11
...

correct output
1
2
3
4
5
...

user output
1
2
3
4
5
...

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 1000
0 1000
0 1000
0 1000
...

correct output
9
9
9
9
9
...

user output
9
9
9
9
9
...

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
100 111
0 101
1 10
10 110
...

correct output
4
6
2
5
8
...

user output
4
6
2
5
8
...

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
480 564
753 988
479 909
32 973
...

correct output
0
0
0
4
0
...

user output
0
0
0
4
0
...

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
98 111
8 111
98 111
111 113
...

correct output
4
6
4
1
7
...

user output
4
6
4
1
7
...

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 0
1 1
2 2
3 3
...

correct output
1
1
0
0
0
...

user output
1
1
0
0
0
...

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
0 1000
0 999
1 1000
0 998
...

correct output
9
8
8
8
7
...

user output
9
8
8
8
7
...

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
0 1000

correct output
9

user output
9

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 100000
0 100000
0 100000
0 100000
...

correct output
33
33
33
33
33
...

user output
33
33
33
33
33
...

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
100000
86042 98295
30077 80920
45856 67174
3890 60412
...

correct output
0
0
0
16
0
...

user output
0
0
0
16
0
...

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
100000
11 10000
1111 11000
1011 1100
1110 1111
...

correct output
14
10
2
2
8
...

user output
14
10
2
2
8
...

Test 16

Group: 2, 3

Verdict: ACCEPTED

input
100000
9 9999
1109 1110
112 1012
11098 11101
...

correct output
14
1
4
2
6
...

user output
14
1
4
2
6
...

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 0
1 1
2 2
3 3
...

correct output
1
1
0
0
0
...

user output
1
1
0
0
0
...

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
100000
0 100000
0 99999
1 100000
0 99998
...

correct output
33
32
32
32
31
...

user output
33
32
32
32
31
...

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
3
99999 99999
99999 100000
100000 100000

correct output
0
1
1

user output
0
1
1

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
1
0 100000

correct output
33

user output
33

Test 21

Group: 3

Verdict: ACCEPTED

input
100000
0 1000000000000000000
0 1000000000000000000
0 1000000000000000000
0 1000000000000000000
...

correct output
262145
262145
262145
262145
262145
...

user output
262145
262145
262145
262145
262145
...

Test 22

Group: 3

Verdict: ACCEPTED

input
100000
179926689319432205 25677963778...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 23

Group: 3

Verdict: ACCEPTED

input
100000
100110100011010101 11100011010...

correct output
74822
54944
140968
252594
23521
...

user output
74822
54944
140968
252594
23521
...

Test 24

Group: 3

Verdict: ACCEPTED

input
100000
100110100011010102 11100011010...

correct output
74822
252594
94086
10836
11352
...

user output
74822
252594
94086
10836
11352
...

Test 25

Group: 3

Verdict: ACCEPTED

input
100000
256779637786129463 25677963778...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 26

Group: 3

Verdict: ACCEPTED

input
100000
0 1000000000000000000
0 999999999999999999
1 1000000000000000000
0 999999999999999998
...

correct output
262145
262144
262144
262144
262143
...

user output
262145
262144
262144
262144
262143
...

Test 27

Group: 3

Verdict: ACCEPTED

input
3
999999999999999999 99999999999...

correct output
0
1
1

user output
0
1
1

Test 28

Group: 3

Verdict: ACCEPTED

input
1
0 1000000000000000000

correct output
262145

user output
262145