Неверная кодировка при работе с кириллицей - C (СИ)

Формулировка задачи:

Вводится строка и каждый 2й '!' меняется на '$'. При вводе русских букв вместо их печатаются какието каракули,както данную проблему решить можно? Сообщения типа "Измененная строка" отображаются нормально,проблема только с строкой вводимой с клавиатуры.Компилятор MS VS 2008.

#include <stdio.h>
#include <conio.h> 
#include <math.h>
#include <process.h>
#include <locale.h>
#include <malloc.h>
#include <string.h>

void zamena(char*);
void main ( )
 
{setlocale(LC_CTYPE, "Russian");
 char c ;
 char *s;   
 s= new char[100];
 int i;
printf ("введите строку\n");
gets (s);
printf("\n \n");
puts(s);
zamena(s);
//printf("sum=%d\n",sum);
printf("\n Измененная строка\n");
 
puts(s);
_getch();
 
}
void zamena(char*s){
     int i, j;
     int sum;
    sum=1;
for (i=0;i<=strlen(s);i++){setlocale(LC_CTYPE, "Russian");
if(s[i] == '!'){sum=sum+1; if (sum%2) { s[i] = '$';}}}
 }

Решение задачи: «Неверная кодировка при работе с кириллицей»

Листинг программы

#include<Windows.h>
SetConsoleCP(866);

Объяснение кода листинга программы

Включаем библиотеку Windows.h - это позволяет использовать функции Windows API в нашем коде.
Устанавливаем кодовую страницу 866 для консоли с помощью функции SetConsoleCP. Это позволяет работать с символами кириллицы в консоли.