Subtract 1 from each element
Apply window to the array for max sum of S


#include <bits/stdc++.h>
using namespace std;
#define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++)
#define rep(i,x,n) for(long i=long(x);i<long(n);i++)
int main()
{
    //ifstream cin("input.in");
    //ofstream cout("output.out");
    ios::sync_with_stdio(0);cin.tie(0);
    long n,s,a[100009],p=0;
    cin>>n>>s;
    bool flag=1;
    rep(i,0,n)
    {
        cin>>a[i];
        a[i]--;
    }
    rep(i,0,n)
    {
        p+=a[i];
        if(p>s)
            flag=0;
        p=max(p,0l);
    }
    if(flag)
        cout<<"YES";
    else
        cout<<"NO";
}

Edited by author 11.12.2017 08:23

This works correct even with 1000 numbers. (What else compilator wants? ))

#include <stdio.h>
int nod(int a, int b){
    while (a != 0 && b != 0){
        if (a > b)
            a = a % b;
        else
            b = b % a;
    }
    return a+b;
}
int main(){
    int size;
    int result = 1;
    scanf_s("%i", &size);
    int arr[1001];
    bool mask[1001];
    for (int i = 0; i < size; ++i)
        scanf_s("%i", &arr[i]);
    for (int i = 0; i < size; ++i){
        int k = 1, temp = arr[i];
        while (temp != i + 1){
            temp = arr[temp - 1];
            ++k;
        }
        if (mask[k] != false){
            mask[k] = false;
        result =result/nod(result,k) * k;

        }
    }
    printf("%i", result);
}

If you don't feel like reviewing my code at least give me some tests please.
So... um... I think my code should work... I tested it along with an accepted program... and it worked fine... Here's the code:

#define DM 1001
#include <bitset>
#include <iostream>
#include <set>
using namespace std;

bitset <DM> bs;
bool verif;
int n, c, lg[DM], mp[DM];
long long v;
set <int> s;

void recursiv (int a)
{
    bs[a] = 1;
    ++v;
    if (s.find(mp[a]) != s.end())
        return;
    s.insert(a);
    recursiv(mp[a]);
}

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> mp[i];
        if (mp[i] == i)
            bs[i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!bs[i])
        {
            recursiv(i);
            s.clear();
            lg[++c] = v;
            v = 0;
        }
    for (v = lg[1]; !verif; ++v)
    {
        verif = 1;
        for (int i = 1; i <= c; ++i)
            if (v%lg[i] != 0)
                verif = 0, i = c + 1;
    }
    cout << v - 1;
    return 0;
}

I really don't understand why i got WA #12...i try a lot of tests and i always have the right answer, could anyone give me test 12, please.

example = {'i': 1, 'j': 1, 'a': 2, 'b': 2, 'c': 2,
           'd': 3, 'e': 3, 'f': 3, 'g': 4, 'h': 4,
           'k': 5, 'l': 5, 'm': 6, 'n': 6, 'p': 7,
           'r': 7, 's': 7, 't': 8, 'u': 8, 'v': 8,
           'w': 9, 'x': 9, 'y': 9, 'o': 0, 'q': 0, 'z': 0}


def create_words(number, amount):
    words = {}

    for i in range(int(amount)):

        word = str(input())
        key = ""

        key = "".join([str(example.get(j)) for j in word])

        if key in str(number):
            words[key] = word

    return words


def create_answers(number, words):
    answers = {}

    for i in words.keys():

        if i != number[:len(i)]:
            continue

        answer = [words[i]]
        answer_key = i

        copy = number[len("".join(answer)):]
        x = len(copy)
        while x > 0:
            if copy[:x] in words.keys():
                answer.append(words[copy[:x]])
                answer_key += copy[:x]
                copy = copy[x:]
                x = len(copy) + 1
            x -= 1

        if len(answer) == 0:
            continue
        elif len(answer) in answers.keys():
            continue
        elif answer_key == n:
            answers[len(answer)] = answer
        else:
            continue

    return  answers

while True:
    n = input()

    if int(n) == -1:
        break

    a = input()

    i = create_answers(n, create_words(n, a))

    if len(i) == 0:
        print("No solution.")
    else:
        y = min(i.keys())
        print(" ".join(i[y]))

Edited by author 09.12.2017 22:06

#include <iostream>
#include <vector>
#include <set>
using namespace std;
set < pair <int, int> > S;
set < pair <int, int> > :: iterator it;
vector <int> A[1111], B[1111];
int n, k, m, x[1111], y[1111], res, X[1111], Y[1111];
bool used[111111];
void cut_x(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && X[i] == v && y[Y[i]] > 1){used[i] = true; y[Y[i]] --; res --;}
    }
}
void cut_y(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && Y[i] == v && x[X[i]] > 1){used[i] = true; x[X[i]] --; res --;}
    }
}
int main(){
    cin >> n >> m >> k;
    res = k;
    for (int i = 0; i < k; i ++){
        int u, v;
        cin >> X[i] >> Y[i];
        A[X[i]].push_back(Y[i]);
        B[Y[i]].push_back(X[i]);
        x[X[i]] ++; y[Y[i]] ++;
    }
    for (int i = 1; i <= n; i ++)
        S.insert(make_pair(x[i], i));
    for (it = S.begin(); it != S.end(); it ++){
        pair <int, int> v = *it;
        if(v.first == 1){
            cut_y(A[v.second][0]);
        }else{
            cut_x(v.second);
        }
    }
    cout << res;
}

visual C++ 2017 can't  use gets() too egg hurt

I wrote the following code. It takes 0.748 s, 13 524 KB. Can you suggest something faster?

[code deleted]


Edited by author 01.05.2016 22:19

Edited by moderator 04.12.2019 21:38

I hate such tasks so much! It's not programming, it's pure math!! So how did you proved the algorithm? I broke my brain truying to solve it!!

Help me please, if you can
I wrote a program, but i got rt#4 i don't know why
I tried different tests(M=0;M=100 and other) but it was all in vain
Very grateful for any help!
Sorry for bad English

Edited by author 03.12.2017 20:04

I think this is a no solution test

I output empty and pass this test...

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > v;
    int x, p;
    for(int i = 1; i <= n; i ++)
    {
        cin >> x >> p;
        v.pb({p, x});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for(int i = 0; i < n; i ++)
    {
        cout << v[i].second << " " << v[i].first << "\n";
    }
}
But it is same sort

I implemented a prefix tree using pointers and it crashed. I don't know why : for me it worked at max test. But as soon as I moved to an array implementation, it worked!

antihash test

I have used bitmasks.
There are only 16 possible Hamming codes.
So,  I have precalculated.
Then check,  whether input is a valid code.
Then try to find such valid code that it differs from input in exactly one position (I have
used xoring for that)  and print that codr.  Don't forget about zero code.  That is a special case.

i have WA6
for correct input of price
use procedure like this
int        read_price(void) {
    double f;
    fscanf(inf,"%lf",&f);
    return (int)((f+1e-9)*100.0);
}
and you got AC

Hello. Could somebody tell me a right DP approach to this problem. I couldn't figure out the solution better than O(|S|*M). |S| - length of the string.

   Hi everybody,
   After a lot of testing I have wa21 ... Is there anything spacial about this test case ? Thanks in advance.

Edited by author 18.07.2009 22:28

int n,i=0; -- AC
int n,i; -- - WA №1

import java.util.Scanner;

public class ex2031 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
     Scanner sc=new Scanner(System.in);
     int n=sc.nextInt();
     if(n==1){
         System.out.println("11");
     }else{
         if(n==2){
             System.out.println("11"+" "+"01");
         }else{
             if(n==3){
                 System.out.println("001"+" "+"66"+" "+"86");
             }else{
                 if(n==4){
                     System.out.println("16"+" "+"06"+" "+"68"+" "+"88");
                 }else{
                     System.out.println("Glupenky Pierre");
                 }
             }
         }
     }
    }

}